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

1、CH3 栈和队列栈和队列n教学内容：教学内容：n本章介绍应用广泛的数据结构本章介绍应用广泛的数据结构 栈栈(stack)和队和队列列(queue)，将分别给出这两种结构的定义、基本将分别给出这两种结构的定义、基本运算、存储结构以及一些基本运算的具体实现，运算、存储结构以及一些基本运算的具体实现，并给出一些应用实例。并给出一些应用实例。n教学重点与难点教学重点与难点n重点是掌握栈和队列在两种存储结构上实现的基重点是掌握栈和队列在两种存储结构上实现的基本运算本运算n难点是应用栈解决一些实际问题，以及循环队列难点是应用栈解决一些实际问题，以及循环队列中对边界条件的处理。中对边界条件的处理。n教学目标

2、教学目标n掌握栈和队列这两种数据结构的特点，了解在什么问题中掌握栈和队列这两种数据结构的特点，了解在什么问题中应该使用哪种结构。应该使用哪种结构。n熟悉几个关系：熟悉几个关系：n栈（队列）和线性表的关系；栈（队列）和线性表的关系；n顺序栈（顺序队列）和顺序表的关系；顺序栈（顺序队列）和顺序表的关系；n链栈（链队列）和链表的关系。链栈（链队列）和链表的关系。n重点掌握在顺序栈和链栈上实现的栈的七种基本运算，特重点掌握在顺序栈和链栈上实现的栈的七种基本运算，特别注意栈满和栈空的条件及它们的描述。别注意栈满和栈空的条件及它们的描述。n重点掌握在循环队列和链队列上实现的七种基本运算，特重点掌握在循环队

3、列和链队列上实现的七种基本运算，特别注意队满和队空的描述方法。别注意队满和队空的描述方法。n熟悉栈和队列的下溢和上溢的概念；顺序队列中产生假上熟悉栈和队列的下溢和上溢的概念；顺序队列中产生假上溢的原因；循环队列消除假上溢的方法。溢的原因；循环队列消除假上溢的方法。 3.1 栈栈n栈的定义栈的定义n栈栈(Stack)是仅限制在表的一端进是仅限制在表的一端进行插入和删除运算的线性表。通行插入和删除运算的线性表。通常称允许插入、删除这一端为常称允许插入、删除这一端为栈栈顶顶（top），），另一端称为另一端称为栈底栈底(bottom)。n栈的修改是按后进先出的原则进栈的修改是按后进先出的原则进行的，故

4、又称栈为行的，故又称栈为LIFO表表(Last In First Out)。n栈的特征栈的特征n栈的逻辑结构和我们先前学过的栈的逻辑结构和我们先前学过的线性表相同。线性表相同。n栈的运算规则与线性表相比有更栈的运算规则与线性表相比有更多的限制。多的限制。ana2a1栈底栈底栈顶栈顶入栈入栈出栈出栈3.1.1 栈的抽象数据类型定义栈的抽象数据类型定义ADT Stack数据对象：数据对象：D=ai|aiElemSet;1in,n0; 数据关系：数据关系：R=| ai,ai+1D,i=1,2,n-1 基本操作：基本操作： InitStack(&S) DestroyStack(&S) StackEmp

