数据结构第六次课-栈和队列Bppt课件

1、电气信息学院 计算机系数据结构每课一贴：原来很简单 有一个人去应征任务，随手将走廊上的纸屑捡起来，放进了渣滓桶，被路过的口试官看到了，因此他得到了这份任务。 原来获得赏识很简单，养成好习惯就可以了。 住在田边的青蛙对住在路边的青蛙说：他这里太危险，搬来跟我住吧！ 路边的青蛙说：我曾经习惯了，懒得搬了。 几天后，田边的青蛙去探望路边的青蛙，却发现他已被车子压死，暴尸在马路。 原来掌握命运的方法很简单，远离懒惰就可以了。电气信息学院 计算机系数据结构2. 逻辑构造逻辑构造 与同线性表一样，仍为一对一关系。与同线性表一样，仍为一对一关系。3. 运算规那么运算规那么 只能在栈顶运算，且访问结点时按照只

2、能在栈顶运算，且访问结点时按照后进先出后进先出 LIFO或先进后出或先进后出FILO的原那么。的原那么。4.出栈顺序：出栈顺序：定义定义 限定只能在表的一端进展插入和删除限定只能在表的一端进展插入和删除运算的运算的 线性表只能在栈顶操作线性表只能在栈顶操作上次课内容回想上次课内容回想电气信息学院 计算机系数据结构讨论：有无通用的判别原那么？讨论：有无通用的判别原那么？有。在能够的输出序列中，不存在这样的输入序列有。在能够的输出序列中，不存在这样的输入序列i，j，k，能同时满足入栈顺序，能同时满足入栈顺序i，j，k 和和 出栈顺序出栈顺序k ，i， j。例例4 4 一个栈的输入序列为一个栈的输入

3、序列为1234512345，假设在入栈的，假设在入栈的过程中允许出栈，那么能够得到的出栈序列有多过程中允许出栈，那么能够得到的出栈序列有多少种，分别是什么？少种，分别是什么？211nnCn 电气信息学院 计算机系数据结构例例1：回文游戏：回文游戏 设计思绪：用栈暂存回文设计思绪：用栈暂存回文例例2：数制转换十转：数制转换十转N 设计思绪：用栈暂存低位值设计思绪：用栈暂存低位值例例3 ：括号匹配的检验：括号匹配的检验 设计思绪：用栈暂存左括号设计思绪：用栈暂存左括号例例4：表达式求值：表达式求值 设计思绪：用栈暂存运算符设计思绪：用栈暂存运算符 简化程序设计问题简化程序设计问题电气信息学院 计算

4、机系数据结构v回文游戏：顺读与逆读字符串一样不含空格dadtop1.读入字符串2.压入栈3.原串字符与出栈字符依次比较 假设不等，非回文 假设直到栈空都相等，那么是回文有没有更简约的方法呢？(读入字符串，压入n/2个字符,n为字符个数)v多进制输出：字符串：“madam I madam“上海自来水来自海上例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732电气信息学院 计算机系数据结构v多进制输出：例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余

5、 3余 2toptop7top73top732public class Test public static void main(String args) int i=159; String binStr=Integer.toBinaryString(i); String otcStr=Integer.toOctalString(i); String hexStr=Integer.toHexString(i); System.out.println(binStr); 电气信息学院 计算机系数据结构v多进制输出：import java.util.*;class T public static v

