实验名称：栈与队列

1、班级： 学号： 姓名： 实验组别： 实验日期： 报告日期： 成绩： 报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：栈与队列一、实验目的（1）掌握栈、队列的思想及其存储实现。（2）掌握栈、队列的常见算法的程序实现。二、实验要求(1).编写函数,采用链式存储实现栈的初始化、入栈、出栈操作。(2).编写函数,采用顺序存储实现栈的初始化、入栈、出栈操作。(3).编写函数,采用链式存储实现队列的初始化、入队、出队操作。(4).编写函数,采用顺序存储实现队列的初始化、入队、出队操作。(5).编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。三、实验原理（流程图）：开始顺序

2、实现栈操作链式实现栈操作顺序实现队列操作链式实现队列操作退出chioce=5输入选择的功能模块chioce结束YN四、实验数据（源代码）：#include #define ERROR 0#define OK 1#define MAX 100/栈的最大值using namespace std;typedef int SElemType;typedef int QElemType;typedef structSElemType *base; SElemType *top;SqStack;void InitStacka(SqStack &S)/顺序存储实现栈的初始化 S.base=(SElemTyp

3、e *) new SElemTypeMAX; if(!S.base) cout=MAX) cout栈已满; *S.top+=x;void Popa(SqStack &S)/顺序存储实现栈的出栈操作SElemType *p; int x; if(S.top=S.base) return ; else p=S.top; x=*-S.top; cout删除的栈顶元素是x出栈操作完成后的栈为:endl; void printa(SqStack S)/输出SElemType *p; p=S.base; coutendl; while(p!=S.top) cout*(p+);coutendl;typede

4、f struct SqNodeSElemType data; SqNode *Link;*Sqptr,NODE;typedef structSqptr top;Stack;void InitStackb(Stack &S)/链式存储实现栈的初始化; S.top=(Sqptr) new NODE; if(!S.top) coutLink=NULL;void Pushb(Stack &S,int x)/链式存储实现栈的入栈操作Sqptr p; p=(Sqptr) new NODE; if(!p) return; p-data=x; p-Link=S.top-Link; S.top-Link=p;v

5、oid Popb(Stack &S)/链式存储实现栈的出栈操作int x; Sqptr p; if(S.top-Link=NULL) return; else p=S.top-Link; x=p-data; S.top-Link=p-Link; cout删除的栈顶元素是x; free(p);typedef struct QNodeQElemType data; struct QNode *next;*QueuePtr,QNode;typedef structQueuePtr front; QueuePtr rear;LinkQueue;void InitQueue(LinkQueue &Q)/

6、链式存储实现队列的初始化 Q.front=Q.rear=(QueuePtr) new QNode; if(!Q.front) coutnext=NULL;void EnQueue(LinkQueue &Q,QElemType x)/链式存储实现队列的入队QueuePtr p; p=(QueuePtr) new QNode; if(!p) coutdata=x; p-next=NULL; Q.rear-next=p; Q.rear=p;void DeQueue(LinkQueue &Q)/链式存储实现队列的出队int x; if(Q.front=Q.rear) return; QueuePtr

7、p; p=Q.front-next; x=p-data; cout删除的队头元素是:next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return;typedef structSElemType *base; int front,rear;SqQueue;void InitQueueb(SqQueue &S)/顺序存储实现队列的初始化 S.base=(SElemType *) new SElemTypeMAX; if(!S.base) cout申请空间失败; S.front=S.rear=0;void EnQueueb(SqQueue &S,

8、int x)/顺序存储实现队列的入队if(S.rear+1)%MAX=S.front) return; S.baseS.rear=x; S.rear=(S.rear+1)%MAX;void DeQueueb(SqQueue &S)/顺序存储实现队列的出队int x; if(S.front=S.rear) return; x=S.baseS.front; S.front=(S.front+1)%MAX; cout删除的队头元素是:x;int main()int choice;do int n,x; int tui=1; coutendl; cout栈与队列; coutendl; cout-end

9、l; cout1.采用顺序存储实现栈的初始化、入栈、出栈操作endl; cout2.采用链式存储实现栈的初始化、入栈、出栈操作endl; cout3.采用顺序存储实现队列的初始化、入队、出队操作endl; cout4.采用链式存储实现队列的初始化、入队、出队操作endl; cout5.退出使用endl;cout-endl; coutchoice; switch(choice) case 1:SqStack S; cout-endl; cout1.顺序存储实现栈的初始化endl; cout2.顺序存储实现栈的入栈操作endl; cout3.顺序存储实现栈的出栈操作endl; cout4.退出n;

10、 cout-endl; while(tui) coutn; switch(n) case 1:InitStacka(S); cout顺序存储栈的初始化完成!endl; break; case 2:cout以0结束endl; coutx; while(x) Pusha(S,x); cinx; cout顺序存储栈的入栈操作完成!endl; printa(S);break; case 3:Popa(S); printa(S); break; case 4:tui=0; break; case 2:Stack Sa; cout-endl; cout1.链式存储实现栈的初始化endl; cout2.链式

11、存储实现栈的入栈操作endl; cout3.链式存储实现栈的出栈操作endl; cout-endl; while(1) coutn; switch(n) case 1:InitStackb(Sa); cout链式存储栈的初始化完成!endl; break; case 2:cout以0结束nendl;coutx; while(x) Pushb(Sa,x);cinx; cout链式存储栈的入栈操作完成!endl;break; case 3:Popb(Sa);break;break; case 3:SqQueue Sv; cout-endl; cout1.顺序存储实现队的初始化endl; cout2

12、.顺序存储实现队的入栈操作endl; cout3.顺序存储实现队的出栈操作endl; cout-endl; while(1) coutn; switch(n) case 1:InitQueueb(Sv); cout链式存储栈的初始化完成!endl;break; case 2:cout以0结束nendl;coutx; while(x) EnQueueb(Sv,x);scanf(%d,&x); cout链式存储栈的入栈操作完成!endl;break; case 3: DeQueueb(Sv);break; break; case 4:LinkQueue Q; cout-endl; cout1.链式

13、存储实现队的初始化endl; cout2.链式存储实现队的入栈操作endl; cout3.链式存储实现队的出栈操作endl; cout-endl; while(1) coutn; switch(n) case 1:InitQueue(Q); cout链式存储队的初始化完成!endl;break; case 2:cout以0结束;coutx; while(x) EnQueue(Q,x);cinx; cout链式存储队的入栈操作完成!endl;break; case 3:DeQueue(Q);break; break;while (choice!=5);return 0;五、程序运行结果：1采用顺序存储实现栈的初始化、入栈、出