加粗样式实验二 栈和队列基本操作的实现
实验目的
1.掌握栈、队列的思想及其存储实现
2.掌握栈、队列基本操作的实现
实验内容
1.编写函数，采用链式存储实现栈的初始化、入栈、出栈操作。
2.编写函数，采用顺序存储实现栈的初始化、入栈、出栈操作。
3.编写函数，采用链式存储实现队列的初始化、入队、出队操作。
4.编写函数，采用顺序存储实现队列的初始化、入队、出队操作。
5.编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述函数。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define Status int
#define SElemType int
#define MaxSize 100
#define QElemType int
//菜单
void menu()
{
printf("********1.入栈 2.出栈*********\n");
printf("********3.退出*********\n");
}
//**************************************顺序栈基本操作函数************************************//
//顺序栈数据结构
typedef struct Stack
{
SElemType *base;//栈底指针
SElemType *top;//栈顶指针
int stacksize;//栈可用的最大容量
}SqStack;
//初始化函数
Status InitStack(SqStack &s)
{
s.base=new SElemType[MaxSize];//动态分配最大容量
if(!s.base)
{
printf("分配失败\n");
return 0;
}
s.top=s.base;//
s.stacksize=MaxSize;
return 1;
}
//入栈
Status Push(SqStack &s,SElemType e)
{
if(s.top-s.base==s.stacksize) return 0;//栈满
*(s.top++)=e;//先压栈再++
return 1;
}
//出栈 用e返回值
Status Pop(SqStack &s,SElemType &e)
{
if(s.top==s.base) return 0;//栈空
e=*--s.top;//先减减 指向栈顶元素，再给e
return 1;
}
//********************************功能实现函数**************************************//
//入栈功能函数 调用Push函数
void PushToStack(SqStack &s)
{
int n;SElemType e;int flag;
printf("请输入入栈元素个数(>=1)：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入第%d个元素的值:",i+1);
scanf("%d",&e);
flag=Push(s,e);
if(flag)printf("%d已入栈\n",e);
else {printf("栈已满！！！\n");break;}
}
}
//出栈功能函数 调用Pop函数
void PopFromStack(SqStack &s)
{
int n;SElemType e;int flag;
printf("请输入出栈元素个数(>=1)：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
flag=Pop(s,e);
if(flag)printf("%d已出栈\n",e);
else {printf("栈已空！！！\n");break;}
}
}
//**************************链栈基本操作函数***************************//
//链栈结点数据结构
typedef struct StackNode
{
SElemType data;//数据域
struct StackNode *next;//指针域
}StackNode,*LinkStack;
//初始化函数
Status InitStack(LinkStack &S)
{
S = NULL;//生成空栈 以单链表表头为栈顶 链栈没有像链表似的头结点
return 1;
}
//入栈函数 将e压入栈
Status Push(LinkStack &S,SElemType e)
{
StackNode *p;
p=new StackNode;
p->data=e; //赋值
p->next=S; //压入栈顶
S=p;
return 1;
}
//出栈函数 栈顶出栈用e返回 注意释放空间
bool Pop(LinkStack &S,SElemType &e)
{
LinkStack p;
if(S==NULL)return false;//栈空
e=S->data;
p=S;
S=S->next;
free(p);
return true;
}
//**************************功能实现函数***************************//
//入栈功能函数 调用Push函数
void PushToStack(LinkStack &S)
{
int n;SElemType e;int flag;
printf("请输入入栈元素个数(>=1)：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入第%d个元素的值:",i+1);
scanf("%d",&e);
flag=Push(S,e);
if(flag)printf("%d已入栈\n",e);
}
}
//出栈功能函数 调用Pop函数
void PopFromStack(LinkStack &S)
{
int n;SElemType e;int flag;
printf("请输入出栈元素个数(>=1)：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
flag=Pop(S,e);
if(flag)printf("%d已出栈\n",e);
else {printf("栈已空！！！\n");break;}
}
}
//***************************循环队列基本操作函数**************************//
//循环队列数据结构
typedef struct
{
QElemType *base;//数据域
int front,rear; //队头队尾指针
}SqQueue;
//初始化函数
Status InitQueue(SqQueue &Q)
{
Q.front=Q.rear=0;
return 1;
}
//判断队空函数
bool QueueEmpty(SqQueue Q)
{
if(Q.front!=Q.rear)return false;
else return true;
}
//入队函数
bool EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MaxSize==Q.front)return false; //队列满 牺牲一个以判断
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MaxSize;//指针加1 取模
return true;
}
//出队函数
bool DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear) return false;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MaxSize;
return 1;
}
//**************************功能实现函数****************************//
//入队功能函数 调用EnQueue函数
void EnterToQueue(SqQueue &Q)
{
int n;QElemType e;int flag;
printf("请输入入队元素个数(>=1)：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入第%d个元素的值:",i+1);
scanf("%d",&e);
flag=EnQueue(Q,e);
if(flag)printf("%d已入队\n",e);
else {printf("队已满！！！\n");break;}
}
}
//出队函数 调用DeQueue函数
void DeleteFromQueue(SqQueue &Q)
{
int n;QElemType e;int flag;
printf("请输入出队元素个数(>=1)：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
flag=DeQueue(Q,e);
if(flag)printf("%d已出队\n",e);
else {printf("队已空！！！\n");break;}
}
}
//**************************链队基本操作函数***************************//
//链队结点数据结构
typedef struct QNode
{
QElemType data;//数据域
struct QNode *next;//指针域
}QNode,*QueuePtr;
typedef struct
{
struct QNode *front,*rear;//rear指针指向队尾 用于入队 front指针指向队头 用于出队
}LinkQueue;
//初始化函数
Status InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=new QNode;//生成新节点作为头结点，队头队尾指针均指向它
Q.front->next=NULL;
return 1;
}
//入队函数
Status EnQueue(LinkQueue &Q,QElemType e)
{
QNode *p;
p=new QNode;//生成新节点
p->data=e; //赋值
p->next=NULL;
Q.rear->next=p;//加入队尾
Q.rear=p; //尾指针后移
return 1;
}
//出队函数 队头出队用e返回 注意释放空间
bool DeQueue(LinkQueue &Q,QElemType &e)
{
QueuePtr p;
if(Q.front==Q.rear)return false;//队空
e=Q.front->next->data; //e返回值 头结点没数据的，一定要注意头结点
p=Q.front->next; //保留，释放空间
Q.front->next=p->next; //出队
if(Q.rear==p)Q.rear=Q.front; //最后一个元素出队，rear指向头结点
free(p);
return true;
}
//**************************功能实现函数***************************//
//入队功能函数 调用EnQueue函数
void EnterToQueue(LinkQueue &Q)
{
int n;QElemType e;int flag;
printf("请输入入队元素个数(>=1)：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("请输入第%d个元素的值:",i+1);
scanf("%d",&e);
flag=EnQueue(Q,e);
if(flag)printf("%d已入队\n",e);
}
}
//出队功能函数 调用DeQueue函数
void DeleteFromQueue(LinkQueue &Q)
{
int n;QElemType e;int flag;
printf("请输入出队元素个数(>=1)：\n");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
flag=DeQueue(Q,e);
if(flag)printf("%d已出队\n",e);
else {printf("队已空！！！\n");break;}
}
}
int main()
{ int choice;
while(1){
printf("\t\t1.实现顺序栈的基本操作\n\n");
printf("\t\t2.实现链栈的基本操作\n\n");
printf("\t\t3.实现循环队列的基本操作\n\n");
printf("\t\t4.实现链队的基本操作\n\n");
printf("\t\t5.退出\n\n");
printf("\n\n\n\t请输入菜单序号：");
scanf("%d",&choice);
if(choice==5)break;
switch(choice)
{
case 1:
SqStack s;int num;
InitStack(s);
while(1)
{
menu();
printf("请输入菜单序号(顺序栈)：\n");
scanf("%d",&num);
if(num==3) break;
switch(num)
{
case 1:PushToStack(s);break;
case 2:PopFromStack(s);break;
default:printf("输入错误！！！\n");
}
}
break;
case 2:
LinkStack S;int choice;
InitStack(S);
while(1)
{
menu();
printf("请输入菜单序号(链栈)：\n");
scanf("%d",&choice);
if(choice==3) break;
switch(choice)
{
case 1:PushToStack(S);break;
case 2:PopFromStack(S);break;
default:printf("输入错误！！！\n");
}
}
break;
case 3:
SqQueue Q;int a;
InitQueue(Q);
while(1)
{
menu();
printf("请输入菜单序号(循环队列)：\n");
scanf("%d",&a);
if(a==3) break;
switch(a)
{
case 1:EnterToQueue(Q);break;
case 2:DeleteFromQueue(Q);break;
default:printf("输入错误！！！\n");
}
}
break;
case 4:
LinkQueue Z;int b;
InitQueue(Z);
while(1)
{
menu();
printf("请输入菜单序号(链队)：\n");
scanf("%d",&b);
if(b==3) break;
switch(b)
{
case 1:EnterToQueue(Z);break;
case 2:DeleteFromQueue(Z);break;
default:printf("输入错误！！！\n");
}
}
break;
}
}
return 0;
}
版权声明：本文为cytcytcytcytcyt原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。