#include<stdio.h>
#include<stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <windows.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 100
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int SElemType;
typedef int Status;
typedef struct
{
SElemType *base;//棧底指針
SElemType *top;//棧頂指針
int stacksize;//棧的最大容量
}SqStack; //順序棧類型定義
typedef int elemtype;
typedef struct node //隊列結點類型定義
{ elemtype data; //隊列的數據元素類型
struct node *next; //指向后繼結點的指針
}NODE;
typedef struct
{ //定義鏈隊
NODE *front,*rear;//定義鏈隊隊頭和隊尾指針
}LINKQUEUE;
Status InitStack(SqStack &s); //初始化棧
Status DisplayStack(SqStack s); //輸出棧
Status ClearStack(SqStack &s);//清空棧
bool StackEmpty(SqStack s); //棧是否為空
Status Push(SqStack &s,SElemType e); //入棧
Status Pop(SqStack &s,SElemType &e); //出棧
Status GetTop(SqStack s,SElemType &e); //取棧頂數據元素
void menu(SqStack s,LINKQUEUE *p);//顯示菜單
//初始化棧
Status InitStack(SqStack &s)
{
s.base = (SElemType *)malloc(sizeof(SElemType));
if(!s.base)
exit(OVERFLOW);
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
return OK;
}
//輸出棧
Status DisplayStack(SqStack s)
{
if(s.base == NULL)
{
printf("棧不存在或者已被銷毀！");
return ERROR;
}
if(StackEmpty(s))
{
printf("這是一個空棧！");
return ERROR;
}
SElemType *p = s.top;
while(p != s.base)
{
p--;
printf("%d ", *p);
}
printf("\n");
return OK;
}
//棧是否為空
bool StackEmpty(SqStack s)
{
if(s.base == s.top)
return true;
else
return false;
}
//棧元素個數
int StackLength(SqStack s)
{
return s.top - s.base;
}
//入棧
Status Push(SqStack &s,SElemType e)
{
if(StackLength(s) >= s.stacksize)
{
s.base = (SElemType *)realloc(s.base, (s.stacksize+STACKINCREMENT) * sizeof(SElemType));
if(!s.base)
return ERROR;
s.top = s.base + s.stacksize;
s.stacksize += STACKINCREMENT;
}
*(s.top++) = e;
return OK;
}
//出棧
Status Pop(SqStack &s,SElemType &e)
{
if(StackEmpty(s))
return ERROR;
e = * --s.top;
return OK;
}
//清空棧
Status ClearStack(SqStack &s)
{
s.base = s.top;
return OK;
}
//取棧頂數據元素
Status GetTop(SqStack s,SElemType &e)
{
if(StackEmpty(s))
return ERROR;
e = *(s.top - 1);
return OK;
}
void initqueue(LINKQUEUE *QL)//隊列的初始化
{
QL->front=(NODE *)malloc(sizeof(NODE));//隊列為帶頭結點的鏈隊列
QL->front->next=NULL;
QL->rear=QL->front;
}
LINKQUEUE *pushqueue(LINKQUEUE *QL,elemtype x)
{ //將元素x插入到鏈隊列QL中，作為QL的新隊尾
QL->rear->next=(NODE *)malloc(sizeof(NODE));
QL->rear->next->data=x;
QL->rear=QL->rear->next;
QL->rear->next=NULL;
return QL;
}
elemtype popqueue(LINKQUEUE *QL)
{ //若鏈隊列不為空，則刪除隊頭元素，返回其元素值
NODE *newnode;
newnode=QL->front->next;
if(newnode==NULL)
return 0;
newnode=QL->front;
QL->front=QL->front->next;
free(newnode);
return(QL->front->data);
}
void printqueue(LINKQUEUE *QL)//隊列的顯示
{
NODE *p;
p=QL->front->next;
if(p==NULL)
printf("隊列空!");
while(p!=NULL)
{
if(p->next==NULL)
printf("%d",p->data);
else
printf("%d<--",p->data);
p=p->next;
}
printf("\n");
}
//主菜單
void menu(SqStack s,LINKQUEUE *p)
{
int length,i,n,j,x,elemdata,y;
SElemType elem;
p=(LINKQUEUE *)malloc(sizeof(LINKQUEUE));
initqueue(p);
while(1)
{
printf("——————主菜單——————\n");
printf("1.初始化順序棧\n");
printf("2.插入一個元素\n");
printf("3.刪除棧頂元素\n");
printf("4.置空順序棧\n");
printf("5.棧頂元素\n");
printf("6.輸出順序棧\n");
printf("7.入隊列\n");
printf("8.出隊列\n");
printf("9.遍歷整個隊列\n");
printf("0.退出\n");
scanf("%d",&x);
switch(x)
{
case 1:
SElemType e;
InitStack(s);
printf("請輸入您要入棧的元素個數:");
scanf("%d", &n);
printf("請輸入要入棧的元素內容：\n");
for(j = 0; j <n; j++)
{
SElemType t;
scanf("%d", &t);
Push(s, t);
}
break;
case 2:
printf("請輸入要入棧的元素內容：");
scanf("%d", &elem);
Push(s, elem)?printf("入棧成功！"):printf("入棧失敗！");
break;
case 3:
Pop(s, elem)?printf("出棧成功！"):printf("出棧失敗！");
printf("\n出棧的元素內容為：%d", elem);
break;
case 4:
ClearStack(s);
printf("順序棧已清空！");
break;
break;
case 5:
GetTop(s, elem);
printf("\n棧頂元素：%d", elem);
break;
case 6:
DisplayStack(s);
break;
case 7:
printf("請輸入進隊元素：");
scanf("%d",&elemdata);
p=pushqueue(p,elemdata);
printf("隊列中的元素為：\n");
printqueue(p);
// system("pause");
break;
case 8:
y=popqueue(p);
// if(y!=0)
printf("元素%d出隊!\n",y);
printf("隊列中的元素為：\n");
printqueue(p);
// system("pause");
break;
case 9:
printf("隊列中的元素分別為：\n");
printqueue(p);
system("pause");
break;
case 0:
exit (0);
break;
default:
printf("error\n");
}
}
}
//主函數
main()
{
SqStack s;
LINKQUEUE *p;
menu(s,p);
}
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
