数据结构堆栈和队列的基本应用与原理

CH3栈和队列教学内容：本章介绍应用广泛的数据结构——栈(stack)和队列(queue)，将分别给出这两种结构的定义、基本运算、存储结构以及一些基本运算的具体实现，并给出一些应用实例。教学重点与难点重点是掌握栈和队列在两种存储结构上实现的基本运算难点是应用栈解决一些实际问题，以及循环队列中对边界条件的处理。教学目标掌握栈和队列这两种数据结构的特点，了解在什么问题中应该使用哪种结构。熟悉几个关系：栈（队列）和线性表的关系；顺序栈（顺序队列）和顺序表的关系；链栈（链队列）和链表的关系。重点掌握在顺序栈和链栈上实现的栈的七种基本运算，特别注意栈满和栈空的条件及它们的描述。重点掌握在循环队列和链队列上实现的七种基本运算，特别注意队满和队空的描述方法。熟悉栈和队列的下溢和上溢的概念；顺序队列中产生假上溢的原因；循环队列消除假上溢的方法。

3.1栈栈的定义栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表。通常称允许插入、删除这一端为栈顶（top），另一端称为栈底(bottom)。栈的修改是按后进先出的原则进行的，故又称栈为LIFO表(LastInFirstOut)。栈的特征栈的逻辑结构和我们先前学过的线性表相同。栈的运算规则与线性表相比有更多的限制。an……a2a1栈底栈顶入栈出栈3.1.1栈的抽象数据类型定义ADTStack{

数据对象：D={ai|ai∈ElemSet;1≤i≤n,n≥0;} 数据关系：R={<ai,ai+1>|ai,ai+1∈D,i=1,2,……,n-1}

基本操作：

InitStack(&S)DestroyStack(&S)StackEmpty(S)StackLength(S)GetTop(G,&e)Push(&S,e)Pop(&S,&e)StackTraverse(S,visit())

}//ADTStack3.1.2栈的顺序存储表示和实现1.栈的顺序存储表示#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;basetopan……a2a1２.基本操作的算法表示初始化一个空栈

