数据结构 第三章 栈和队列

《数据结构 第三章 栈和队列》由会员分享，可在线阅读，更多相关《数据结构 第三章 栈和队列（45页珍藏版）》请在金锄头文库上搜索。

1、1,数据结构课程的内容,2,3.1 栈（Stack）,第三章 栈和队列,3.2 队列（Queue）,1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式,1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式,3,1. 定义,3.1 栈,与线性表相同，仍为一对一关系。,用顺序栈或链栈存储均可，但以顺序栈更常见,只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。,关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同。,限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）,基本操作有入栈、出栈、读栈顶元素值

2、、建栈、或判断栈满、栈空等。,4,问：堆栈是什么？它与一般线性表有什么不同？,3.1 栈,答：堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。,一般线性表 堆栈 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO),“进” 压入=PUSH（x) “出” 弹出=POP ( y ),5,栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底base,例如： 栈 s= (a1 , a2 , a3

3、, .,an-1 , an ),a1 称为 栈底元素 an 称为 栈顶元素,插入元素到栈顶（即表尾）的操作，称为入栈。 从栈顶（即表尾）删除最后一个元素的操作，称为出栈。,教材P44对栈有更详细定义：,强调：插入和删除都只能在表的一端（栈顶）进行！,6,顺序栈示意图,7,表和栈的操作区别对线性表 s= (a1 , a2 , . , an-1 , an ),写入：vi= ai 读出： x= vi,压入：PUSH (an+1) 弹出： POP (x),前提：一定要预设栈顶指针top！,an+1,8,入栈操作例如用堆栈存放（A，B，C，D） （注意要遵循“后进先出” 原则）,A,A,C B A,B

4、A,核心语句： top=L;,顺序栈中的PUSH函数 status Push(ElemType x) if(topM)上溢else vtop+=x; ,Push (B);,Push (C);,Push (D);,低地址L,Push (A);,高地址M,B,C,D,9,出栈操作例如从栈中取出B （注意要遵循“后进先出” 原则）,核心语句： Pop ( ); Pop ( ); Printf( Pop () );,顺序栈中的POP函数 status Pop( ) if(top=L) 下溢 else y=v-top; return(y); ,10,例1：一个栈的输入序列是12345，若在入栈的过程中允

5、许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，只需压入一个立即弹出一个即可。,435612中到了12顺序不能实现；135426可以实现。,例2：如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？,答：,答：,11,例3（严题集3.1）一个栈的输入序列为123，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出， 即132； 1、2入，2出， 3入3出

6、， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性。,12,例4：计算机系2001年考研题（程序设计基础）,设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,A、D可以（ B、C不行）。,答：,13,补充1： 若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈；对于向上生成的栈 入栈口诀：堆栈指针top先压后加（vtop+=x）； 出栈口诀：堆栈指针top先减后弹（y=v-top) 。

7、,3.1 栈,补充2： 栈不存在的条件： base=NULL;栈为空 的条件 ： base=top;栈满的条件 ： top-base=stacksize;,14,补充3：链栈 链栈示意图,15,链栈的入栈函数、出栈函数 （以头指针为栈顶，在头指针处插入或删除！）,公共说明部分： typedef struct snodeSElemType data; struct snode *link; NODE; NODE *st, *p; int m=sizeof(NODE);,16,Push (SElemType x) p=(NODE*)malloc(m);if(!p)上溢 else p-data=x;

8、 p-link=st; st=p; ,Status pop( ) if(st=NULL)下溢 elsey=st-data;p=st;st=st-link; free(p); return(y);,链栈 入栈函数,链栈 出栈函数,插入表头,从表头删除,17, 链栈不必设头结点，因为栈顶（表头）操作频繁； 采用链栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。,说 明,18,问：为什么要设计堆栈？它有什么独特用途？,调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。,答：,19,数制转换（十转N）

