第三章栈和队列的应用【实验目的】1．熟练掌握栈和队列的结构，以及这两种数据结构的特点；2．能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；3．熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；第一节知识准备一、栈：1. 基本概念栈是一种限定仅在表的一端进行插入与删除操作的线性表。
允许进行插入与删除操作的这一端称为栈顶，而另一端称为栈底，不含元素的空表称为空栈，插入与删除分别称进栈与出栈。
由于插入与删除只能在同一端进行，所以较先进入栈的元素，在进行出栈操作时，要比较后才能出栈。
特别是，最先进栈者，最后才能出栈，而最晚进栈者，必最先出栈。
因此，栈也称作后进先出（Last In First Out）的线性表，简称LIFO表。
栈示意图见图3-12. 栈的抽象数据类型定义：ADT Stack{数据对象：D={ | ∈ElemSet, i=1,2,...,n, n>=0}数据关系：R1={< , >| , ∈D, i=2,...,n}基本操作：InitStack(&S) 构造一个空栈SStackEmpty(S) 判断栈S是否为空StackLength(S) 返回栈S的元素个数,即栈的长度GetTop(S,&e) 取栈S的栈顶元素Push(&S,e) 将元素e入栈Pop(&S,&e) 删除S的栈顶元素并用e返回其值（即出栈）}ADT Stack3. 栈的表示：栈有两种存储表示方法：顺序存储结构和链式存储结构。
(1)顺序存储结构：#define STACK_INIT_SIZE 100； //存储空间初始分配量#define STACKINCREMENT 10； //存储空间分配增量typedef struct{SElemType *base； //栈底指针SElemType *top； //栈顶指针int StackSize； //栈的当前容量}SqStack；(2)链式存储结构：Typedef struct Lnode{ElemType data;struct Lnode *next;}Lnode, *LinkList;二、队列：1. 与栈相对应，队列是一种先进先出的线性表。
它只允许在表的一端进行插入，而在另一端进行删除元素。
允许插入的一端称队尾，允许删除的一端称队头。
插入与删除分别称为入队与出队。
队列示意图见图3-2：──────────────出队←a1 a2 …… an-1 ←an进队──────────────队头队尾图3-2 队列2. 队列的抽象数据类型定义：ADT Queue{数据对象：D={ | ∈ElemSet, i=1,2,...,n, n>=0}数据关系：R1={< , >| , ∈D, i=2,...,n}基本操作：InitQueue(&Q) 构造一个空队列QQueueEmpty(Q) 判断队列是否为空QueueLenght(Q) 返回队列Q的元素个数，即队列的长度GetHead(Q,&e) 取队列Q的队头元素，并用e返回EnQueue(&Q,e) 将元素e入队列DeQueue(&Q,&e) 删除非空队列Q的队头元素，并用e返回其值}ADT Queue3. 队列的表示：队列有两种表示方法：链队列、循环队列（顺序队列）。
（1）链队列的表示：typedef struct QNode{QElemType data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;(2) 循环队列的表示（见第二节）第二节循环队列的表示和实现【问题描述】设计一个抽象数据类型队列的顺序表示和实现的演示程序。
【数据描述】#define MaxQsize 100 //最大队列长度typedef struct {QElemType *base;//初始化的动态分配存储空间int front; //头指针，若队列不空，指向队列头元素int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置}SqQueue;【算法描述】Status InitQueue(SqQueue &Q){//构造一个空队列QQ.base=(QelemType *)malloc(MaxQsize*sizeof(QelemType));if(!Q.base) exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;return OK;}Status QueueEmpty(SqQueue Q){//若队列Q为空队列，则返回TRUE，否则返回FALSEif(Q.front﹦﹦Q.rear) return TRUE;else return FALSE;}int QueueLength(SqQueue Q){//返回Q的元素个数，即为队列的长度return(Q.rear-Q.front+MaxQsize)% MaxQsize;}Status GetHead(SqQueue Q,QelemType &e){//若队列不为空，则用e返回Q的队头元素，并返回OK；否则返回ERRORif(Q.front==Q.rear) return ERROR;e=Q.base[Q.front];return OK;}Status EnQueue(SqQueue &Q,QelemType e){//插入元素e为Q的新的队尾元素if((Q.rear+1)%MaxQsize==Q.front) return ERROR;//队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MaxQsize;return OK;}Status DeQueue(SqQueue &Q,QelemType &e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK,否则返回ERRORif(Q.rear==Q.front) return ERROR;//队列空e=Q.base[Q.front];Q.front=(Q.front+1)%MaxQsize;return OK;}【C源程序】#include <stdio.h>#include <stdlib.h>typedef int QElemType;typedef int Status;#define OK 1#define TRUE 1#define FALSE 0#define ERROR 0#define OVERFLOW -2#define MaxQsize 100 /*最大队列长度*/typedef struct {QElemType *base; /*初始化的动态分配存储空间*/int front; /*头指针，若队列不空，指向队列头元素*/int rear; /*尾指针，若队列不空，指向队列尾元素的下一个位置*/ }SqQueue;Status InitQueue(SqQueue *Q){/*构造一个空队列Q*/(*Q).base=(QElemType *)malloc(MaxQsize*sizeof(QElemType));if(!(*Q).base) return(OVERFLOW);/*存储分配失败*/(*Q).front=(*Q).rear=0;return OK;}Status QueueEmpty(SqQueue Q){/*若队列Q为空队列，则返回TRUE，否则返回FALSE*/if(Q.front==Q.rear) return TRUE;else return FALSE;}int QueueLength(SqQueue Q){/*返回Q的元素个数，即为队列的长度*/return(Q.rear-Q.front+MaxQsize)% MaxQsize;}Status GetHead(SqQueue Q,QElemType *e){/*若队列不为空，则用e返回Q的队头元素，并返回OK；否则返回ERROR*/if(Q.front==Q.rear) return ERROR;*e=Q.base[Q.front];return OK;}Status EnQueue(SqQueue *Q,QElemType e){/*插入元素e为Q的新的队尾元素*/if(((*Q).rear+1)%MaxQsize==(*Q).front) return ERROR;/*队列满*/(*Q).base[(*Q).rear]=e;(*Q).rear=((*Q).rear+1)%MaxQsize;return OK;}Status DeQueue(SqQueue *Q,QElemType *e){/*若队列不空，则删除Q的队头元素，用e返回其值，并返回OK,否则返回ERROR*/ if((*Q).rear==(*Q).front) return ERROR;/*队列空*/*e=(*Q).base[(*Q).front];(*Q).front=((*Q).front+1)%MaxQsize;return OK;}main(){SqQueue Q;int select;QElemType e;if (InitQueue(&Q)==OVERFLOW)printf("分配失败，即将退出程序！");else/*否则显示队列操作的菜单，并选择相应的基本操作*/do {printf("1：判断队列是否为空\n");printf("2：测试队列的长度\n" );printf("3：取队头元素值\n");printf("4：向队列中插入一新元素\n");printf("5：删除队列中一元素\n");printf("0：结束\n");scanf("%d",&select);switch (select) {case 1: if (QueueEmpty(Q)==TRUE) printf("队列为空\n");else printf("队列不为空\n");break;case 2: printf("队列长度为：%d\n",QueueLength(Q));break;case 3: if(GetHead(Q,&e)==ERROR) printf("队列为空\n");else printf("队首元素为：%d\n",e);break;case 4: scanf("%d",&e);if(EnQueue(&Q,e)==ERROR) printf("队列满\n");else printf("元素成功插入\n");break;case 5: if(DeQueue(&Q,&e)==ERROR) printf("队列空,无数据可删\n"); else printf("删除元素为：%d\n",e);break;case 0: printf("操作结束\n");break;default:printf("输入选择出错！\n");}/*switch*/}while (select);}/*main_end*/【测试数据】读者根据运行提示和显示的功能菜单实现循环队列的基本操作。