#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空间
腾讯微博
腾讯朋友
收藏
淘帖
顶
踩