9、 P48设计思路：用栈暂存低位值例2：括号匹配的检验P49设计思路：用栈暂存左括号例3 ：表达式求值 -P52设计思路：用栈暂存运算符例4：汉诺仪（Hanoi）塔-P55设计思路：用栈实现递归调用,例1：,20,例3 表达式求值 ( 这是栈应用的典型例子 )这里，表达式求值的算法是 “算符优先法”。,例如：3*（7 2 ）（1）要正确求值，首先了解算术四则运算的规则：a. 从左算到右b. 先乘除，后加减c. 先括号内，后括号外由此，此表达式的计算顺序为：3*（7 2 ）= 3 * 5 = 15,21,（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符1和2 ，都要比较优先权关系

10、。 算符优先法所依据的算符间的优先关系见教材P53表3.1（是提供给计算机用的表！） 由表可看出，右括号 ) 和井号 # 作为2时级别最低；由c 规则得出： * ，/， + ，-为1时的优先权低于（，高于）由a规则得出：（=） 表明括号内运算，已算完。 # = # 表明表达式求值完毕。,栈的应用（表达式求值）,22,（3）算法思想： 设定两栈：操作符栈 OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 #； 依次读入字符：是操作数则入OPND栈，是操作符则要判断：if 操作符 栈顶元素，压入OPTR栈。,栈的应用（表达式求值）,

11、23,栈的应用（表达式求值）,24,Status EvaluateExpression( OperandType /EvaluateExpression,25,例4 汉诺仪（ Hanoi）塔 传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。移动时的规则： 每次只能移动一个盘子；只能小盘子在大盘子上面；可以使用任一柱子。 当工作做完之后，就标志着世界末日到来。,分析：设三根柱子分别为 x，y, z , 盘子在 x 柱上，要移到 z 柱上。 1、当 n=1 时，盘子直接从 x 柱移到 z 柱上；

12、 2、当 n1 时, 则设法将 前 n 1 个盘子 借助 z ，从 x 移到 y 柱上，把 盘子 n 从 x 移到 z 柱上； 把n 1 个盘子 从 y 移到 z 柱上。,n,n 1,26,Void Hanoi ( int n, char x, char y, char z ) /将 n 个 编号从上到下为 1n 的盘子从 x 柱，借助 y 柱移到 z 柱 if ( n = = 1 ) move ( x , 1 , z ) ; /将编号为 1 的盘子从 x 柱移到 z 柱 else /将 n -1个 编号从上到下为1n-1的盘子从 x 柱，借助 z 柱移到 y 柱 Hanoi ( n-1 ,

13、x , z , y ) ; move ( x , n, z) ; /将编号为 n 的盘子从 x 柱移到 z 柱 /将 n -1个 编号从上到下为 1n-1的盘子从 y 柱，借助 x 柱移到 z 柱 Hanoi ( n-1 , y , x , z ); /Hanoi,27,定 义,3.2 队列,与同线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作有入队或出队，建空队列，判队空或队满等操作。,只能在表的一端进行插入运算，在表的另一端进行删除运

14、算的线性表 （头删尾插）,28,队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。表尾即 an 端，称为 队尾 ； 表头即 a1 端，称为队头。它是一种先进先出（）的线性表。,例如：队列 Q= (a1 , a2 , a3 , .,an-1 , an ),插入元素称为入队；删除元素称为出队。,队头,队尾,教材P59对队列有更详细定义：,队列的抽象数据类型定义见教材5960 队列的存储结构为链队或顺序队（常用循环顺序队）,29,链队列示意图,讨论： 空队列的特征？, 怎样实现入队和出队操作？ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-next=p-next;,完整动作设计参见教材P61-62, 队列会满吗？,front=rear,一般不会，因为删除时有free动作。除非内存不足！,30,顺序队示意图,(队尾),(队首), 队列会满吗？ 很可能会，因为数组前端空间无法释放。因此数组应当有长度限制。, 空队列的特征？约定：front=rear,队尾后地址,入队(尾部插入)：vrear=e; rear+; 出队(头部删除)：x=vfront; front+;,讨论：,假溢出,有缺陷, 怎样实现入队和出队操作？,3.2 队列,31,