数据结构——栈与队列.ppt

1、3 栈与队列,栈与队列,2/132,主要内容,栈 栈的应用 队列 队列的应用,栈与队列,3/132,栈与队列,栈和队列是在程序设计中被广泛使用的两种线性数据结构。 与线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。,栈与队列,4/132,栈,栈：限定仅只能在末端进行插入和删除的线性表。 栈顶：允许插入和删除的一端。 栈底：不允许插入和删除的一端。 时间有序表：先进后出（FILO) /后进先出（LIFO）,栈与队列,5/132,栈的基本操作, clear()清空栈。 isEmpty()判断栈是否为空。 push(el)将元素el放到栈的顶部。 pop()取出栈顶部

2、的元素。 topEl()获取栈顶部的元素，但不删除该元素。,栈与队列,6/132,栈顶指针top,指向实际栈顶 后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,设数组大小为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow),栈空,栈与队列,7/132,栈的表示和实现,顺序方式 链式方式,栈与队列,8/132,顺序表示的栈的实现,top,空栈: top = -1 MaxTop = = 4,3,1,2,0,栈与队列,9/132,栈的初始化操作,0 1 2 MaxTop-1,top,template Stack:Sta

3、ck(int MaxStackSize) MaxTop=MaxStackSize-1; stack=new TMaxStackSize; top=-1; ,栈与队列,10/132,进栈操作,0 1 2 maxSize-1,top,b,a,0 1 2 maxSize-1,top,b,a,c,template Stack ,栈与队列,11/132,出栈操作,template Stack ,0 1 2 maxSize-1,top,b,a,c,栈与队列,12/132,两个栈共享栈空间,-,-,0,MaxTop-1,b0,t0,t1,b1,该空间的两端分别设为两个栈的栈底，用b0(=-1)和b1(=Ma

4、xTop)指示。让两个栈的栈顶t0和t1都向中间伸展，直到两个栈的栈顶相遇，才认为发生了溢出。,栈与队列,13/132,链式栈,data link,栈顶,栈底,top,top,初始化,栈与队列,14/132,链式表示的栈的实现,data link,栈顶,栈底,top,top,初始化,template class Node friend class LinkedStack ; private: T data; Node * link; ,栈与队列,15/132,链式栈的进栈操作,template LinkedStack ,data link,栈与队列,16/132,data link,top,x

5、 = A,template LinkedStack ,链式栈的出栈操作,栈与队列,17/132,链式栈的清空操作,template void LinkedStack:MakeEmpty() /同析构函数 Node *next; while(top) next=top-link; delete top; top=next; ,栈与队列,18/132,栈的应用,数制转换 括号匹配 回文游戏 表达式计算 计算中缀表带式的值 中缀、后缀表达式转换 匹配程序分隔符 大数加法（乘法） 递归,栈与队列,19/132,将一个非负十进制整数转换成八进制数并输出。 例 把十进制数159转换成八进制数。,数制转换,

