第3章_栈和队列A

1、1数据结构课程的内容数据结构课程的内容23.1 栈栈（Stack） 第三章第三章 栈和队列栈和队列3.2 队列队列（Queue）1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式1. 定义定义2. 逻辑结构逻辑结构3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式31. 定义定义3.1 栈栈与同线性表相同，仍为一对一关系与同线性表相同，仍为一对一关系。用用顺序栈顺序栈或或链栈链栈存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见只能在只能在栈顶栈顶运算，且访问结点时依照运算，且访问结点时依照后进先出后进先出（LIFOLIFO

2、）或先进后出或先进后出（FILOFILO）的原则。的原则。关键是编写关键是编写入栈入栈和和出栈出栈函数，具体实现依顺函数，具体实现依顺序栈或链栈的不同而不同。序栈或链栈的不同而不同。基本操作有入栈、出栈、读栈顶元素值、建基本操作有入栈、出栈、读栈顶元素值、建栈、或判断栈满、栈空等。栈、或判断栈满、栈空等。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式 2. 逻辑结构逻辑结构限定只能在限定只能在表的一端表的一端进行插入和删除运算的进行插入和删除运算的线性表线性表（只能在（只能在栈顶栈顶操作）操作）4问：堆栈是什么？它与一般线性表有什么不同？问：堆栈是什么？它与一般线性表有什么

3、不同？3.1 栈栈答：答：堆栈是一种特殊的线性表，它只能在堆栈是一种特殊的线性表，它只能在表的一端表的一端（即栈顶）（即栈顶）进行插入和删除运算。进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。与一般线性表的区别：仅在于运算规则不同。一般线性表一般线性表 堆栈堆栈逻辑结构：一对一逻辑结构：一对一 逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序表、链表 存储结构：顺序栈、链栈存储结构：顺序栈、链栈运算规则：随机存取运算规则：随机存取 运算规则：运算规则：后进先出后进先出(LIFO)“进进” 压入压入=PUSH（x)“出出” 弹出弹出=POP ( y )5栈栈

4、是仅在是仅在表尾表尾进行插入、删除操作的线性表。进行插入、删除操作的线性表。表尾表尾(即即 an 端端)称为称为栈顶栈顶 top ; 表头表头(即即 a1 端端)称为称为栈底栈底base例如：例如： 栈栈 s= (a1 , a2 , a3 , .,an-1 , an ) a1 称为称为 栈底元素栈底元素 an 称为称为 栈顶元素栈顶元素插入元素到插入元素到栈顶栈顶（即表尾）的操作，称为（即表尾）的操作，称为入栈入栈。从从栈顶栈顶（即表尾）删除最后一个元素的操作，称为（即表尾）删除最后一个元素的操作，称为出栈出栈。教材教材P44P44对对栈栈有更详细定义：有更详细定义：强调：强调：插入和删除都只

5、能在表的一端（栈顶）进行！插入和删除都只能在表的一端（栈顶）进行！6顺序栈示意图顺序栈示意图s a1 a2 a3data a4(栈底栈底)(栈顶栈顶)99.3210top7 a1 a2 an顺序栈顺序栈S ai表和栈的操作区别表和栈的操作区别对线性表对线性表 s= (a1 , a2 , . , an-1 , an )表头表头表尾表尾栈底栈底base栈顶栈顶top低地址低地址高地址高地址写入：写入：vi= ai读出：读出： x= vi压入：压入：PUSH (an+1)弹出：弹出： POP (x)前提：前提：一定要一定要预设预设栈顶指针栈顶指针top！低地址低地址高地址高地址vi a1 a2 ai

6、 an 顺序表顺序表Vn an+18入栈操作入栈操作例如用堆栈存放（例如用堆栈存放（A A，B B，C C，D D） （注意要遵循（注意要遵循“后进先出后进先出” ” 原则）原则）AACBABAtop核心语句：核心语句：top=L; 顺序栈中的顺序栈中的PUSHPUSH函数函数status Push(ElemType x) if(topM)上溢 else vtop+top+=x;Push (B);Push (C);Push (D);toptoptoptop低地址低地址LPush (A);高地址高地址MBCD9 出栈操作出栈操作例如从栈中取出例如从栈中取出BB （注意要遵循（注意要遵循“后进先出

7、后进先出” ” 原则）原则）DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址MD核心语句：核心语句：Pop ( );Pop ( );Printf( Pop () );顺序栈中的顺序栈中的POPPOP函数函数status Pop( )status Pop( ) if(top=L) if(top=L) 下溢下溢 else y=velse y=v-top-top; ; return(y); return(y); 10例例1：一个栈的输入序列是一个栈的输入序列是12345，若在入栈的过，若在入栈的过程中允许出栈程中允许出栈，则栈的输出序列则栈的输出序列43512可能实

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

9、可能得到的出栈序列是入栈的过程中允许出栈，则可能得到的出栈序列是什么？什么？答：答： 可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入入3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合计有合计有5