判栈空取栈顶元素入栈出栈1)初始化一个空栈StatusInitStack(SqStack&S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exitOVERFLOW;S.top=S.base;S.StackSize=STACK_INIT_SIZE; returnOK;}s.bases.top2)取栈顶元素和元素出栈StatusGetTop(SqStackS,ElemType&e){if(S.base==S.top)returnERROR;e=*(S.top-1);returnOK;}StatusPop(SqStack&S,ElemType&e){if(S.base==S.top)returnERROR;e=*--S.top;//--S.top;e=*S.top;returnOK;}s.bases.topan……a2a13)元素入栈StatusPush(SqStack&S,ElemTypee){if(S.top-S.base>=S.stacksize){ newbase=(ElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW);S.base=newbase;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//*S.top=e;S.top++;returnOK;}s.bases.topan……a2a1思考题：一个栈的入栈序列为：123，那么可能得到的出栈序列是什么？答：321，231，213，132，123。2.设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何？(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。3.1.3栈的共享存储单元引言思考：两个栈如何共享存储空间？ “底设两端、相向而动、迎面增长”3.1.4链栈的表示和实现1.栈的链式存储表示typedefstructSNode{ElemTypedata;structSNode*next;}SNode,*LinkStack;问：链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的首指针就可以了。anan-1ai+1ai^a1……栈顶栈底Ｓ3.链栈基本操作的实现初始化 S=NULL；入栈 申请结点p；p->data=e;p->next=S;S=p;判空：

S==NULL出栈：if(S==NULL)

returnERROR;else{p=S;S=p->next;e=p->data;free(p); }anan-1ai+1ai^a1……栈顶栈底Ｓ练习(1) 栈是限定在__________处进行插入或删除操作的线性表。A.端点 B.栈底 C.栈顶 D.中间(2) 4个元素按A、B、C、D顺序连续进S栈，进行Pop(S,x)运算后，x的值是___________。A.A B.B C.C D.D(3) 栈的特点是__________。A.先进先出 B.后进先出C.后进后出 D.不进不出(4) 栈与一般线性表的区别主要在____方面。A.

元素个数

B.元素类型C.逻辑结构

D.插入、删除元素的位置(5)一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列的是______。A.2，3，4，1，5，B.5，4，1，3，2，C.2，3，1，4，5，D.1，5，4，3，23.2栈的应用举例3.2.1数制转换

voidconversion(){InitStack(S);scanf("%d",&N);while(N){Push(S,N%8);N=N/8;}//whilewhile(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}将除8的余数依次入栈S，先得的余数为低位，后得的余数为高位。从栈顶到栈底元素依次出栈，得到对应的8进制数3.2栈的应用举例3.2.2括号匹配的检查例如：（［］（））［（［］［］）］［（］）（［（））（（）]）算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余StatusCompare(){InitStack(S);flag=TURE;while（（ch=getchar()）！=‘#’）&&flag）{switch(ch){case‘(‘:case‘[‘:caxe‘{‘:Push(S,ch);break;case‘)’:if(Pop(S,e)==ERROR||e!=‘(‘)flag=FALSE;break;case‘]’:if(Pop(S,e)==ERROR||e!=‘[‘)flag=FALSE;break;case‘}’:if(Pop(S,e)==ERROR||e!=‘{‘)flag=FALSE;break; }//switch}if(flag&&ch==‘#’&&StackEmpty(S))returnTRUE;elsereturnFALSE;}3.2.3迷宫求解出口入口求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。求迷宫中一条从入口到出口的路径的算法：设定当前位置的初值为入口位置；

do｛

若当前位置可通，则｛将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；｝否则{…

…｝｝while(栈不空）；3.2.4表达式求值运算规则实现思想设置两个工作栈运算符栈操作数栈算法描述⊙2

⊙1＋－×／（）#＋＞＞＜＜＜＞＞－＞＞＜＜＜＞＞×＞＞＞＞＜＞＞／＞＞＞＞＜＞＞（＜＜＜＜＜＝error）＞＞＞＞error＞＞#＜＜＜＜＜error＝运算规则OperandTypeEvaluateexpress(){InitStack(OPTR);Push(OPTR,’#’);InitStack(OPND);c=getchar();while(c!=‘#’||GetTop(OPTR)!=‘#’){if（c为操作数）{Push(OPND,c);c=getchar();}else

switchPrecede(GetTop(OPTR),c){case‘<‘:Push(OPTR,c);c=getchar();break;case‘=‘:Pop(OPTR,c);c=getchar();break;case‘>’:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;}//switch}//while}//Evaluateexpress有关思考与提示算符优先表的存储和表示;栈的选择（静态顺序栈---用数组表示）判断c是否为算符。Operate(a,theta,b)的实现Intchange(charc){Switchcof{case‘+’:i=0;break;case‘-’:i=1;break;case‘*’:i=2;break;case‘/’:i=3;break;case‘(’:i=4;break;case‘)’:i=5;break;case‘#’:i=6;break;}Returni;}CharPrecede(charc1,charc2){Chara[7][7]={‘>><<<>>’,‘>><<<>>’,’>>>><>>’,’>>>><>>’, ‘<<<<<=‘,’>>>>>>’,’<<<<<=‘}i=change(c1);j=change(c2);Returna[i][j]}课堂提问：栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于运算规则不同。一般线性表堆栈逻辑结构：线性结构逻辑结构：线性结构存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)“进”＝插入=入栈“出”＝删除=出栈3.3栈与递归的实现一、函数调用与返回通常，当一个函数调用另一个函数时，在执行被调用函数前系统要预先做三件事情：将所有的实参和函数返回地址等信息传递给被调用函数；为被调用函数的局部变量分配存储空间将控制转移到被调用函数的入口处。而在从被调用函数返回调用函数之前，系统也需要做如下三件事情：保存被调用函数的计算结果；释放为被调用函数局部变量分配的数据空间；按返回地址将控制转移给调用函数。二、函数的嵌套调用当多个函数构成嵌套调用时，系统按照先调用后返回的原则进行工作。这种信息的传递和控制转移符合后进先出的原则，使用栈来实现是非常自然的。例：设有一个主程序，它调用函数a，函数a又调用函数b，函数b又调用函数c，（见下页），其中r，s，t分别表示中断地址，我们可以用一个栈来描述调用情况（见下页）r主程序srrrs函数1rst函数2rst函数3注：系统将整个程序运行期间所需要的存储空间都利用一个工作栈来管理，每当调用（或执行）一个函数时，就为它在栈顶分配一个存储区；每当退出（或执行完）一个函数时，就释放为它所分配的存储区；当前工作的函数的数据区总在工作栈的当前栈顶位置。三、递归函数的执行过程递归函数的执行过程类似于嵌套调用时的情况，只不过是在直接递归时的调用函数和被调用函数是同一个函数罢了递归是程序设计中一个强有力的工具，可以解决许多实际应用问题：递归定义的数学函数递归的数据结构问题的定义是递归的3.3.1递归的定义与实现1.很多数学函数的定义是递归的。例：阶乘的定义和实现。n!=1n=0n*(n-1)！n>0longfact(longn){if(n==0)return1;elsereturnn*fact(n-1);}例如：fact(4)fact(3)fact(2)fact(1)fact(0)112624函数调用与返回

返回值2.递归的数据结构例1：线性链表结构打印非空链表f的最后一个结点的数据值voidfind(Linklistf){if(f->next==NULL)printf(f->data);elsefind(f->next);}例2：树型结构n-1个3.问题的解法是递归的例：Hanoi塔问题分析：n个X

Y

Z

将X轴上的n－1个盘子借助Z轴移到Y轴上；将X轴上的余下的1个盘子移到Z轴上；

将Y轴上的n－1个盘子借助X轴移到Z轴上X求解算法及调用示意图voidhanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);}}Hanoi(3,a,b,c)Hanoi(1,a,b,c)Hanoi(1,b,c,a)Hanoi(1,c,a,b)Hanoi(1,a,b,c)Hanoi(2,a,c,b)Hanoi(2,b,a,c)move(a,c)move(a,c)move(b,c)move(b,a)move(c,b)move(a,b)move(a,c)n=3的调用示意图1.递归过程调用过程回推过程2.递归工作栈目的：保证递归函数正确执行，系统设立工作栈作为递归函数运行期间使用的数据存储区。

内容：函数返回地址本次调用时与形参结合的实参本层的局部变量值3.3.2递归过程与递归工作栈递归算法的优点和缺点利用递归算法（函数、过程、子程序等）编写的程序具有结构简洁清晰、易读易理解等优点。然而由于使用栈来实现这种“调用—返回”的递归过程，无论在时间上还是在空间上都比相应的非递归程序的开销要大。3.4队列队列的定义队列(Queue)是仅限制在表的一端进行插入，另一端进行删除运算的线性表。通常称允许插入一端为队尾（rear），另一端称为队头(front)。队列的修改是按先进先出的原则进行的，故又称栈为FIFO表(FastInFirstOut)。队头队尾入队列出队列anan-1…a3a2a1例如：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。乘坐公共汽车，应该在车站排队，车来后，按顺序上车。在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。3.4.1队列的抽象数据类型定义ADTQueue{数据对象：D={ai|ai∈ElemSet;1≤i≤n,n≥0;}数据关系：R={<ai,ai+1>|ai,ai+1∈D,i=1,2,……,n-1}， 约定a1端为队列头，an端为队列尾基本操作：

InitQueue(&Q) DestroyQueue(&Q)QueueEmpty(Q) QueueLength(Q)GetHead(Q,&e) EnQueue(&Q,e)DelQueue(&Q,&e)}ADTQueue

3.4.2链队列的表示和实现单链队列的定义

typedefstructQnode{ ElemTypedata; structQnode*next;}Qnode,*QueuePtr;typedefstruct{ QueuePtrfront； QueuePtrrear;}LinkQueue带头结点的链队列示意图：

a1a2^an…Q.frontQ.rear

1.队列的初始化 StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));if(!Q.front)exitOVERFLOW;Q.front->next=NULL;returnOK;}Q.frontQ.rear^2.队列的销毁StatusDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}a1a2^an…Q.frontQ.rear3.入队列StatusEnQueue(LinkQueue&Q,ElemTypee){p=(QueuePtr)malloc(sizeof(Qnode));if(!p)exitOVERFLOW;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}说明：所谓入队列即在队尾之后插入一个新结点，并让新结点成为新的队列尾.a1a2^an…Q.frontQ.rearp^e