6、oid main(String args) System.out.println(toOctal(159); public static String toOctal(int a) String str = ; Stack s = new Stack(); while(a!=0) s.push(a%8); a=a/8; while(!s.empty() str += s.pop(); return str; 例 把十进制数159转换成八进制数电气信息学院 计算机系数据结构例如：例如：3*7 2 (1) 要正确求值，首先了解算术四那么运算的规那要正确求值，首先了解算术四那么运算的规那么：么： a

7、. 从左算到右从左算到右 b. 先乘除，后加减先乘除，后加减 c. 先括号内，后括号外先括号内，后括号外 由此，通常此表达式的计算顺序为：由此，通常此表达式的计算顺序为： 3*7 2 = 3 * 5 = 15v 表达式求值( 这是栈运用的典型例子 )v 这里，表达式求值的算法是 “算符优先法。电气信息学院 计算机系数据结构表达式表示法表达式表示法 算术表达式中最常见的表示法方式有算术表达式中最常见的表示法方式有 中缀、前缀和中缀、前缀和 后缀表示法。中缀表示法是后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。示法主要用

8、于计算机科学领域。中缀表示法中缀表示法 Syntax: operand1 operator operand2Example: (A+B)*C-D/(E+F)前缀表示法前缀表示法 -波兰表示法波兰表示法Polish notation，PNSyntax : operator operand1 operand2Example : -*+ABC/D+EF后缀表示法后缀表示法 -逆波兰表示法逆波兰表示法Reverse Polish Notation，RPNSyntax : operand1 operand2 operatorExample : AB+C*DEF+/- 无操作符优先级问题，求值简无操作符优

9、先级问题，求值简单单电气信息学院 计算机系数据结构1. 中缀表达式到后缀表达式的转换 要把表达式从中缀表达式的方式转换成用后缀表示法表示的等价表达式，必需了解操作符的优先级和结合性。 优先级或者说操作符的强度决议求值顺序；优先级高的操作符比优先级低的操作符先求值。 假设一切操作符优先级一样，那么求值顺序就取决于它们的 结合性。操作符的结合性定义了一样优先级操作符组合的顺序从右至左或从左至右。 Left associativity : A+B+C = (A+B)+CRight associativity : ABC = A(BC) 常用表达式求值方法常用表达式求值方法1. 中缀表达式转换成后缀表

10、达式中缀表达式转换成后缀表达式2. 计算后缀表达式计算后缀表达式电气信息学院 计算机系数据结构转换算法：1. 读入运算对象数据，直接输出2. 遇到( 运算符进栈3. 遇到) 运算符，那么栈内的最上一个( 以上的一切运算符退栈，(也退栈4. 读入运算符，进入运算栈 4.1 后进栈的运算符 先进栈的运算符，运算符进栈 (优先级比较) 4.2 后进栈的运算符 = 先进栈的运算符，将栈内的运算符退栈输出，再进栈电气信息学院 计算机系数据结构31*(5-22)+70电气信息学院 计算机系数据结构后缀表达式求值后缀表达式求值 对后缀表达式求值比直接对中对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达

11、式缀表达式求值简单。在后缀表达式中，不需求括号，而且操作符的优中，不需求括号，而且操作符的优先级也不再起作用了。先级也不再起作用了。可以用如下算法对后缀表达式求值：可以用如下算法对后缀表达式求值： 初始化一个空堆栈初始化一个空堆栈 从左到右读入后缀表达式从左到右读入后缀表达式 假设字符是一个操作数，把它压入假设字符是一个操作数，把它压入堆栈。堆栈。 假设字符是个操作符，弹出两个操假设字符是个操作符，弹出两个操作数，执行操作，然后把结果压入作数，执行操作，然后把结果压入堆栈。堆栈。 到后缀表达式末尾，从堆栈中弹出到后缀表达式末尾，从堆栈中弹出结果。假设后缀表达式格式正确，结果。假设后缀表达式格式

12、正确，那么堆栈应该为空。那么堆栈应该为空。电气信息学院 计算机系数据结构31*(5-22)+70参看Class1.java代码电气信息学院 计算机系数据结构1. 顺序栈的普通定义/堆栈接口public interface Stack public int getSize(); public boolean isEmpty(); public void push(Object e); public Object pop() throws StackEmptyException; public Object peek() throws StackEmptyException;二. 根本操作的程序实

13、现电气信息学院 计算机系数据结构1. 顺序栈的普通定义public class StackArray implements Stack private final int LEN=8; / private Object elements; / private int top; public StackArray() top=-1; elements=new ObjectLEN; public int getSize() return top+1; public boolean isEmpty() return top =elements.length) expandSpace(); eleme

14、nts+top =e; 二. 根本操作的程序实现电气信息学院 计算机系数据结构 private void expandSpace() Object a=new Objectelements.length*2; for(int i=0; ielements.length; i+) ai=elementsi; elements=a; public Object pop() throws StackEmptyException if(getSize() 1) throw new StackEmptyException(“错误，堆栈空); Object obj= elementstop; elemen

15、tstop- =null; return obj; public Object peek() throws StackEmptyException if(getSize() 1) throw new StackEmptyException(“错误，堆栈空); return elementstop; 电气信息学院 计算机系数据结构l入栈算法l 出栈算法 .栈底toptopxptop .栈底topq链栈根本操作P67 Stack的链式存储实现初始化、判别栈空、栈满、入栈、出栈、取栈顶元素、销毁。初始化、判别栈空、栈满、入栈、出栈、取栈顶元素、销毁。SLNode p= new SLNode(x,to

16、p); top= p; size+;栈非空，那么Object obj= top.getData() ; top= top.getNext() ; size-;电气信息学院 计算机系数据结构补充补充1：假设入栈动作使地址向高端增长，称假设入栈动作使地址向高端增长，称为为“向上生成的栈；向上生成的栈；假设入栈动作使地址向低端增长，称假设入栈动作使地址向低端增长，称为为“向下生成的栈；向下生成的栈；top=0123450栈空 对于向上生成的栈对于向上生成的栈入栈口诀：堆栈指针入栈口诀：堆栈指针top先压后加先压后加vtop+=x；出栈口诀：堆栈指针出栈口诀：堆栈指针top先减后弹先减后弹y=v-to

17、p) 。 对于向下生成的栈对于向下生成的栈假设商定假设商定top指向栈顶元素的后一个位指向栈顶元素的后一个位置置入栈口诀：堆栈指针入栈口诀：堆栈指针top先压后减先压后减vtop-=x；出栈口诀：堆栈指针出栈口诀：堆栈指针top先加后弹先加后弹y=v+top) 。top=6123450栈空电气信息学院 计算机系数据结构第三章 栈和队列3.2 队队Queue 队的根本实际队的根本实际 定义、逻辑构造、存储构造、根本运定义、逻辑构造、存储构造、根本运算规那么、队的运用算规那么、队的运用2. 根本操作的程序实现方法根本操作的程序实现方法电气信息学院 计算机系数据结构3.2 队列队列的定义及特点定义：

18、队列是限定只能在表的一端进展插入，在表的另一端进展删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队队头front队尾rear队列Q=(a1,a2,an)电气信息学院 计算机系数据结构ADT Queue 数据对象：数据对象：D=ai|aiElemSet, i=1,2,n,n0 数据关系：数据关系：R1=| ai-1,ai D,i=2,n 根本操作：根本操作： getSize(); /前往队列大小，即元素个数前往队列大小，即元素个数 isEmpty() ; /对为空前往对为空前往true,否那么前往否那么前往f

19、alse enqueue(e); /数据元素数据元素e入对入对 dequeue(); /对头元素出对对头元素出对 peek(); /获取对头元素，但不出对获取对头元素，但不出对/ADT Queue队的笼统数据类型定义队的笼统数据类型定义电气信息学院 计算机系数据结构队列的顺序存储构造实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,商定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1

20、 空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront队列会满吗？队列会满吗？这样操作有这样操作有没有问题？没有问题？电气信息学院 计算机系数据结构v存在问题v设数组容量为M，那么：v当front=-1,rear=M-1时，再有元素入队发生溢出真溢出v当front-1,rear=M-1时，再有元素入队发生溢出假溢出0M-11frontrear.v处理方案v队首固定，每次出队剩余元素向下挪动浪费时间v循环队列v根本思想：把队列想象成环形，让sq0接在s

21、qM-1之后，假设rear+1=M,那么令rear=0; 在顺序队中，当尾指针曾经到了数组的上界，不能再有入队在顺序队中，当尾指针曾经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫操作，但其实数组中还有空位置，这就叫“假溢出。假溢出。u实现：利用“求模运算u入队： rear=(rear+1)%M; sqrear=x;u出队： front=(front+1)%M; x=sqfront;u队满、队空断定条件？电气信息学院 计算机系数据结构012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始形状J4,J5

22、,J6出队J7,J8,J9入队队空：front=rear队满：front=rear真溢出假溢出电气信息学院 计算机系数据结构处理方案有三：处理方案有三： 加设标志位，让删除动作使其为加设标志位，让删除动作使其为1,插入动作使其为插入动作使其为0,那那么可识别当前么可识别当前front=rear人为浪费一个单元，令队满特征为人为浪费一个单元，令队满特征为front=(rear+1)%N；运用一个计数器记录队列中元素个数即队列长度；运用一个计数器记录队列中元素个数即队列长度； 选用空闲单元法：即选用空闲单元法：即front和和rear之一指向实元素，另一指向空闲元之一指向实元素，另一指向空闲元素。

23、素。 队空条件队空条件 : front = rear (初始化时：初始化时：front = rear )队满条件：队满条件：front = (rear+1) % N (N=maxsize)队列长度：队列长度：L=Nrearfront% N rearJ2 J3J1 J4 J5front问问2： 在具有在具有n个单元的循环队列个单元的循环队列中，队满时共有多少个元素？中，队满时共有多少个元素？问问1：左图中队列长度：左图中队列长度L=？ 左图中队列容量左图中队列容量maxsize N=？n -156电气信息学院 计算机系数据结构J2 J3J1 J4 J5rearfrontfrontfrontfro

24、ntJ6 J5J7J8 J9例例1： 一循环队列如以下图所示，假设先删除一循环队列如以下图所示，假设先删除4个元素，接个元素，接着再插入着再插入4个元素，请问队头和队尾指针分别指向哪个位置个元素，请问队头和队尾指针分别指向哪个位置? front解：由图可知，队头和队尾指针的初态分别为解：由图可知，队头和队尾指针的初态分别为front=1和和rear=6。frontrear删除删除4个元素后个元素后front=5；再插入；再插入4个元素后，个元素后，r=(6+4)%6=4 frontu入队： rear=(rear+1)%M; u出队： front=(front+1)%M; 电气信息学院 计算机系

25、数据结构例例2 2 ：数组：数组nn用来表示一个循环队列，用来表示一个循环队列，f f 为当前队为当前队列头元素的前一位置，列头元素的前一位置，r r 为队尾元素的位置。假定为队尾元素的位置。假定队列中元素的个数小于队列中元素的个数小于n n，计算队列中元素的公式，计算队列中元素的公式为为: : rf nfr% n nrf nrf% n4种公式哪种合理？种公式哪种合理？当当 r f 时时A合理；合理；当当 r f 时时C合理；合理；分析分析 ：综合综合2种情况，以种情况，以D的表达最为合理的表达最为合理例例3：在一个循环队列中，假设商定队首指针指：在一个循环队列中，假设商定队首指针指向队首元素

26、的前一个位置。那么，从循环队列中向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是删除一个元素时，其操作是 先先 ，后后 。 挪动队首指针挪动队首指针取出元素取出元素rear123450J4,J5,J6入队J4J5J6front电气信息学院 计算机系数据结构根本运算如下： 置空队 分配空间，头尾指针赋值，计数赋0 入队 顺序表插入，调整头尾指针 计数赋 出队 顺序表删除，调整头尾指针 计数赋 判队空 队列中数据数目为0。 运用计数器的循环队列的类型定义：运用计数器的循环队列的类型定义：Java实现运用计数器的循环队列.txt电气信息学院 计算机系数据结构结点接口结点接口Public interface Nodepublic Object getData( );/获取结点数据域获取结点数据域Public void setData(Object object);/设置结点数据域设置结点数据域Public class SLNode implements Node private Object element; private SLNode next; public SLNode this(null,null); public SLNode(Obje