数据结构栈和队列

实验二栈和队列一、实验目的1. 掌握栈的顺序表示和实现2. 掌握队列的链式表示和实现二、实验内容1. 编写一个程序实现顺序栈的各种基本运算。

2. 实现队列的链式表示和实现。

三、实验步骤1. 初始化顺序栈2. 插入元素3. 删除栈顶元素4. 取栈顶元素5. 遍历顺序栈6. 置空顺序栈7. 初始化并建立链队列8. 入链队列9. 出链队列10. 遍历链队列四、实现提示1. /*定义顺序栈的存储结构*/typedef struct {ElemType stack[MAXNUM];int top;}SqStack;/*初始化顺序栈函数*/void InitStack(SqStack *p){q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/void Push(SqStack *p,ElemType x){if(p->top<MAXNUM-1){p->top=p->top+1; /*栈顶+1*/p->stack[p->top]=x; } /*数据入栈*/}/*出栈函数*/ElemType Pop(SqStack *p){x=p->stack[p->top]; /*将栈顶元素赋给x*/p->top=p->top-1; } /*栈顶-1*//*获取栈顶元素函数*/ElemType GetTop(SqStack *p){ x=p->stack[p->top];}/*遍历顺序栈函数*/void OutStack(SqStack *p){ for(i=p->top;i>=0;i--)printf("第%d个数据元素是：%6d\n",i,p->stack[i]);} /*置空顺序栈函数*/void setEmpty(SqStack *p){ p->top= -1;}2. /*定义链队列*/typedef struct Qnode{ ElemType data;struct Qnode *next;}Qnodetype;typedef struct{ Qnodetype *front;Qnodetype *rear;}Lqueue;/*初始化并建立链队列函数*/void creat(Lqueue *q){ h=(Qnodetype*)malloc(sizeof(Qnodetype)); /*初始化申请空间*/ h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++)*利用循环快速输入数据*/{ scanf("%d",&x);Lappend(q,x);} /*利用入链队列函数快速输入数据*/}/*入链队列函数*/void Lappend(Lqueue *q,int x){ s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;}/*出链队列函数*/ElemType Ldelete(Lqueue *q){ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);} /*释放空间*//*遍历链队列函数*/void display(Lqueue *q){ while(p!=NULL) /*利用条件判断是否到队尾*/{ printf("%d-->",p->data);p=p->next;}}五、思考与提高1. 读栈顶元素的算法与退栈顶元素的算法有何区别？2. 如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。

若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。

如何解决这个问题？（1）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？（2）一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现。

即双向栈共享邻接空间。

如果一个程序中要用到两个队列，能否实现？如何实现？六、完整参考程序1.栈的顺序表示和实现#include <stdio.h>#include <stdlib.h>#include <conio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int SElemType;//----- 栈的顺序存储表示-----#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct {SElemType *base;SElemType *top;int stacksize;} SqStack;Status InitStack(SqStack &S);Status DestroyStack(SqStack &S);Status StackDisplay(SqStack &S);Status GetTop(SqStack S,SElemType &e);Status Push(SqStack &S,SElemType e);Status Pop(SqStack &S,SElemType &e);Status StackEmpty(SqStack S);Status InitStack(SqStack &S){//构造一个空栈SS.base = (SElemType *) malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base) exit(OVERFLOW); //存储分配失效S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}//InitStackStatus DestroyStack(SqStack &S){//销毁栈Sif(S.base) free(S.base);S.top = S.base = NULL;return OK;}//InitStackStatus StackDisplay(SqStack &S){//显示栈SSElemType * p=S.base;int i = 0;if(S.base == S.top){printf("堆栈已空!\n");return OK;}while( p < S.top)printf("[%d:%d]",++i,*p++);printf("\n");return OK;}//StackDisplayStatus GetTop(SqStack S,SElemType &e){//若栈不空，则用e返回S的栈顶元素，//并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(S.top-1);return OK;}//GetTopStatus Push(SqStack &S,SElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.base=(SElemType*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if( ! S.base ) exit(OVERFLOW);//存储分配失败S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}* S.top ++ = e;return OK;}//PushStatus Pop(SqStack &S,SElemType &e){//若栈不为空，则删除S的栈顶元素，//用e返回其值，并返回OK；否则返回ERRORif (S.top == S.base) return ERROR;e = * --S.top;return OK;}//PopStatus StackEmpty(SqStack S){//若S为空栈，则返回TRUE，否则返回FALSE。

if(S.top == S.base) return TRUE;else return FALSE;}// StackEmptyvoid main(){SqStack St;Status temp;int flag=1,ch;int e;printf("本程序实现顺序结构的堆栈的操作。

\n");printf("可以进行入栈，出栈，取栈顶元素等操作。

\n");InitStack(St); //初始化堆栈Stwhile(flag){printf("请选择:\n");printf("1.显示栈中所有元素\n");printf("2.入栈\n");printf("3.出栈\n");printf("4.取栈顶元素\n");printf("5.退出程序\n");scanf("%d",&ch);switch(ch){case 1:StackDisplay(St);break;case 2:printf("请输入要入栈的元素(一个整数):");scanf("%d",&e); //输入要入栈的元素temp=Push(St,e); //入栈if(temp!=OK) printf("堆栈已满!入栈失败!\n");else {printf("成功入栈!\n"); //成功入栈StackDisplay(St);}break;case 3:temp=Pop(St,e); //出栈if(temp==ERROR) printf("堆栈已空!\n");else {printf("成功出栈一个元素:%d\n",e); //成功出栈StackDisplay(St);}break;case 4:temp=GetTop(St,e); //取得栈顶元素if(temp==ERROR) printf("堆栈已空!\n");else printf("栈顶元素是:%d\n",e); //显示栈顶元素break;default:flag=0;printf("程序结束，按任意键退出!\n");getch();}}DestroyStack(St);}2. 队列的链式表示和实现#include <conio.h>#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2//Status 是函数的类型,其值是函数结果状态代码typedef int Status;//ElemType 是顺序表数据元素类型,此程序定义为int型typedef int QElemType;//-----单链队列--队列的链式存储结构-----typedef struct QNode{ //定义结点结构QElemType data; //数据域struct QNode *next; //指针域}QNode,*QueuePtr;typedef struct linkqueue{ //定义队列结构QueuePtr front; //队头指针QueuePtr rear; //队尾指针}LinkQueue;Status InitLinkQueue(LinkQueue &); //初始化一个队列Status DestroyLinkQueue(LinkQueue &); //销毁一个队列int LinkQueueLength(LinkQueue &Q); //队列的长度Status EnLinkQueue(LinkQueue &,QElemType); //将一个元素入队列Status DeLinkQueue(LinkQueue &,QElemType &);//将一个元素出队列Status DisplayLinkQueue(LinkQueue); //显示队列中所有元素void main(){LinkQueue LQ;QElemType e;int flag=1,ch,len;Status temp;printf("本程序实现链式结构队列的操作。