6、栈与队列,20/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,匹配情况：左括号4 右括号8 左括号1 右括号11,算法：从左向右扫描字符串， (1)如果是左括号，就把它的位置编码压入栈中 (2)如果是右括号，则与栈顶的位置编码所指的左括号匹配。,栈与队列,21/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,栈与队列,22/132,括号匹配,匹配一个字符串中的左、右括号。如 (

7、a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,栈与队列,23/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,栈与队列,24/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,4,栈与队列,25/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6

8、7 8 9 10 11,1,4,栈与队列,26/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,4,栈与队列,27/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,4,栈与队列,28/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,4,8 4 匹配,栈与队列,29/13

9、2,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,8 4 匹配,栈与队列,30/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,8 4 匹配,栈与队列,31/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,8 4 匹配,栈与队列,32/132,括号匹配,匹配一个字符串中的左、

10、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,1,8 4 匹配,11 1 匹配,栈与队列,33/132,括号匹配,匹配一个字符串中的左、右括号。如 ( a * ( b + c ) + d ),字符位置 1 2 3 4 5 6 7 8 9 10 11,8 4 匹配,11 1 匹配,栈与队列,34/132,算法思想： 读入字符串； 去掉空格（原串）； 压入栈； 原串字符与出栈字符依次比较； 若不等，非回文； 若直到栈空都相等，回文。,回文游戏（顺读与逆读字符串一样（不含空格）,栈与队列,35/132,表达式计算,表达式都由操作数（

11、也称运算对象）、操作符（也成运算符）和分界符组成。 算术表达式三种表示： （1）中缀(infix)表示： 例如A+B （2）前缀(prefix)表示： 例如+ AB （3）后缀(postfix)表示： 例如AB +,栈与队列,36/132,中缀表示,平时所用的表达式都是中缀表示。如 A+B*(C-D)-E/F 中缀表示中有操作符的优先级问题，并可以加括号改变运算顺序。 用中缀表示求解表达式的值需要利用两个栈来实现，一个暂存操作数，另一个暂存操作符。,栈与队列,37/132,计算中缀表达式算法思想,设置两个工作栈 运算符栈OPTR，运算符栈的栈底为表达式的起始符#。 操作数栈OPND，操作数栈为

12、空栈。,栈与队列,38/132,计算中缀表达式算法思想,设isp(.)代表栈内优先级,icp(.)代表栈外优先级 依次读入表达式中的每个字符,若是 操作数,则进OPND栈； 运算符s1，则和OPTR中的栈顶元素s2做比较再操作。 若icp(s1)isp(s2)，则运算符入栈； 若icp(s1)isp(s2)，则从OPND栈顶弹出两个操作数，与OPTR中的栈顶元素做运算，并将运算结果入OPND； 若icp(s1)=isp(s2)，则OPTR中的栈顶元素出栈。 直至表达式扫描完毕。,栈与队列,39/132,各个算术操作符的优先级,操作符#(*,/,% +,- ),isp01 7 5 3 8,icp

13、0 8 6 4 2 1,栈与队列,40/132,如： x = 3 (7-2);,OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,计算中缀表达式的值,栈与队列,41/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,计算中缀表达式的值,栈与队列,42/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,计算中缀表达式的值,栈与队列,43/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,计算中缀表达式的值,栈与队列,44/1

14、32,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,计算中缀表达式的值,栈与队列,45/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,计算中缀表达式的值,栈与队列,46/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,计算中缀表达式的值,栈与队列,47/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,7,计算中缀表达式的值,栈与队列,48/132,如： x = 3

15、(7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,7,计算中缀表达式的值,栈与队列,49/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,7,-,计算中缀表达式的值,栈与队列,50/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,7,-,2,计算中缀表达式的值,栈与队列,51/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,7,-,2,计算中缀表达式的值,栈与队列,52/132,如：

16、x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,7,-,2,),计算中缀表达式的值,栈与队列,53/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,5,-,),计算中缀表达式的值,栈与队列,54/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,5,),计算中缀表达式的值,栈与队列,55/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,5,),计算中缀表达式的值,栈与队列,

17、56/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,(,5,),计算中缀表达式的值,栈与队列,57/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,5,计算中缀表达式的值,栈与队列,58/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,5,计算中缀表达式的值,栈与队列,59/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,3,5,#,计算中缀表达式的值,栈与队列,60/132

18、,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,15,#,计算中缀表达式的值,栈与队列,61/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,15,#,计算中缀表达式的值,栈与队列,62/132,如： x = 3 (7-2),OPND栈,OPTR栈,执行过程：# 3 (7-2) #,#,15,#,计算中缀表达式的值,栈与队列,63/132,后缀表达式,后缀表示也叫做 RPN或逆波兰记号，参加运算的操作数总在操作符前面。 利用后缀表示求解表达式的值时，从左向右顺序地扫描表达式。 后缀表达式中不出现括

19、号。 后缀表达式例子: 3 7 2 - * 10 +,栈与队列,64/132,后缀表达式计算,顺序扫描表达式的每一项， 操作数，压入栈中； 操作符，连续从栈中退出两个操作数Y 和X，形成运算指令 XY,并将结果重新压入栈中。 当扫描完表达式后，栈顶存放的就是计算结果。,栈与队列,65/132,计算后缀表达式的值,A B C D - * + E F / - R1 R4 R2 R3 R5 等价于：A+B*(C-D)-E/F,用后缀表达式计算的步骤,步 扫描项项类型动作 栈中内容,1 置空栈 空,2Aoperand进栈 A,3Boperand进栈 A B,4Coperand进栈 A B C,5Dop

20、erand进栈 A B C D,6-operator D和C退栈,计算C-D,结果R1进栈 A B R1,7*operand R1和B退栈,计算B*R1,结果R2进栈 A R2,8 + operand R2和A退栈,计算A+R2,结果R3进栈 R3,9 E operand进栈 R3 E,10 F operand进栈 R3 E F,11 / operand F和E退栈,计算E/F,结果R4进栈 R3 R4,12 - operand R4和R3退栈,计算R3-R4,结果R5进栈 R5,A B C D - * + E F / -,栈与队列,67/132,中缀向后缀转换,扫描中缀表达式， 操作数直接输