5、ty(S) StackLength(S) GetTop(G,&e) Push(&S,e) Pop(&S,&e) StackTraverse(S,visit()/ ADT Stack3.1.2 栈的顺序存储表示和实现栈的顺序存储表示和实现n1.栈的顺序存储表示栈的顺序存储表示#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct ElemType *base; ElemType *top; int stacksize;SqStack;basetopana2a1n.基本操作的算法表示基本操作的算法表示n初始化一个空栈初始

6、化一个空栈n判栈空判栈空n取栈顶元素取栈顶元素n入栈入栈n出栈出栈1)初始化一个空栈初始化一个空栈Status InitStack(SqStack &S) S.base=(ElemType*) malloc(STACK_INIT_SIZE*sizeof(ElemType); if (!S.base) exit OVERFLOW; S.top=S.base; S.StackSize=STACK_INIT_SIZE; return OK;s.bases.top2)取栈顶元素和元素出栈取栈顶元素和元素出栈Status GetTop(SqStack S,ElemType &e) if (S.base=

7、S.top) return ERROR; e=*(S.top-1); return OK;Status Pop(SqStack &S,ElemType &e) if (S.base=S.top) return ERROR; e=*- -S.top; /- -S.top;e=*S.top; return OK;s.bases.topana2a13)元素入栈元素入栈Status Push(SqStack &S,ElemType e) if (S.top- S.base=S.stacksize) newbase=(ElemType*)realloc(S.base, (S.stacksize+STAC

8、KINCREMENT)*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+; return OK;s.bases.topana2a1思考题：思考题：n一个栈的入栈序列为：一个栈的入栈序列为：1 2 3，那么可能得到的出栈，那么可能得到的出栈序列是什么？序列是什么？n答：答：3 2 1，2 3 1，2 1 3 ，1 3 2 ，1 2 3。n2.设将整数设将

9、整数1，2，3，4依次进栈，但只要出栈时栈依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：答下述问题： n(1)若入、出栈次序为若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何？则出栈的数字序列为何？ n(2) 能否得到出栈序列能否得到出栈序列1423和和1432?并说明为什么不能得到并说明为什么不能得到或者如何得到。或者如何得到。 n(3)请分析请分析 1，2 ，3 ，4 的的24种排列中，哪些序列是可以通

10、种排列中，哪些序列是可以通过相应的入出栈操作得到的。过相应的入出栈操作得到的。 3.1.3 栈的共享存储单元栈的共享存储单元n引言引言n思考：两个栈如何共享存储空间？思考：两个栈如何共享存储空间？“底设两端、相向而动、迎面增长底设两端、相向而动、迎面增长”3.1.4 链栈的表示和实现链栈的表示和实现n1.栈的链式存储表示栈的链式存储表示typedef struct SNode ElemType data; struct SNode *next;SNode,*LinkStack;n问：问： 链栈中为何不设置头结点链栈中为何不设置头结点?n答：链栈不需要在头部附加头结点，因答：链栈不需要在头部附加

11、头结点，因为栈都是在头部进行操作的，如果加了为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要行操作，反而使算法更复杂，所以只要有链表的首指针就可以了。有链表的首指针就可以了。 anan-1ai+1aia1栈顶栈顶栈底栈底n3.链栈基本操作的实现链栈基本操作的实现n初始化初始化S=NULL；n入栈入栈申请结点申请结点p； p-data=e;p-next=S;S=p;n判空：判空：n S=NULLn出栈：出栈：if (S=NULL) return ERROR;else p=S; S=p-next; e=p-da

12、ta; free(p); anan-1ai+1aia1栈顶栈顶栈底栈底练习练习n(1) 栈是限定在栈是限定在_处进行插入或删除处进行插入或删除操作的线性表。操作的线性表。 nA. 端点端点 B. 栈底栈底 C. 栈顶栈顶 D. 中间中间n(2) 4个元素按个元素按A、B、C、D顺序连续进顺序连续进S栈，栈， 进行进行Pop(S,x)运算后，运算后，x的值是的值是_。nA.A B. B C. C D. Dn(3) 栈的特点是栈的特点是_。nA. 先进先出先进先出 B. 后进先出后进先出 nC. 后进后出后进后出 D. 不进不出不进不出n(4) 栈与一般线性表的区别主要在栈与一般线性表的区别主要在

13、_方面。方面。nA. 元素个数元素个数 B. 元素类型元素类型nC. 逻辑结构逻辑结构 D. 插入、删除元素的位置插入、删除元素的位置n(5) 一个栈的输入序列为一个栈的输入序列为1，2，3，4，5，则下，则下列序列中不可能是栈的输出序列的是列序列中不可能是栈的输出序列的是_。nA. 2，3，4，1，5，nB. 5，4，1，3，2，nC. 2，3，1，4，5， nD. 1，5，4，3，23. 2 栈的应用举例栈的应用举例n3.2.1 数制转换数制转换 void conversion() InitStack(S); scanf( %d ,&N); while (N) Push(S,N%8); N

14、=N/8; /while while(!StackEmpty(S) Pop (S,e); printf( %d ,e); 将除将除8的余数依次入栈的余数依次入栈S，先得的先得的余数为低位，后得的余数为高位余数为低位，后得的余数为高位。从栈顶到栈底元素依次出栈，从栈顶到栈底元素依次出栈，得到对应的得到对应的8进制数进制数3. 2 栈的应用举例栈的应用举例n3.2.2 括号匹配的检查括号匹配的检查n例如：n（）n（ ）n（ ）n（ ）n（）n算法的设计思想：算法的设计思想：n1）凡出现左括弧，则进栈；）凡出现左括弧，则进栈；n2）凡出现右括弧，首先检查栈是否空）凡出现右括弧，首先检查栈是否空n若栈

15、空，则表明该若栈空，则表明该“右括弧右括弧”多余多余n否则和栈顶元素比较，否则和栈顶元素比较，n若相匹配，则若相匹配，则“左括弧出栈左括弧出栈”n否则表明不匹配否则表明不匹配n3）表达式检验结束时，）表达式检验结束时，n若栈空，则表明表达式中匹配正确若栈空，则表明表达式中匹配正确n否则表明否则表明“左括弧左括弧”有余有余Status Compare( ) InitStack(S); flag=TURE; while （ch= getchar( )）！）！=#） & flag ） switch (ch) case ( :case :caxe :Push(S,ch);break;case ) :i

16、f ( 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) return TRUE; else return FALSE; 3.2.3 迷宫求解迷宫求解出出口口入入口口n求迷宫路径算法的基本思想是：求迷宫路径算法的基本思想是：n若当前位置若当前位置“可通可通”，则纳入路径，继续前进，则

17、纳入路径，继续前进;n若当前位置若当前位置“不可通不可通”，则后退，换方向继续探，则后退，换方向继续探索索;n若四周若四周“均无通路均无通路”，则将当前位置从路径中删，则将当前位置从路径中删除出去。除出去。n求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法：设定当前位置的初值为入口位置；设定当前位置的初值为入口位置； do 若当前位置可通，若当前位置可通， 则将当前位置插入栈顶；则将当前位置插入栈顶； 若该位置是出口位置，则算法结束；若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的当前位置；否则切换当前位置的东邻方块为新的当前位置； 否则否则 whi

18、le (栈不空）；栈不空）；3.2.4 表达式求值表达式求值n运算规则运算规则n实现思想实现思想n设置两个工作栈设置两个工作栈n运算符栈运算符栈n操作数栈操作数栈n算法描述算法描述 2 1（）#（error ）error运算规则运算规则 OperandType Evaluateexpress()InitStack(OPTR); Push(OPTR,#);InitStack(OPND); c=getchar( );while (c!=# | GetTop(OPTR)!=#) if （c为操作数）为操作数） Push(OPND,c);c=getchar(); else switch Precede

19、(GetTop(OPTR),c) case :Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b);break; /switch/while/ Evaluateexpressn有关思考与提示有关思考与提示n算符优先表的存储和表示算符优先表的存储和表示;n栈的选择（静态顺序栈栈的选择（静态顺序栈-用数组表示）用数组表示）n判断判断c是否为算符。是否为算符。nOperate(a,theta,b) 的实现的实现Int change(char c)Switch c ofcase +:i=0;break;case -:

20、i=1;break;case *:i=2;break;case /:i=3;break;case (:i=4;break;case ):i=5;break;case #:i=6;break;Return i;nChar Precede(char c1,char c2)Char a77=, , , ,0long fact(long n) if (n=0) return 1; else return n*fact(n-1);n例如：例如：fact(4)fact(3)fact(2)fact(1)fact(0)112624函数函数调用与返回调用与返回 返回值返回值n2.递归的数据结构递归的数据结构n例

21、例1：线性链表结构：线性链表结构打印非空链表打印非空链表f的最后一个结点的数据值的最后一个结点的数据值void find (Linklist f) if (f-next=NULL) printf(f-data); else find(f-next);n例例2：树型结构：树型结构n-1n-1个个3.问题的解法是递归的问题的解法是递归的例：例：Hanoi塔问题塔问题分析：分析：n n个个 X Y Z 1. 将将X轴上的轴上的n1个盘子借助个盘子借助Z轴移到轴移到Y轴上；轴上；2.将将X轴上的余下的轴上的余下的1个盘子移到个盘子移到Z轴上；轴上；3. 将将Y轴上的轴上的n1个盘子借助个盘子借助X轴移

22、到轴移到Z轴上轴上 X求解算法及调用示意图求解算法及调用示意图void hanoi(int n,char x,char y,char z) 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)m

23、ove(a,c)n=3的调用示意图的调用示意图1.递归过程递归过程调用过程调用过程回推过程回推过程2.递归工作栈递归工作栈 目的目的：保证递归函数正确执行，系统设立工作栈：保证递归函数正确执行，系统设立工作栈作为递归函数运行期间使用的数据存储区。作为递归函数运行期间使用的数据存储区。 内容内容： 函数返回地址函数返回地址 本次调用时与形参结合的实参本次调用时与形参结合的实参 本层的局部变量值本层的局部变量值3.3.2 递归过程与递归工作栈递归过程与递归工作栈n递归算法的优点和缺点递归算法的优点和缺点n利用递归算法（函数、过程、子程序等）编写利用递归算法（函数、过程、子程序等）编写的程序具有的程

24、序具有结构简洁清晰、易读易理解结构简洁清晰、易读易理解等优点。等优点。n然而由于使用栈来实现这种然而由于使用栈来实现这种“调用调用返回返回”的的递归过程，无论在递归过程，无论在时间时间上还是在上还是在空间空间上都比相上都比相应的非递归程序的开销要大。应的非递归程序的开销要大。3.4 队列队列n队列的定义队列的定义n队列队列(Queue)是仅限制在表的一端进行插入，另是仅限制在表的一端进行插入，另一端进行删除运算的线性表。通常称允许插入一端进行删除运算的线性表。通常称允许插入一端为一端为队尾队尾（rear），），另一端称为另一端称为队头队头(front)。n队列的修改是按先进先出的原则进行的，故

25、又队列的修改是按先进先出的原则进行的，故又称栈为称栈为FIFO表表(Fast In First Out)。队头队头队尾队尾入队列入队列出队列出队列anan-1a3a2a1n例如：例如：n到医院看病，首先需要到挂号处挂号，然后，按到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。号码顺序救诊。n乘坐公共汽车，应该在车站排队，车来后，按顺乘坐公共汽车，应该在车站排队，车来后，按顺序上车。序上车。n在在Windows这类多任务的操作系统环境中，每个这类多任务的操作系统环境中，每个应用程序响应一系列的应用程序响应一系列的“消息消息”，像用户点击鼠，像用户点击鼠标；拖动窗口这些操作都会导致向应用程

26、序发送标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。并依次给予响应。3.4.1 队列的抽象数据类型定义队列的抽象数据类型定义ADT Queue数据对象：数据对象：D=ai|aiElemSet;1in,n0;数据关系：数据关系：R=| ai,ai+1D,i=1,2,n-1， 约定约定a1端为队列头，端为队列头，an端为队列尾端为队列

27、尾基本操作：基本操作： InitQueue(&Q) DestroyQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q,&e) EnQueue(&Q,e) DelQueue(&Q,&e)ADT Queue 3.4.2 链队列的表示和实现链队列的表示和实现n单链队列的定义单链队列的定义typedef struct QnodeElemType data; struct Qnode *next;Qnode,*QueuePtr;typedef struct QueuePtr front； QueuePtr rear;LinkQueuen带头结点的链队列示意图