Q.rear4.出队列StatusDeQueue(LinkQueue&Q,ElemType&e){if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}

注意：p指向被删除结点，需要考虑p是否为队尾结点指针。

a1a2^an…Q.frontQ.rearp5.取队首StatusGetHead(LinkQueueQ,ElemType&e){if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;returnOK;}

a1a2^an…Q.frontQ.rear

3.4.3队列顺序存储的表示和实现（1）空队列J1J2J3J4（2）J1、J2、J3、J4依次入队列J4（3）J1、J2、J3依次出队列J4J5J6（4）J5、J6依次入队列顺序队列的特点设立两棵指针Q.front和Q.rear队空的判定条件:Q.front==Q.rear队满的判定条件:Q.rear≥Q.Maxsize队列的顺序存储结构存储结构定义#defineMAXQSIZE100typedefstruct{ ElemType*base; intfront; intrear;}SqQueue;顺序队列的“溢出”问题(1)真溢出Q.rear－Q.front≥Q.Maxsize(2)假溢出顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。问题：如何解决顺序队列的“假溢出”问题？答：按最大可能的进队操作次数设置顺序队列的最大元素个数；修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置；修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向队头移动，然后方完成入队操作。采用循环队列；循环队列1.基本思想2.示意图顺序队列J1J2J3Q.frontQ.rear6543210J3J2J10123Q.rearQ.front循环队列循环队列一个新问题：在循环队列中，队空特征是Q.front＝Q.rear；队满时也会有Q.front＝Q.rear；判决条件将出现二义性！解决方案有三：①使用一个计数器记录队列中元素个数（即队列长度）；判队满：count＝MAXQSIZE判队空：count==0②加设标志位判队满：tag==1&&Q.rear==Q.front判队空：tag==0&&Q.rear==Q.front③少用一个存储单元判队满：Q.front==(Q.rear+1)%MAXQSIZE判队空：Q.rear==Q.front循环队列4.基本操作的算法分析与实现初始化求队列的长度入队列出队列循环队列1.队列的初始化StatusInitQueue(SqQueue&Q){Q.base＝(ElemType*)malloc(MAXQSIZE*sizeof(ElemType));if(!Q.base)exitOVERFLOW;Q.front＝Q.rear＝0;returnOK;}（1）空队列循环队列2.求队列的长度intQueueLength(SqQueueQ){return(Q.rear－Q.fron