21、出； 操作符放到(操作符)栈中。 如：A+B*(C-D)-E/F 应转换为 ABCD-*+EF/-,算法过程?,栈与队列,68/132,a=b+(c-d)*(e-f); g10=h i9 +(j+k)*l; while( m(n8+o) ) p=7; /* initialize p */ r=6; ,更多：匹配程序中的分隔符, 在程序中匹配分隔符 分隔符：圆括号( ); 方括号 ; 花括号 ; 注释分隔符/* */.,特大数加法（乘法）,4376,592 + 3784,Operand- Stack1,Operand- Stack2,result- Stack,5,9,2,3,7,8,4,栈与队

22、列,70/132,栈与递归,概念 例子 演示 递归与循环,栈与队列,71/132,栈与递归,函数调用与递归实现 每个函数（包括主函数main()）的状态的决定因素: 函数中所有自动变量的内容 函数参数的值 返回地址 包含这些信息的数据区称为活动记录或者栈结构，它是在运行栈上分配空间的。,栈与队列,72/132,栈与递归,活动记录通常包含以下信息： 函数所有参数的值； 可以存储在其他地方的局部变量（自动变量），活动记录只包含它们的描述符和指向存放它们的位置的指针。 回到调用程序的返回地址，即在调用完成之后紧接着此函数调用指令之后的指令的地址。 一个指向调用程序的活动记录的动态链接指针。 非voi

23、d类型的函数的返回值。,栈与队列,73/132,main(),f1(),f2(),f3(),栈与队列,74/132,栈与递归实例,递归调用的剖析 定义一个数x的非负整数n次幂的函数是递归函数的一个很好的例子。这个函数最直接的定义是： 可以直接根据幂的定义写出计算xn的C+函数： /*102*/ double power (double x, unsigned int n) /*103*/ if (n=0) /*104*/ return 1.0; /else /*105*/ return x*power (x,n-1);,栈与队列,75/132,栈与递归,使用这个定义，x4的值可以按照下面的方式

24、计算：,栈与队列,76/132,栈与递归,或者表示为下面的形式：,栈与队列,77/132,栈与递归实例2,函数power()通过以下语句在主函数main()中调用： int main() /*136*/ y=power(5.6, 2) ,栈与队列,78/132,栈与递归实例2,递归调用的追踪： 第1次调用 power(5.6, 2) 第2次调用 power(5.6, 1) 第3次调用 power(5.6, 0) 第3次调用 1 第2次调用 5.6 第1次调用 31.36,栈与队列,79/132,对power()的 第三次调用,对power()的 第二次调用,对power()的 第一次调用,Ma

25、in()的 活动记录,注：SP 栈指针 AR 活动记录 ？ 为返回值保留的位置,/*102*/ double power (double x, unsigned int n) /*103*/ if (n=0) /*104*/ return 1.0; /else /*105*/ return x*power (x,n-1);,int main() /*136*/ y=power(5.6, 2) ,栈与递归演示,栈与队列,80/132,对power()的 第三次调用,对power()的 第二次调用,对power()的 第一次调用,Main()的 活动记录,注：SP 栈指针 AR 活动记录 ？ 为返

26、回值保留的位置,/*102*/ double power (double x, unsigned int n) /*103*/ if (n=0) /*104*/ return 1.0; /else /*105*/ return x*power (x,n-1);,int main() /*136*/ y=power(5.6, 2) ,栈与递归演示,栈与队列,81/132,对power()的 第三次调用,对power()的 第二次调用,对power()的 第一次调用,Main()的 活动记录,注：SP 栈指针 AR 活动记录 ？ 为返回值保留的位置,/*102*/ double power (do

27、uble x, unsigned int n) /*103*/ if (n=0) /*104*/ return 1.0; /else /*105*/ return x*power (x,n-1);,int main() /*136*/ y=power(5.6, 2) ,栈与递归演示,栈与队列,82/132,对power()的 第三次调用,对power()的 第二次调用,对power()的 第一次调用,Main()的 活动记录,注：SP 栈指针 AR 活动记录 ？ 为返回值保留的位置,/*102*/ double power (double x, unsigned int n) /*103*/

28、if (n=0) /*104*/ return 1.0; /else /*105*/ return x*power (x,n-1);,int main() /*136*/ y=power(5.6, 2) ,栈与递归演示,栈与队列,83/132,对power()的 第三次调用,对power()的 第二次调用,对power()的 第一次调用,Main()的 活动记录,注：SP 栈指针 AR 活动记录 ？ 为返回值保留的位置,/*102*/ double power (double x, unsigned int n) /*103*/ if (n=0) /*104*/ return 1.0; /el

