数据结构（C语言版）（第三版）（微课版）第3章 栈和队列

第3章栈和队列教学要求相关知识点相关术语：栈、队列物理结构：顺序栈、链栈、顺序队列、链队列学习重点栈的逻辑结构、存储结构及其相关算法队列的逻辑结构、存储结构及其相关算法目录队列本章小结3栈123.1栈3.1栈栈的定义栈(Stack)是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(base)。不含任何数据元素的栈称为空栈。假设栈S=（a0，a1，…，an-1），则称a0为栈底元素，an-1为栈顶元素。栈中元素按a1，a2，…，an-1的顺序进栈，退栈从栈顶元素开始出栈。所以，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（LIFO：lastinfirstout）的线性表。3.1栈栈的顺序存储与操作1.顺序栈的定义顺序栈是指利用顺序存储分配方式来实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。通常用一维数组存储数据元素，并预设一个最大空间。把数组中下标为0的一端作为栈底，为了指示栈中元素的位置，定义top指示栈顶元素在顺序栈中的位置。3.1栈顺序栈分为静态顺序存储和动态顺序存储，静态顺序存储的栈一次性分配空间，在栈满后不能追加空间进行入栈操作，而动态顺序存储是在静态顺序存储的基础上增加了可追加空间的功能。静态存储是将top定义为整数，而动态存储是将top定义为指针。top可以指向栈顶元素的下一个位置，也可以指向栈顶元素。3.1栈(1)栈的静态分配顺序存储结构描述#defineMaxSize100 /*定义静态栈最大长度*/typedefstruct{SElemTypebase[MaxSize];/*定义一个存放栈数据元素的一维数组*/inttop;/*栈顶指针*，可以指向栈顶元素的下一位置或者指向栈顶元素/intStackSize;/*存储顺序栈的当前长度*/}SeqStack;3.1栈我们使用数组来实现栈中元素的存储，并设存储栈元素的数组长度为StackSize。当栈满时再进行进栈运算必定产生溢出，简称“上溢”；当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免。下溢是正常现象，常常用来作为程序控制转移的条件。3.1栈①top为整数且指向栈顶元素的下一个位置当top为整数且指向栈顶元素的下一个位置时，初始化条件为S.top=0。(a)栈空S.top==0(b)入栈S.base[S.top++]=e3.1栈(c)栈满S.top>=MaxSize

(d)出栈*e=S.base[--S.top]3.1栈②top为整数且指向栈顶元素当top为整数且指向栈顶元素时，初始化条件S.top=-1(a)栈空S.top==-1(b)元素入栈S.base[++S.top]=e3.1栈

(c)栈满S.top>=MaxSize-1

(d)元素出栈*e=S.base[S.top--]3.1栈(2)栈的动态分配顺序存储结构描述栈的动态分配顺序存储结构是通过将top定义为指针来实现的。#defineSTACK_INIT_SIZE10 /*存储空间初始化分配量*/#defineSTACK_INCREMENT2 /*存储空间分配增量*/typedefintSElemType;3.1栈typedefstructSqStack{SElemType*base;/*栈底指针，始终指向栈底的位置*/int*top; /*栈顶指针，可以指向栈顶元素的下一个位置或者指向栈顶元素*/intStackSize; /*当前分配的栈可使用的以元素为单位的最大存储容量*/}SqStack; /*顺序栈*/3.1栈①top为指针且指向栈顶元素的下一个位置当top为指针且指向栈顶元素的下一个位置时，初始化条件为S.top=S.base。(a)栈空S.top==S.base

(b)元素入栈*S.top++=e3.1栈(c)栈满S.top-S.base>=StackSize

(d)元素出栈*e=*--S.top3.1栈②top为指针且指向栈顶元素当top为指针且指向栈顶元素时，初始化条件为S.top=S.base-1。(a)栈空S.top==S.base-1(b)元素入栈*++S.top=e3.1栈

(c)栈满S.top-S.base+1>=StackSize

(d)元素出栈*e=*S.top--3.1栈2.顺序栈的基本操作（top为指针且指向栈顶元素下一个位置的动态顺序栈存储的基本操作）(1)构造一个空栈SintInitStack(SqStack*S)/*成功返回1失败返回0*/{S->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S->base)return0;/*存储分配失败*/S->top=S->base;//top为指针且指向栈顶元素下一个位置S->StackSize=STACK_INIT_SIZE;return1;}3.1栈(2)销毁栈算法3.2销毁栈voidDestroyStack(SeqStack*S){if(S!=NULL){free(S->base);/*释放栈*/S->top=S->base=NULL;//top为指针且指向栈顶元素下一个位置S->StackSize=0;}}3.1栈(3)清空栈voidClearStack(SqStack*S){S->top=S->base;}//top为指针且指向栈顶元素下一个位置(4)判断一个栈是否为空intStackEmpty(SqStackS)/*若栈S为空栈，则返回1，否则返回0*/{if(S.top==S.base)return1;elsereturn0;}3.1栈(5)求栈的长度算法3.5求一个栈的长度intLengthStack(SqStackS){if((S.base)&&(S.top))