28、：带头结点的链队列示意图： a1a2anQ.front Q.rear 1. 队列的初始化队列的初始化Status InitQueue(LinkQueue &Q) Q.front=Q.rear= (QueuePtr)malloc(sizeof(Qnode); if (!Q.front) exit OVERFLOW; Q.front-next=NULL; return OK;Q.frontQ.rear2. 队列的销毁队列的销毁Status DestroyQueue(LinkQueue &Q) while (Q.front) Q.rear=Q.front-next; free(Q.front); Q

29、.front=Q.rear; return OK;a1a2anQ.frontQ.rear3. 入队列入队列Status EnQueue(LinkQueue &Q, ElemType e) p=(QueuePtr)malloc (sizeof(Qnode); if (!p) exit OVERFLOW; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;n说明：说明：n所谓入队列即在队尾之后插入一个新结点，并让新所谓入队列即在队尾之后插入一个新结点，并让新结点成为新的队列尾结点成为新的队列尾.a1a2anQ.frontQ.rear

30、pe Q.rear4. 出队列出队列Status DeQueue(LinkQueue &Q, ElemType &e) if (Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if (Q.rear=p) Q.rear=Q.front; free(p); return OK; 注意注意：p指向被删除结点，需要考虑指向被删除结点，需要考虑p是否为队尾结点指针。是否为队尾结点指针。 a1a2anQ.frontQ.rearp 5. 取队首取队首Status GetHead(LinkQueue Q,

31、 ElemType &e) if (Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; return OK; a1a2anQ.frontQ.rear 3.4.3 队列顺序存储的表示和实现队列顺序存储的表示和实现（1）空队列）空队列J1J2J3J4（2）J1、J2、J3、J4依次入队列依次入队列J4（3）J1、J2、J3依依次出队列次出队列J4J5J6（4）J5、J6依次依次入队列入队列顺序队列的特点顺序队列的特点1. 设立两棵指针设立两棵指针Q.front和和 Q.rear2. 队空的判定条件队空的判定条件:Q.front= Q.re

32、ar3. 队满的判定条件队满的判定条件:Q.rearQ.Maxsize队列的顺序存储结构队列的顺序存储结构n存储结构定义存储结构定义#define MAXQSIZE 100typedef struct ElemType *base; int front; int rear;SqQueue;n顺序队列的顺序队列的“溢出溢出”问题问题n(1)真溢出真溢出nQ.rear Q.front Q.Maxsizen(2)假溢出假溢出n顺序队列因多次入队和出队操作后出现的有存储空间顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。但不能进行入队操作的溢出。n问题：问题：n如何解决顺序队列

33、的如何解决顺序队列的“假溢出假溢出”问题？问题？n答：答：n按最大可能的进队操作次数设置顺序队列的最大按最大可能的进队操作次数设置顺序队列的最大元素个数；元素个数；n修改出队算法，使每次出队列后都把队列中剩余修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置；数据元素向队头方向移动一个位置；n修改入队算法，增加判断条件，当假溢出时，把修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向队头移动，然后方完成入队队列中的数据元素向队头移动，然后方完成入队操作。操作。n采用循环队列；采用循环队列；循环队列循环队列n1.基本思想基本思想n2.示意图示意图顺序队列顺序队列J

34、1J2J3Q.frontQ.rear6 5 4 3 210 J3J2J10123Q.rearQ.front 循环队列循环队列循环队列循环队列n一个新一个新问题问题：n在循环队列中，队空特征是在循环队列中，队空特征是Q.frontQ.rear；队队满时也会有满时也会有Q.frontQ.rear ；判决条件将出现二判决条件将出现二义性！义性！n解决方案有三：解决方案有三：n使用一个计数器记录队列中元素个数（即队列使用一个计数器记录队列中元素个数（即队列长度）；长度）；n判队满：判队满：countMAXQSIZEn判队空：判队空：count=0n加设标志位加设标志位n判队满：判队满：tag=1 &

35、Q.rear=Q.frontn判队空：判队空：tag=0 & Q.rear=Q.frontn 少用一个存储单元少用一个存储单元n判队满：判队满： Q.front=(Q.rear+1)%MAXQSIZEn判队空：判队空： Q.rear=Q.front循环队列循环队列n4.基本操作的算法分析与实现基本操作的算法分析与实现n初始化初始化n求队列的长度求队列的长度n入队列入队列n出队列出队列循环队列循环队列n1.队列的初始化队列的初始化Status InitQueue(SqQueue &Q) Q.base(ElemType*) malloc(MAXQSIZE*sizeof(ElemType); if

36、(!Q.base) exit OVERFLOW; Q.frontQ.rear0; return OK;（1）空队列）空队列循环队列循环队列n2.求队列的长度求队列的长度int QueueLength(SqQueue Q)return (Q.rearQ.front+MAXQSIZE) % MAXQSIZE;循环队列循环队列n2.入队列入队列Status EnQueue(SqQueue &Q, ElemType e) if (Q.rear+1)% MAXQSIZE=Q.front) return ERROR; Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE;

37、return OK;n3.出队列出队列Status DeQueue(SqQueue &Q,ElemType &e) if (Q.rear=Q.front) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1)%MAXQSIZE; return OK;3.5 队列应用队列应用n1.判断一个字符序列是否是回文。判断一个字符序列是否是回文。n基本思想：基本思想：n将输入字符逐个分别存入队列和栈，然后逐个将输入字符逐个分别存入队列和栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，符是