29、se /*105*/ return x*power (x,n-1);,int main() /*136*/ y=power(5.6, 2) ,栈与递归演示,栈与队列,84/132,对power()的 第三次调用,对power()的 第二次调用,对power()的 第一次调用,Main()的 活动记录,注：SP 栈指针 AR 活动记录 ？ 为返回值保留的位置,/*102*/ double power (double x, unsigned int n) /*103*/ if (n=0) /*104*/ return 1.0; /else /*105*/ return x*power (x,n-1

30、);,int main() /*136*/ y=power(5.6, 2) ,栈与递归演示,栈与队列,85/132,对power()的 第三次调用,对power()的 第二次调用,对power()的 第一次调用,Main()的 活动记录,注：SP 栈指针 AR 活动记录 ？ 为返回值保留的位置,/*102*/ double power (double x, unsigned int n) /*103*/ if (n=0) /*104*/ return 1.0; /else /*105*/ return x*power (x,n-1);,int main() /*136*/ y=power(5.

31、6, 2) ,栈与递归演示,栈与队列,86/132,有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘； 圆盘可在三个塔座上任意移动； 任何时刻，每个塔座上不能将大盘压到小盘上。,Tower of Hanoi问题,解决方法： n=1时，直接把圆盘从A移到C。 n1时 把上面n-1个圆盘从A移到B 然后将n号盘从A移到C 将n-1个盘从B移到C。 即把解n个圆盘的Hanoi问题转化为解n-1个圆盘的Hanoi问题,依次,直至转化成只有一个圆盘的Hanoi问题。,栈与

32、队列,88/132,递归与循环,递归函数可以使用循环来实现。 函数Power()可以用另一种方法来实现： double nonRecPower(double x, unsigned int n) double result=1; for(result=x;n1;-n) result*=x; return result; ,栈与队列,89/132,尾部递归,尾部递归的特点 在每个函数的实现的末尾只使用一个递归调用 例如： void tail(int i) if(i0) couti ; tail(i-1); ,栈与队列,90/132,尾部递归,尾部递归只是一个变形的循环 void iterativ

33、eTail(int i) for(; i0;i-) couti“ ”; ,栈与队列,91/132,非尾部递归,例如：将输入行以相反的顺序打印出来。 void reverse() char ch; cin.get(ch); if(ch!=n) reverse(); cout.put(ch); ,栈与队列,92/132,非尾部递归,非尾部递归转换成非递归： 非尾部递归转化为迭代形式需要对栈进行显示处理。 void nonRecursiveReverse() int ch; cin.get(ch); while(ch!=n) st.push(ch); /st是一个全局栈对象 cin.get(ch);

34、 while(!st.empty() cout.put(st.pop(); ,栈与队列,93/132,递归过程改为非递归过程,递归过程简洁、易编、易懂； 递归过程效率低，重复计算多； 改为非递归过程的目的是提高效率； 单向递归和尾递归可直接用迭代实现其非递归过程； 其他情形必须借助栈实现非递归过程。,栈与队列,94/132,队列,先进先出（first in/first out, FIFO）线性结构。 队首：删除端 队尾：插入端,栈与队列,95/132,队列操作,clear（） 清空队列。 isEmpty（） 判断队列是否为空。 enqueue（el） 队列的尾部加入元素el。 dequeue（

35、） 取出队列的第一个元素。 firstEl（） 返回队列的第一个元素，但不移去它。,栈与队列,96/132,队列,顺序方式表示和实现 链式方式表示和实现 循环队列 队列的应用,栈与队列,97/132,队列的顺序表示1,用数组queueMaxSize描述一个队列， location(i)=i-1;,队空：front=0; rear=-1;,插入A元素： front=0; rear=0;,插入B元素： front=0; rear=1;,栈与队列,98/132,队列的顺序表示1,A,B,C,D,队列满： rear=MaxSize-1,出队， front=1;,插入E： rear=MaxSize-1;

36、 队列满，不能插入,假溢出!空间浪费！,栈与队列,99/132,队列的顺序表示1,A,B,C,D,队列满： rear=MaxSize-1,B,C,D,出队， front=1;,B,C,D,出队后调整： front=0; rear=rear-1;,浪费 时间!,栈与队列,100/132,队列假溢出解决方案,循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0; 入队： rear=(rear+1)%M; sqrear=x; 出队： front=(front+1)%M; x=sqfront;,栈与队列,101/132,解决方案： 1.另外设一个标志以区别队空、队满 2.少用