return(S.top-S.base);//top为指针且指向栈顶元素下一个位置}3.1栈(6)取栈顶元素算法3.6取栈顶元素intGetTop(SqStackS,SElemType*e)/*若栈不空，则用e返回S的栈顶元素，并返回1；否则返回0*/{if(S.top>S.base)//top为指针且指向栈顶元素下一个位置{*e=*(S.top-1);return1;}elsereturn0;}3.1栈(7)入栈操作让数据元素e进栈，首先要判断栈是否未满，若是则栈顶指针右移一位，将数据元素e存入栈顶指针所指位置。intPush(SqStack*S,SElemTypee)/*所插入元素e为新的栈顶元素，如果插入成功，返回1，否则返回0，top为指针且指向栈顶元素下一个位置*/{if(S->top-S->base>=S->StackSize) /*栈满，追加存储空间*/{S->base=(SElemType*)realloc(S->base,(S->StackSize+STACKINCREMENT)*sizeof(SElemType));3.1栈if(!(S->base)return0;/*存储分配失败*/S->top=S->base+S->StackSize;/*修改栈底指针*/S->StackSize+=STACKINCREMENT;}*(S->top)++=e;//将e入栈，成为新的栈顶元素return1;}3.1栈(8)出栈操作退出一个栈内节点并得到栈顶数据元素的值。首先判断栈是否为空栈，若不空则取得栈顶元素并且栈高度-1。intPop(SqStack*S,SElemType*e)/*若栈不空，则删除S的栈顶元素，用e返回值，并返回1；否则返回0，top为指针且指向栈顶元素下一个位置*/{if(S->top==S->base)return0;/*栈空*/*e=*--S->top;//栈底元素赋给e，栈顶指针下移return1;}3.1栈(9)遍历栈算法3.9遍历栈voidStackTraverse(SqStackS,void(*visit)(SElemType)){while(S.top>S.base)//top为指针且指向栈顶元素下一个位置printf("%2d",*S.base++);}3.1栈栈的链式存储与操作1.链栈的定义栈用链式存储结构实现简称链栈。链栈中指针的方向是从栈顶指向栈底，图3.5中的S为栈顶指针。3.1栈链栈的定义可以描述如下：typedefstructnode{elemtypedata;

structnode*next;}NODE,*NODEPTR#defineLENsizeof(NODE)3.1栈2.链栈的一些基本操作(1)建立一个空栈只要利用已经定义的链表的节点指针类型声明一个栈顶指针，并将其置为空即可。建立一个空栈的代码语句如下：intInit_Stack(NodePtrtop)/*构造空栈，返回1*/{top=NULL;return1;}3.1栈(2)进栈操作，让数据元素e进入链栈在链式存储结构下，不需要像顺序存储那样需要判断栈是否未满，但需要建立一个新节点，并给新节点分配相应的内存空间。若系统分配空间失败，则新节点e进栈失败，否则将数据元素存入新节点，并将新节点挂载到链头，并作为新链头。3.1栈intPush_Stack(NodePtrtop,elemtypee){NodePtrp;

p=(NodePtr)malloc(LEN);

if(p==NULL) {printf(“系统分配空间失败！”); return0;}

p->data=e; /*存入新节点元素值*/

p->next=top; /*新节点与原栈顶相连接*/

top=p; /*新节点作为新栈顶*/return1;}3.1栈(3)出栈操作，让一个节点出栈并得到栈顶数据元素的值首先判断栈是否为空，若不为空则获取栈顶元素值，并将链头节点删除，原链头的后继节点作为新栈顶。3.1栈intPop_Stack(NodePtrtop,elemtype*e){NodePtrp;p=top;

if(p==NULL){printf(“栈为空，无法操作！”); return0;}*e=p->data; /*取得栈顶节点元素值*/

top=p->next;/*栈顶指针后移，删除栈顶节点*/

free(p); /*释放被删除节点所占用的内存空间*/return1;}3.2队列3.2队列队列的定义队列(queue)是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。a0是队头元素an-1是队尾元素3.2队列队列的顺序存储与操作1.顺序队列的数据类型定义#defineMaxSize10 //顺序队列的最大容量typedefstruct{ElemType*data;//定义队列元素的存储空间

