数据结构(三)栈和队列课件

1、第三章 栈和队列3.1 栈 3.1.1 栈的定义 3.1.2 栈的表示和实现3.2 栈的应用举例 3.1 栈3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。因此，栈的修改是按后进先出的原则进行的，所以，栈称为后进先出（先进后出）表（LIFO，FILO）。3.1.2 顺序存储栈 栈是线性表的特例，因此线性表的

2、存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top（栈顶指针）来指出栈顶。栈顶 栈底例、一叠盘子、弹夹等。 anan-1.a2a1入出-1 空栈top016 为指示当前栈顶的位置，需top为栈顶指针（ MAXSIZE代表栈容量）。初始化:x进栈：退栈：top=-1;if(top= =MAXSIZE-1 上溢处理； else top+; stacktop=x;if(top=-1) 下溢处理； else y=stacktop; top-;

3、3.1.3 链栈 栈的链式存储结构称为链栈，插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。 初始化：top=NULLX进栈：p= new StackNode;p-data=x; p-next=top;top=p;退栈:if(top = = NULL) 下溢处理；else y= top-data; p=top;top=p-next;delete p; top3.2.2 括号匹配的检验假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或 （）)均为不正确的格式。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否

4、则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。3.2.3 行编辑程序 在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 3.2.4 迷宫求解 if(

5、栈不空&栈顶位置尚有其他方向未被探索) 新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；if(栈不空&栈顶位置的四周均不可通)则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；3.2.5 表达式求解 表达式的三种标识方法：设 exp = S1 OP S2则称 OP S1 S2 为前缀表示法 S1 OP S2 为中缀表示法 S1 S2 OP 为后缀表示法 例如: exp = a b + (c d / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e

6、 / f + 结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;例如: exp = a b + (c d / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e / f + 结论:3）中缀式丢失了括弧信息， 致使运算的次序不确定;例如: exp = a b + (c d / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e / f + 结论:4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;例如: exp

7、= a b + (c d / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e / f + 结论:5)后缀式的运算规则为: 运算符在式中出现的顺序恰为 表达式的运算顺序; 每个运算符和在它之前出现 且 紧靠它的两个操作数构成一个最小 表达式。如何从后缀式求值？先找运算符，再找操作数例如： a b c d e / f +abd/ec-d/e(c-d/e)fa b+ (c-d/e)f如何从原表达式求得后缀式？ 每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析 “原表达式” 和

8、 “后缀式”中的运算符:原表达式: a + b c d / e f 后缀式: a b c + d e / f 从原表达式求得后缀式的规律为：1) 设立运算符栈2) 设表达式的结束符为“#”， 预设运算符栈的栈底为“#”3) 若当前字符是操作数，则直接发送给后缀式4) 若当前运算符的优先数高于栈顶运算符，则进栈5) 否则，退出栈顶运算符发送给后缀式； 7) 遇表达式结束“#” ，连续将栈中运算符退到后缀式。6) “(” 对它之前后的运算符起隔离作用，可理解为优先级最低的运算符号，进栈；“)”可视为自相应左括弧开始的表达式的结束符。一直退到栈顶是“(”（符号送后缀式），最后“（”退栈。a b +

9、(c d / e) f #栈后缀表达式：a b + (c d / e) f #栈后缀表达式：a b + (c d / e) f #a后缀表达式：栈a b + (c d / e) f #a后缀表达式：栈a b + (c d / e) f #a后缀表达式：栈a b + (c d / e) f #ab后缀表达式：栈a b + (c d / e) f #ab后缀表达式：栈a b + (c d / e) f #ab后缀表达式：栈a b + (c d / e) f #ab后缀表达式：栈a b + (c d / e) f #a+b后缀表达式：栈a b + (c d / e) f #a+b后缀表达式：栈a b

10、 + (c d / e) f #栈a+b（后缀表达式：a b + (c d / e) f #栈a+b（后缀表达式：a b + (c d / e) f #栈a+b（c后缀表达式：a b + (c d / e) f #a+b（c后缀表达式：栈a b + (c d / e) f #a+b（c后缀表达式：栈a b + (c d / e) f #a+b（c后缀表达式：栈a b + (c d / e) f #a+b（cd后缀表达式：栈a b + (c d / e) f #a+b（cd后缀表达式：栈a b + (c d / e) f #a+b（cd/后缀表达式：栈a b + (c d / e) f #a+b

11、（cd/后缀表达式：栈a b + (c d / e) f #a+b（cd/e后缀表达式：栈a b + (c d / e) f #a+b（cd/e后缀表达式：栈a b + (c d / e) f #a+b（cde后缀表达式：栈a b + (c d / e) f #a+b（cde/后缀表达式：栈a b + (c d / e) f #a+b（cde/后缀表达式：栈a b + (c d / e) f #a+bcde/后缀表达式：栈a b + (c d / e) f #a+bcde/后缀表达式：栈a b + (c d / e) f #a+bcde/后缀表达式：栈a b + (c d / e) f #a+

12、bcde/后缀表达式：栈a b + (c d / e) f #a+bcde/f后缀表达式：栈a b + (c d / e) f #栈a+bcde/f后缀表达式：a b + (c d / e) f #栈a+bcde/f后缀表达式：a b + (c d / e) f #栈abcde/f+后缀表达式：a b + (c d / e) f #栈abcde/f+后缀表达式：第二种实现: 用两个栈 运算符栈 操作数栈 已知操作符包括+，-，*，/，（和），将中缀表达式a+b-a*(c+d)/e-f)+g转化为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定的运算次序的操作符，若栈初

13、始时为空，则转换过程中同时保存在栈中的操作符的最大个数是A. 5 B. 7 C. 8 D. 112012年试题（2分）3.2.6、实现递归将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。 当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回 ！例如：void main( ) void

14、a( ) void b( ) a( ); b( ); /main / a / bmain的数据区函数a的数据区函数b的数据区3.3 队列3.3.1 队列的定义 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队

15、列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。出队入队队头队尾front=rear=-1front=-1 ,rear=2 (a)队列初始为空（b）a,b,c入队3.3.2 循环队列队列的顺序表示和实现 队列的顺序存储结构称为顺序队列，用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针分别指示队头和队尾元素在队列中的位置，它们的初始值在队列初始化时均应置为-1。入队时将新元素插入所指的位置，然后加。出队时，删去所指的元素，然后加并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头前一个位置，

16、而尾指针始终指向队尾元素的实际位置。 0 1 2 3 0 1 2 3abc ( c) a出队 (d) b,c出队，队为空bcrearfrontrearfront 为充分利用向量空间。克服上述现象，把向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MaxSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： if(i+1=MaxSize) i=0; else i+; 利用模运算可简化为： i=(i+

17、1)%MaxSizen-10 显然，因为循环队列元素的空间可以全被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。 入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。 开始：front=rear=032107528连续加入2，5，7，8后front=rear=0rearfront3210 显然，因为循环队列元素的空间可以全被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队

18、列。 入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。 解决此问题的方法至少有三种： 其一:另设一个布尔变量以区分队列的空和满； 其二:少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满；（但此时实际还有一个空位置）其三 :是使用一个计数器记录队列中元素的总数 （实际上是队列长度）。752连续加入2，5，7后，再要加入8，溢出rearfront3210752连续删除三次rearfront3210752连续删除三次rearfront3210752连续删

19、除三次rearfront3210752连续删除三次rear3210front752连续删除三次再删除，由于front等于rear,下溢rearfront3210（1）置空队front=rear=0;/0到MaxSize-1中任意数都可以if(rear+1) % MaxSize= = front) 队满处理； else rear=(rear+1)%MaxSize; queuerear=x; （2）x进队（3）退队if(front = = rear ) 队空处理； else front=(front+1)%MaxSize; y=queuefront;3.3.3 链队列 链式存储结构作为为链队列，它

20、是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。初始化：rear=front=new Node; rear-next=NULL;x进队：r=new Node; r-data=x; r-next=NULL; rear-next=r;rear=r;退队：if(front = rear) 队空处理；else p=front-next;y=p-data;front-next=p-next;delete p; if(front-next= =NULL) rear=front;frontrear习题1、一个连续空间，两个栈共

21、享，其组织方式为底固定在两端，如图： 试写出（1）栈初始化 （2）push(x,i) (3)pop(y,i) 其中，i为栈号(i=1,2),x是进栈元素，退栈元素放在y中。0n-1top0top12、设元素e1、e2、e3、e4、e5、e6依此通过栈S，得到的序列是e2、e4、e3、e6、e5、e1，若用I代表进栈，O代表出栈，写出操作步骤。（比如IOIIOO得到的序列是e1e3e2)。3、设栈和队列Q的初始状态为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g,则栈的容量至少是) B) 2 C)3 D)4 (2009年研究生入学考试题）4、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据