10、 5种可能性。种可能性。12例例4：计算机系计算机系2001年考研题（程序设计基础）年考研题（程序设计基础）设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：则可得到出栈的元素序列是： A、D可以可以（ B、C不行）。不行）。讨论：有无通用的判别原则？讨论：有无通用的判别原则？有。在可能的输出序列中，不存在这样的输入序列有。在可能的输出序列中，不存在这样的输入序列i i，j j，k k，能同时满足，能同时满足 ijk ijk 和和 PjPkPjPkPidata=x; p-link=st; st=p; S Status pop( ) pop( )

11、if(st if(st=NULL)=NULL)下溢下溢 elsey=stelsey=st-data;p=-data;p=stst; ;st=stst=st-link;-link; free(p); return(free(p); return(y y);); 链栈链栈入栈入栈函数函数链栈链栈出栈出栈函数函数插入插入表头表头从表头从表头删除删除17说说 明明18问：为什么要设计堆栈？它有什么独特用途？问：为什么要设计堆栈？它有什么独特用途？1. 调用函数或子程序非它莫属；调用函数或子程序非它莫属；2. 递归运算的有力工具；递归运算的有力工具；3. 用于保护现场和恢复现场；用于保护现场和恢复现场；

12、4. 简化了程序设计的问题简化了程序设计的问题。答：答：19 数制转换（十转数制转换（十转N） P48 设计思路：用栈暂存低位值设计思路：用栈暂存低位值例例2：括号匹配的检验括号匹配的检验P49 设计思路：用栈暂存左括号设计思路：用栈暂存左括号例例3 ：表达式求值表达式求值 -P52 设计思路：用栈暂存运算符设计思路：用栈暂存运算符例例4：汉诺仪（汉诺仪（Hanoi）塔）塔-P55 设计思路：用栈实现递归调用设计思路：用栈实现递归调用例例1：20例例3 表达式求值表达式求值 ( 这是栈应用的典型例子这是栈应用的典型例子 ) 这里，这里，表达式求值的算法是表达式求值的算法是 “算符优先法算符优先

13、法”。例如：例如：3*（7 2 ） （1）要正确求值，首先了解算术四则运算的规则：）要正确求值，首先了解算术四则运算的规则： a. 从左算到右从左算到右 b. 先乘除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外 由此，此表达式的计算顺序为：由此，此表达式的计算顺序为： 3*（7 2 ）= 3 * 5 = 1521（2）根据上述三条运算规则，在运算的每一步中，对）根据上述三条运算规则，在运算的每一步中，对任意相继出现的算符任意相继出现的算符 1和和 2 ，都要比较优先权关系。，都要比较优先权关系。算符优先法所依据的算符间的优先关系算符优先法所依据的算符间的优先关系见教材见教

14、材P53表表3.1 （是提供给计算机用的表！）（是提供给计算机用的表！）由表可看出，右括号由表可看出，右括号 ) 和井号和井号 # 作为作为 2时时级别最低；级别最低； 由由c 规则规则得出：得出： * ，/， + ，-为为 1时的优先权低于时的优先权低于（，高于，高于） 由由a规则规则得出：得出：（=） 表明括号内运算，已算表明括号内运算，已算完。完。 # = # 表明表达式求值完毕。表明表达式求值完毕。栈的应用（表达式求值）栈的应用（表达式求值）22（3）算法思想：）算法思想： 设定两栈：设定两栈：操作符栈操作符栈 OPTR ，操作数栈，操作数栈 OPND 栈初始化栈初始化：设操作数栈：设

15、操作数栈 OPND 为空；操作符栈为空；操作符栈 OPTR 的栈的栈底元素为表达式起始符底元素为表达式起始符 #； 依次读入字符依次读入字符：是操作数则入：是操作数则入OPND栈，是操作符则要判断：栈，是操作符则要判断： if 操作符操作符 栈顶元素栈顶元素，压入，压入OPTR栈。栈。栈的应用（表达式求值）栈的应用（表达式求值）23栈的应用（表达式求值）栈的应用（表达式求值）OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*

16、,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)24Status EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR);Push(OPTR ,#);c=getchar(); while(c!=#)&(GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c);

17、c=getchar(); else switch(compare(c,GetTop(OPTR) case : Push(OPTR , c); c=getchar();break; case =: Pop(OPTR);c=getchar();break; case 1 时时, 则则设法将设法将 前前 n 1 个盘子个盘子 借助借助 z ，从，从 x 移移到到 y 柱上，把柱上，把 盘子盘子 n 从从 x 移到移到 z 柱上；柱上； 把把n 1 个盘子个盘子 从从 y 移到移到 z 柱上。柱上。x y zx y znn 126Void Hanoi ( int n, char x, char y, char z ) /将将 n 个个 编号从上到下为编号从上到下为 1n 的盘子从的盘子从 x 柱，借助柱，借助 y 柱移到柱移到 z 柱柱 if ( n = = 1 ) move ( x , 1 , z ) ; /将编号为将编号