intfront,rear; /*定义队头和队尾指针*/}SqQueue定义指向队列的指针变量：SqQueue*sq;申请顺序队列的存储空间：sq->base=(ElemType*)malloc(MaxSize*sizeof(ElemType));3.2队列2.顺序队列的操作(1)front为队头元素当前位置，rear为队尾元素下一个位置①置空队列sq->front=sq->rear=0;②入队操作sq->data[sq->rear]=a; /*将新元素a入队*/sq->rear++;3.2队列③出队操作*e=sq->data[sq->front];//将队头元素a出队sq->front++;④计算队列中元素个数n=(sq->rear)-(sq->front)当队列真满时，n=MaxSize当队列空时，n=03.2队列(2)front为队头元素前一个位置，rear为队尾元素当前位置①置空队列sq->front=sq->rear=-1;②元素入队sq->rear++;sq->data[sq->rear]=a; /*将新元素a入队*/3.2队列③出队操作sq->front++;*e=sq->data[sq->front];//将队头元素a出队④队列中元素个数n=(sq->rear)-(sq->front)当队列真满时，n=MaxSize当队列空时，n=03.2队列3.顺序队列存在的假溢出现象图3.8是顺序队列的各种操作示意图，从图中可以看到不管是入队操作还是出队操作，整个队列都会随着操作的进展向数组中下标较大的位置方向移动，因为从上述相关操作可以看到，都会执行“++”这一步，于是就出现了图3.8(d)的情况，此时队尾指针rear已经移到了所分配空间的最后一个位置，但是此时队列中并没有满载，可以看出所分配的存储空间的下半部分几乎完全空闲，并没有元素存储进来。这种现象我们称为“假溢出”。出现假溢出现象的主要原因是队列本身“队尾进入，队头出”的特性所导致的。3.2队列问题由于队列的进队操作是在两端进行的，随着元素的不断插入，删除，两端都向后移动，队列会很快移动到数组末端造成溢出，而前面的单元无法利用。解决办法：每次删除一个元素后，将整个队列向前移动一个单元，保持队列头总固定在数组的第一个单元。将所用的数组想象成是头尾相接的圆环，当队列的尾端到达数组的末端（第n个单元）时，如果再插入元素可继续使队列向数组的前端（第1个单元）延长，此队列称为循环队列。3.2队列4.循环队列解决假溢出，让第MaxSize个元素进入到第0个空间中(利用取余数运算%)。使队列数据区形成一个循环，头尾指针front、rear的指示不变，这种结构称为循环队列。3.2队列入队时，将队尾的自加1操作修改为：sq->rear=(sq->rear+1)%MaxSize;出队时，将队头指针的自加1操作修改为：sq->front=(sq->front+1)%MaxSize;判断一个循环队列是否队满为：（Q.rear+1）%MaxSize==Q.front判断一个队列是否为空可用表达式：Q.rear==Q.front计算队中元素长度应为：(Q.rear-Q.front+MaxSize)%MaxSize3.2队列队列的链式存储与操作1.链队列的数据类型定义typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;/*队头指针*/QueuePtrrear;/*队尾指针*/}LinkQueue;3.2队列2.链队列的操作(1)建立一个空队列利用已经定义的链表的节点指针类型声明一个队头和队尾指针，并将指针置为空即可，这里不再像顺序存储的章节中那样需要一个队列长度，因为在链队列中不需要做队满判断，只要内存空间还存在可用的位置，就可以不停地完成入队操作；而在进行队空判定时也只需要查验队头指针是否为空即可，也不再需要借助队列中元素的个数判断。3.2队列建立一个空链队列的算法如下：voidInitQueue(LinkQueue*Q){/*初始化一个队列*/

Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q->front)exit(0);/*生成头节点失败*/

Q->front->next=NULL;}3.2队列(2)判断一个队列是否为空，算法如下：StatusQueueEmpty(LinkQueueQ){/*判断队列是否为空*/

if(Q.front->next==NULL) return1;

elsereturn0;}3.2队列(3)入队操作让数据元素e进入队列，首先要建立一个新节点e，然后判断队列是否为空，若是空队列，则此e进入队列后既是队头又是队尾，否则就将节点e直接链接到队尾，并将队尾指针后移一个节点即可。3.2队列voidEnQueue(LinkQueue*Q,QElemTypee){/*所插入的元素e为队列Q的新队尾元素*/

QueuePtrp;

p=(QueuePtr)malloc(sizeof(QNode));/*动态生成新节点*/

if(!p) exit(0);

p->data=e;/*将e的值赋给新节点*/

p->next=NULL;/*新节点的指针为空*/