数据结构(第四章 栈和队列).ppt

1、数 据 结 构,第 4 章 栈和队列,现实生活中的一些线性数据结构的事例： 递归问题的解决方法 表达式的计算：如5（43（52） 排队等车的队列 栈和队列的特点： 它们的状态是不断变化的 添加和删除是它们共同的操作 添加和删除在特定的位置（哪些位置？） 考虑：此类数据结构应该对用户提供哪些操作？,栈和队列,栈和队列,栈和队列是在程序设计中被广泛使用的两种特殊的线性表，它们的特殊性在于对栈和队列的插入和删除操作被限制为只能在表的两端（或一端）进行： L=（a1,a2,a3,ai,an） 线性表：在表的任意位置进行插入和删除： 栈：只能在表尾进行插入和删除：“后进先出”。 队列: 只能在表尾进行插

2、入,而在表头删除：“先进先出”。 和线性表相比，栈和队列的插入和删除操作受更多的约束和限定，故又称为操作受限（或限定性）的线性表结构。,可将线性表和栈及队列的插入和删除操作对比如下：,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 /表尾 /表尾 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in /表尾 /表头,栈和队列,主要内容,4.1 栈 4.2 队列,4.1 栈,栈的抽象数据类型,栈的定义 栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。

3、通常称允许插入、删除操作的这一端为栈顶(Top)，不允许操作的一端称为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a0，a1，a2，a3，an-1)，则a0称为栈底元素，an-1为栈顶元素，标识栈顶位置的指针称为栈顶指针。栈中元素按a0， a1，a2，a3， an-1的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,栈的操作 习惯上将每次删除（也称为退栈）操作又称为出栈或弹出（POP）操作。删除的元素总是当前栈中“最新”的元素（栈顶元素）。 每次插入（称为进栈）操作称为入栈或压入（PUSH）操作，入栈的

4、元素总是当前栈中“最新”的元素。 在空栈中最先插入的元素总被放在栈的底部，只有所有元素被弹出之后它才能被删除。,4.1 栈,栈的抽象数据类型,base,base,base,base,base,stacksize,入栈示例,4.1 栈,栈的抽象数据类型,base,base,base,base,base,出栈示例,4.1 栈,栈的抽象数据类型,出、入栈示例,4.1 栈,栈的抽象数据类型,图4.1 栈（顺序栈）及其状态变化：A, B, C, D 入栈, 入栈, 出栈, 入栈, 入栈, 出栈, 出栈, 出栈,【思考题4-1】 入栈A, B, C, D，出栈A, B, C, D、D, C, B, A？还

5、有哪些？有哪些不可能的出栈序列？为什么？,出、入栈示例,4.1 栈,栈的抽象数据类型,栈的数据元素,栈的数据元素和线性表的数据元素完全相同，即栈的数据元素是n（n=0）个相同类型的数据元素a0，a1，。an-1组成的有限序列，记为：a0,a1,an-1。 其中，n为数据元素的个数，称为栈的长度。n=0时，为空栈。 考虑：线性表和栈的区别在哪呢？,4.1 栈,栈的抽象数据类型,栈的运算,栈的基本运算一般有以下几种： InitStack（S）构造一个空栈S。 StackEmpty（S）判栈空，若S为空栈返回TRUE，否则返回FALSE。 StackFull（S）判栈满，若S为满栈，则返回TRUE，

6、否则返回 FALSE。该运算只适用于栈的顺序存储结构。 Push（S，x）入栈。若栈S不满，则将元素x压入S的栈顶。 Pop（S）出栈。若栈S非空，则将S的栈顶元素弹出，并返回该元素。 StackTop（S）取栈的栈顶元素，不修改栈顶指针。 比较重要的运算就是入栈和出栈两种。,4.1 栈,栈的抽象数据类型,栈的溢出,当栈满时进栈运算称为“上溢”。 当栈空时退栈运算称为“下溢”。 栈上溢是一种出错状态，应该设法避免之；而下溢则可能是正常现象，通常下溢用来作为程序控制转移的条件。,4.1 栈,栈的抽象数据类型,栈抽象数据类型ADT，栈接口,public interface Stack public

7、 abstract boolean isEmpty(); /判空 public abstract void push(T x); /x入栈 public abstract T peek(); /返回栈顶，未出栈 public abstract T pop(); /出栈，返回栈顶 ,4.1 栈,栈的抽象数据类型,总结 栈的运算规则是按后进先出的原则进行的（又称为后进先出），简称为LIFO（last in first out）表。 就线性表而言，实现栈的方法有很多，由于栈也是线性表，因此线性表的存储结构对栈也适用，我们着重介绍顺序栈（arrary-based stack）和链式栈（linked s

8、tack） ，它们类似于顺序表和链式表。 这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。,4.1 栈,栈的抽象数据类型,栈的表示和实现,4.1 栈,栈的抽象数据类型,能否使用一个线性表对象作为栈，或将栈声明为继承线性表？入栈调用insert(0,x)函数，出栈调用remove(0)函数？为什么？ 【习题解答】都不能。,习题,4.1 栈,栈的抽象数据类型,由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈（Sequential Stack），它是运算受限的线性表。因此，可用数组来实现顺序栈。 因为栈底位置是固定不变的，所以可以将栈底位置设置在

9、数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，一般需用一个整型变量top。,顺序栈的定义,4.1 栈,顺序栈,顺序栈的操作实例如上图所示,4.1 栈,顺序栈,顺序栈的定义,栈的顺序存储结构及操作实现 public class SeqStack implements Stack /顺序栈类，实现栈接口 Object element; /存储栈数据元素的数组 int top; /栈顶元素下标 注意：element数组存储栈的数据元素；top表示当前栈顶元素的下标。,顺序栈的实现（经典实现）,4.1 栈,顺序栈,基于数组的顺序栈（经典实现）,顺序栈的实现从本质上讲，就是顺序线性表实

10、现的简化。惟一重要的是需要确定应该用数组的哪一端表示栈顶： 一种选择是把数组的第0个位置作为栈顶。根据线性表的函数，所有的插入(insert)和删除(remove)操作都在第0个位置的元素上进行。由于这时每次push(insert)或者pop(remove)操作都需要把当前栈中的所有元素在数组中移动一个位置，因此效率不高。如果栈中有n个元素，则时间代价为O(n)。 另一种选择是当栈中有n个元素时把位置n-1作栈顶。也就是说，当向栈中压人元素时，把它们添加到线性表的表尾，成员函数pop也是删除表尾元素。在这种情况下，每次push或者pop操作的时间代价仅为O(1)。,4.1 栈,顺序栈,栈的运算

11、主要考虑栈的入栈和出栈算法： 其原因是在栈的基本运算中有六种：判断栈空、栈初始化、判断栈满（仅限于顺序存储的情况下），入栈元素、出栈元素、取栈顶元素等 而入栈时需要考虑的操作步骤是： 栈初始化，然后判断栈是否为满，如果不满，则可以插入元素（入栈） 出栈时，需要考虑的步骤是： 判断栈是否为空，如果不空，删除元素（出栈），出栈之前，保存栈顶元素。 也就是说，栈的入出栈运算包含了其他的六种基本运算，取栈顶元素的运算，只是不用修改栈顶的指针而已。,基于数组的顺序栈（经典实现）,4.1 栈,顺序栈,（1）栈的初始化 public SeqStack(int size) /构造容量为size的空栈 this

12、.element = new ObjectMath.abs(size); this.top=-1; public SeqStack() /构造默认容量的空栈 this(64); ,基于数组的顺序栈（经典实现）,4.1 栈,顺序栈,（2）判读栈是否为空 public boolean isEmpty() /判断栈是否空，若空返回true return this.top=-1; ,基于数组的顺序栈（经典实现）,4.1 栈,顺序栈,判读栈是否为满？ 本实现采用与顺序表同样的处理：当容量不够时，则将数组容量扩充一倍。,基于数组的顺序栈（经典实现）,4.1 栈,顺序栈,（3）入栈 空元素不能入栈 栈的容量

13、不够时，数组容量倍增 栈顶元素top加1，将element放入top位置，作为新的栈顶元素 public void push(T x) /元素x入栈，空对象不能入栈 if (x=null) return; /空对象不能入栈 if (this.top=element.length-1) /若栈满，则扩充栈容量 Object temp = this.element; this.element = new Objecttemp.length*2; /重新申请一个容量更大的数组 for (int i=0; itemp.length; i+) /复制数组元素，O(n) this.elementi = t

14、empi; this.top+; this.elementthis.top = x; ,基于数组的顺序栈（经典实现）,4.1 栈,顺序栈,（4）出栈 栈不空时，取走top位置处栈顶元素，top减1，下一位置数据元素作为新的栈顶元素 public T pop() /出栈，返回栈顶元素，若栈空返回null return this.top=-1 ? null : (T)this.elementthis.top-; ,基于数组的顺序栈（经典实现）,4.1 栈,顺序栈,（5）获得栈顶数据元素 栈不空时，获取top位置处栈顶元素，此时数据元素未出栈，top值不变 public T get() /取栈顶元素

15、，未出栈，若栈空返回null return this.top=-1 ? null : (T)this.elementthis.top; ,基于数组的顺序栈（经典实现）,4.1 栈,顺序栈,顺序栈实现（基于已有顺序表）,/顺序栈类，最终类，实现栈接口，T表示元素类型 public final class SeqStack implements Stack private SeqList list; /顺序表 public SeqStack(int capacity) /构造空栈 public SeqStack() /构造空栈 public boolean isEmpty() /判空 public

16、 void push(T x) /x入栈 public T peek() /返回栈顶（未出栈） public T pop() /出栈，返回栈顶元素 ,4.1 栈,顺序栈,/顺序栈类，最终类，实现栈接口，T表示数据元素的数据类型 public final class SeqStack implements Stack private SeqList list; /使用顺序表（第2章）存储栈元素 public SeqStack(int length) /构造容量为length的空栈 this.list = new SeqList(length); /执行顺序表构造方法 public SeqStac

17、k() /构造默认容量的空栈 this(64); ,顺序栈实现（基于已有顺序表）,4.1 栈,顺序栈,public boolean isEmpty() /判断栈是否空，若空返回true return this.list.isEmpty(); public void push(T x) /元素x入栈，空对象不能入栈 this.list.insert(x); /顺序表尾插入元素x，自动扩充容量 public T peek() /返回栈顶元素（未出栈），若栈空返回null return this.list.get(list.size()-1); /若栈空，get(i)返回null / return

18、this.isEmpty() ? null : this.list.get(list.size()-1); ,顺序栈实现（基于已有顺序表）,4.1 栈,顺序栈,public T pop() /出栈，返回栈顶元素；若栈空返回null return this.list.remove(list.size()-1); /若栈不空，顺序表尾删除，返回删除元素 / return this.isEmpty() ? null : this.list.remove(list.size()-1); /若栈不空，顺序表尾删除，返回删除元素 public String toString() /返回栈所有元素的描述字符

19、串，形式为“(,)” return this.getClass().getName()+ +this.list.toString(); ,顺序栈实现（基于已有顺序表）,4.1 栈,顺序栈,习题解答4-4 使用顺序表对象作为栈成员变量的操作效率分析,4.1 栈,顺序栈,链式栈定义,栈的链式存储，称为链栈。 链式栈的基本运算同顺序栈，定义也同线性表的链表定义，它是对链表实现的简单化（因为它只是对链表的头部操作）。 可用单向链表实现链栈。 它的元素只能在表头进行插入和删除。在链式存储结构中，不需要给出表头结点（head），因为其中惟一的已知条件是栈顶指针top，它是指向链式栈的第一个结点（相当于头指

20、针）。,4.1 栈,链式栈,图 栈的链式存储结构,链式栈定义,4.1 栈,链式栈,栈的链式存储结构及操作实现 public class LinkedStack implements Stack private Node top; ,链式栈实现（经典实现）,4.1 栈,链式栈,栈的各种运算比链式存储的普通线性表运算实现时要方便得多，主要原因是栈的各种运算只能在栈的一端操作，栈是特殊的线性表，我们只要考虑对线性表的一端操作的情况，并且只能在一端插入删除（栈顶） 而线性表除此之外（不限定一端插入删除），还需要考虑另外一端结点以及中间的结点的插入、删除、查询等操作，理解时，我们可以把栈的入出栈运算当作

21、线性表的一端进行插入删除的特例即可。,链式栈实现（经典实现）,4.1 栈,链式栈,图 链式栈的入栈和出栈操作,链式栈实现（经典实现）,4.1 栈,链式栈,栈的特性是只有一端（栈顶）可以删除和添加。 单链表表头操作比较方便。 入栈操作只需向单链表的头部添加一个结点即可。 出栈操作只需将单链表的表头结点删除即可。,链式栈实现（经典实现）,4.1 栈,链式栈,（1）栈的初始化 public LinkedStack() /构造空栈 this.top=null; ,链式栈实现（经典实现）,4.1 栈,链式栈,（2）判读栈是否为空 public boolean isEmpty() /判断栈是否空，若空返回

22、true return this.top=null; ,链式栈实现（经典实现）,4.1 栈,链式栈,链式栈实现（经典实现）,4.1 栈,链式栈,链式栈实现（经典实现）,4.1 栈,链式栈,（3）入栈 public void push(T x) /元素x入栈，空对象不能入栈 if (x!=null) this.top = new Node(x, this.top); /头插入，x结点作为新的栈顶结点 ,链式栈实现（经典实现）,4.1 栈,链式栈,（4）出栈 public T pop() /出栈，返回栈顶元素，若栈空返回null if (this.top=null) return null; T

23、temp = this.top.data; /取栈顶结点元素 this.top = this.top.next; /删除栈顶结点 return temp; ,链式栈实现（经典实现）,4.1 栈,链式栈,（5）获得栈顶元素 public T get() /取栈顶元素，未出栈，若栈空返回null return this.top=null ? null : this.top.data; ,链式栈实现（经典实现）,4.1 栈,链式栈,/链式栈类，最终类，实现栈接口，T表示元素类型 public final class LinkedStack implements Stack private Singl

24、yList list; /单链表 public LinkedStack() /构造空栈 public boolean isEmpty() /判空 public void push(T x) /x入栈 public T peek() /返回栈顶（未出栈） public T pop() /出栈，返回栈顶元素 ,链式栈实现（基于单链表）,4.1 栈,链式栈,/链式栈类，最终类，实现栈接口，T表示数据元素的数据类型 public final class LinkedStack implements Stack private SinglyList list; /使用单链表（第2章）存储栈元素 publ

25、ic LinkedStack() /构造空栈 this.list = new SinglyList(); /构造空单链表 public boolean isEmpty() /判断栈是否空，若空返回true return this.list.isEmpty(); ,链式栈实现（基于单链表）,4.1 栈,链式栈,public void push(T x) /元素x入栈，空对象不能入栈 this.list.insert(0, x); /单链表头插入元素x public T peek() /返回栈顶元素（未出栈）；若栈空返回null return this.list.get(0); ,链式栈实现（基于

26、单链表）,4.1 栈,链式栈,public T pop() /出栈，返回栈顶元素；若栈空返回null return this.list.remove(0); /若栈不空，单链表头删除，返回删除元素 public String toString() /返回栈所有元素的描述字符串，形式为“(,)” return this.getClass().getName()+ +this.list.toString(); ,链式栈实现（基于单链表）,4.1 栈,链式栈,习题解答4-4 使用单链表对象作为栈成员变量的操作效率分析,4.1 栈,链式栈,实现链式栈和顺序栈的操作，都是需要常数时间，即时间复杂度为O（

27、1）。主要两者从空间和时间两个方面考虑： 初始时，顺序栈必须说明一个固定的长度，当栈不够满时，造成一些空间的浪费，而链式栈的长度可变则是长度不需要预先设定，相对比较节省空间，但是在每个结点中，设置了一个指针域，从而产生了结构开销。,4.1 栈,顺序栈和链式栈的比较,当需要多个栈共享时，顺序存储中可以充分利用顺序栈的单向延伸性。可以使用一个数组存储两个栈，使每个栈从各自的端点向中间延伸，这样浪费的空间就会减少。但这种情况只有当两个栈的空间需求有相反的需求时，这种方法才有效。也就是说，最好一个栈增长，一个栈缩短。反之，如果两个栈同时增长，则可能比较容易造成栈的溢出。如果多个顺序栈共享空间，则可能需

28、要大量的数据移动，造成时间的开销增大。而链式栈由于存储的不连续性，一般不存在栈满的问题，所以一般不需要栈的共享。,4.1 栈,顺序栈和链式栈的比较,（一）程序调用 （二）递归 （三）括号匹配 （四）表达式的求值 （五）汉内塔（hanoi）问题 （六）数制转换 （七）行编辑程序,4.1 栈,栈的应用,函数（过程）的嵌套调用：在一个函数内调用另 一个函数,Call 1,Call 2,Call 3,4.1 栈,栈的应用-程序调用,函数嵌套调用,1. 将所有的实参、返回地址等信息传递给被调用函数保存； 2. 为被调用函数的局部变量分配存储区； 3. 将控制转移到被调用函数的入口。 -保护断点,当在一个

29、函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,4.1 栈,栈的应用-程序调用,1. 保存被调函数的计算结果； 2. 释放被调函数的数据区； 3. 依照被调函数保存的返回地址将控制转移到调用函数。 -恢复断点,从被调用函数返回调用函数之前，应该完成下列三项任务：,4.1 栈,栈的应用-程序调用,例 用栈实现程序设计语言中的子程序调用和返回。,假设有一个主程序main和三个子程序A1，A2和A3，其调用关系如下图所示。,4.1 栈,栈的应用-程序调用,从上图可知，主程序main调用子程序A1，子程序A1完成之后，返回到主程序的r处继续执行。但是，因为子程序A1又调用了

30、子程序A2，所以在A2执行完毕并返回之前，A1是不可能结束的。类似地，A2也必须在A3执行完毕并返回之后才能从t处继续进行。其调用与返回的过程如下图所示。,显然，调用次序和返回次序是 相反的，最后调用到的子程序 最先返回。为了保证各个被调 用子程序能正确地返回，可以 在程序运行期间设置一个工作 栈来保存返回地址。,4.1 栈,栈的应用-程序调用,4.1 栈,栈的应用-程序调用,使用栈以非递归方式实现递归算法,4.1 栈,栈的应用-递归,例 括号匹配的语法检查,程序设计语言的表达式中，只能通过括号改变运算次序，而且括号必须是左右匹配的。 在程序实际运行的过程中，编译系统是通过栈来判断括号是否匹配

31、的。 本例中，声明了类Bracket，对于给定字符串infix,方法isMatched（）判断其中的括号是否匹配。,4.1 栈,栈的应用-括号匹配,4.1 栈,栈的应用-括号匹配,isMatched（）的算法描述如下： 设ch是待检测字符串infix的当前字符：则有 若ch是左括号，则ch入栈； 若ch是右括号，则出栈一个值。 若出栈值为左括号，表示括号匹配； 若出栈值为空（null）或不为左括号，则表示缺少左括号，期望左括号。 重复执行上一步。当infix检测结束后： 若栈为空，表示括号匹配； 否则表示缺少右括号，期望右括号。,4.1 栈,栈的应用-括号匹配,public class Bra

32、cket /检查infix表达式中的圆括号是否匹配，若匹配，返回空串； /否则返回错误信息 public static String isMatched(String infix) SeqStack stack = new SeqStack(infix.length(); /声明接口对象stack，引用实现Stack接口的顺序栈类的实例， /创建空栈 / Stack stack = new LinkedStack();,4.1 栈,栈的应用-括号匹配,for (int i=0; iinfix.length(); i+) char ch=infix.charAt(i); switch(ch) c

33、ase (: stack.push(ch+); /左括号入栈 System.out.println(stack.toString(); break; case ): if (stack.isEmpty() | !stack.pop().equals() /遇见右括号时，出栈 return 期望(; /检查出栈字符是否为左括号 return (stack.isEmpty() ? : 期望); /返回空串表示没有错误 ,4.1 栈,栈的应用-括号匹配,public static void main(String args) String infix=(1+2)*3+4)(; System.out.

34、println(infix+ ，编译错误：+Bracket.isMatched(infix); /* 运行结果如下： (1+2)*3+4)( ，编译错误：期望( */,4.1 栈,栈的应用-括号匹配,例 使用栈计算算术表达式值,算术表达式有三种表示方法： ，如A+B，称为中缀(infix)表示； ，如+AB称为前缀(prefix)表示； ，如AB+，称为后缀(postfix)表示。 在后缀表达式中，没有括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程仅需一遍扫描便可完成，显然比中缀表达式的计算要简单得多。因此，程序设计语言的编译系统要将通常的中缀表达式转换成后

35、缀表达式,4.1 栈,栈的应用-表达式求值,例如，A*(B+C)的后缀表达式是ABC+*, 因+运算符在前，* 运算符在后，所以应先做加法，后做乘法。 再如，表达式A/B*C+D*(E-A)+C/(D*B) 的后缀形式是AB/C*DEA-*+CDB*/+ .,怎样设计算法把运算符放在两个运算对象中间的中缀表达式转换为后缀形式呢？ 观察一下两种形式的表达式，我们注意到操作数在两种形式中出现的次序是相同的。所以在扫描表达式时，凡遇到操作数就马上输出，剩下的事情就是处理所遇到的运算符。解决的办法是把遇到的运算符存放到栈中，直到某个适当时刻再将运算符退栈并输出。,4.1 栈,栈的应用-表达式求值,我们

36、来看两个例子： （1）要由表达式A+B*C产生出后缀表达式ABC*+，必须按照如表3.1所示的操作顺序执行（栈向右增长）。到达第4步时必须确定是*进入栈顶，还是+退栈；由于*的优先级更高，应该是*进栈，从而产生第5步；现在已从表达式中取完所有的符号，于是我们输出运算符栈中所有剩余的运算符得到： ABC*+,4.1 栈,栈的应用-表达式求值,（2）表达式A*(B+C)/D 的后缀形式为ABC+* D/，当遇到左括号时必须入栈，遇到右括号时，必须依次把栈中元素退栈。直到相应的左括号为止，然后去掉左右括号。如表3.2所示。,4.1 栈,栈的应用-表达式求值,这些例子启发我们，算术运算符和括号可用如上

37、表3.3所示分级方案实现。其规则是：,只要运算符在栈中的优先级isp(in-stack priori ty)大于或等于新运算符进来时的优先级icp(in-c oming priority)，则运算符就从栈中取出。,4.1 栈,栈的应用-表达式求值,【习题解答】ABCDEF+*G/-H+*+IJ+K*-,习题4-5 中缀表达式如下， 写出后缀表达式。 A+B*(C-D*(E+F)/G+H)-(I+J)*K,4.1 栈,栈的应用-表达式求值,中缀表达式：1+2*(3-4)+5,4.1 栈,栈的应用-表达式求值,（1）将中缀表达式转换为后缀表达式,4.1 栈,栈的应用-表达式求值,（2）后缀表达式求

38、值,4.1 栈,栈的应用-表达式求值,public class Expression StringBuffer toPostfix(String infix) /返回将infix中缀表达式转换成的后缀表达式 int toValue(StringBuffer postfix) /计算后缀表达式的值 ,4.1 栈,栈的应用-表达式求值,队列的定义,队列(Queue)也是一种运算受限的特殊线性表。其插入和删除操作分别在线性表的两端进行（只允许在表的一端进行插入，而在另一端进行删除）。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 当队列中没有元素时称为空队列。在空队列中依

39、次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的，例如：排队购物。 先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。,4.2 队列,队列抽象数据类型,下图是队列的示意图：,4.2 队列,队列抽象数据类型,队列的数据元素,队列的数据元素和线性表的数据元素完全相同，即队列的数据元素是n（n=0）个相同类型的数据元素a0，a1，。an-1组成的有限序列，记为：a0,a1,an-1。 其中，n为数据元素的个数，称为队列的长度。n

40、=0时，为空队列 。 考虑：那么线性表和队列的区别在哪呢？,4.2 队列,队列抽象数据类型,队列的操作,队列的基本运算通常和栈的基本运算类似，有以下6种： 置空队； /构造一个空队列。 判队空； /队空返回真，否则返回假。 判队满； /队满返回真，否则返回假，仅限于顺序存储结构。 入队； /队列非满时，从队尾插入元素。 出队； /队列非空时，从队首删除元素。 取队首元素； /返回队首元素，不修改队首指针。,4.2 队列,队列抽象数据类型,队列的操作,队列的操作： 一般情况下，入队(enqueue)操作又称为队列的插入。 出队(dequeue)操作又称为队列的删除。,4.2 队列,队列抽象数据类

41、型, 0 1 2 3,front rear,front rear,(a)队列初始为空（b）a,b,c入队,front rear front rear （c) a出队 (d) b,c出队，队为空,4.2 队列,队列抽象数据类型,队列的操作,队列抽象数据类型,/队列接口，描述队列抽象数据类型，T表示元素类型 public interface Queue public abstract boolean isEmpty(); /判空 public abstract boolean add(T x); /x入队 public abstract T peek(); /返回队头，没有删除 public ab

42、stract T poll(); /出队，返回队头 ,4.2 队列,队列抽象数据类型,队列的存储结构 队列的存储具有顺序和链式存储两种,4.2 队列,队列抽象数据类型,习题 能否使用一个线性表对象作为队列， 或将队列声明为继承线性表，入栈调用insert(x)函数，出栈调用remove(0)函数？为什么？,【习题解答】都不能。,4.2 队列,队列抽象数据类型,顺序队列的基本概念： 队列的顺序存储结构称为顺序队列。 顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也必须用一个数组空间来存放当前队列中的元素。 由于队列的队头和队尾的位置是变化的，因而要设置两个指针front和和rear分别

43、指示队头元素和队尾元素在数组空间中的位置，它们的初值在队列初始化时可以置为0。,4.2 队列,顺序队列,如果队列的长度（即上限）可以事先预知，对我们分配队列的内存空间有很大帮助。 我们说的队列长度是指在某一瞬间，队列的长度，不是指通过队列的元素之和。 键盘的敲击产生的消息也是存放在队列中，依次进入系统进行处理。,基于数组的队列,4.2 队列,顺序队列,数组队列的操作： 主要考虑队列的入队和出队算法。其原因是在队列的基本运算中有六种：判断队空、队列初始化、判断队列满（仅限于顺序存储的情况下），入队元素、出队元素、取队首元素等。 而入队时需要操作的步骤是：初始化，然后判断队列是否为满，如果不满，则

44、可以插入元素（入队）。 出队时，需要考虑的操作步骤是：判断队列是否为空，如果不空，删除元素（出队），出队之前，保存队首元素。 也就是说，队列的入出队运算包含了其他的六种基本运算，取队首元素的运算，只是不用修改队首的指针而已。,基于数组的队列,4.2 队列,顺序队列,基于数组的队列,4.2 队列,顺序队列,基于数组的队列,4.2 队列,顺序队列,基于数组的队列,4.2 队列,顺序队列,基于数组的队列,4.2 队列,顺序队列,基于数组的队列,4.2 队列,顺序队列,数组队列的操作： 入队时将新元素插入rear所指的位置，然后将rear加1。 出队时，删去front所指的元素，然后将front加1并

45、返回被删元素。 由此可见，当头尾指针相等时队列为空。 在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。,基于数组的队列,4.2 队列,顺序队列,非循环的数组队列的几个条件： 队空：Q.front=Q.rear 队满：Q.rear=maxsize（假溢出） 求队长： Q.rear-Q.front 入队：新元素按 rear 指示位置加入，再将队尾指针加一 ，即 rear = rear + 1 出队：将front指示的元素取出，再将队头指针加一，即front = front + 1,基于数组的队列,4.2 队列,顺序队列,数组已经到了最右端，此时，我们无法再往数组中加入数

46、据了，但前面显然有空间我们没有使用。我们称这种情况为假上溢。,基于数组的队列,4.2 队列,顺序队列,数组队列的假溢出： 队列同栈一样也有上溢和下溢现象。 此外队列中还存在“假溢出”现象。所谓“假溢出”是指在入队和出队操作中，头尾指针不断增加而不减小或只减小而不增加，致使被删除元素的空间无法重新利用，最后造成队列中有空闲空间，但是不能够插入元素，也不能够删除元素的现象。 因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针已超越向量空间的上界而不能进行入队或出队操作。该现象称为假上溢。,基于数组的队列,4.2 队列,顺序队列,解决假上溢现象的方法有很多种： 基于顺序表： 如

47、固定队首指针，一旦删除元素，需要移动所有元素后，修改队尾指针，这样又可以插入元素了，只有在不能插入元素时，队列才满，否则可以一直插入元素，这种方法虽然能够解决“假溢出”，但需要造成大量的数据元素的移动。,基于顺序表的队列,4.2 队列,顺序队列,基于顺序表： 缺点： 使用顺序表，出队效率低。,基于顺序表的队列,4.2 队列,顺序队列,解决假上溢现象的方法有很多种： 顺序循环队列： 现在解决“假溢出”比较好的解决方案是使用循环向量，存储在循环向量中的队列称为循环队列（Circular Quene）。 将顺序队列设计成在逻辑上首尾相接的循环结构，则可循环使用顺序队列的连续存储单元。,顺序循环队列,

48、4.2 队列,顺序队列,假设数组的空间是m，只要在入、出队列时，将队首和队尾的指针对m做求模运算即可实现队首和队为指针的循环，即队首和队尾指针的取值范围是0到m-1之间。 入队时：rear=（rear+1）% maxsize 出队时：front=（front+1）% maxsize,顺序循环队列的操作,4.2 队列,顺序队列,J4,J5,J6,0,1,2,3,4,5,rear,front,初始状态,队空：front=rear 队满：front=rear,解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front,顺

49、序循环队列,4.2 队列,顺序队列,但是入队和出队时front和rear的取值不能够确定队列的空和满： 因为入队时，rear指针不断增加一个，当rear指针“追上”front指针时，此时队列已经满了，此时满的条件是rear=front； 反之，当出队时，front指针不断增加一个，当front指针“追上”rear指针时，此时队列已经空了，此时队列空的条件是rear=front。 由此可见队空和队满的条件是相同的，都是front=rear。,顺序循环队列,4.2 队列,顺序队列,区分队空和队满的方法有多种： 方法一：设定一个变量来表示队列中的元素个数，利用该变量的值与队列的最大容量比较，如果该变

50、量的值与最大容量相等，则表示队满，如果该变量的只为0，此时表示队列为空。 此方法每次入队、出队一个元素时，需要修改队列中的数据元素的个数。,顺序循环队列,4.2 队列,顺序队列,区分队空和队满的方法有多种： 方法二：可以设置浪费一个空间单元，也就是假定rear指向的是刚刚插入元素的位置，front指向刚刚删除元素的位置。 也就是说在入队时，先不修改rear的值，而是先判断（rear+1） % maxsize=front，如果成立，表示队列已满（此时实际还有rear指向的位置空闲） 出队时，只要判断front=rear，如果成立表示队已空，否则只要front=（front+1） % maxsiz

51、e直接删除元素即可。 此种方法存储的数据元素个数是maxsize-1个，是利用浪费一个空间来换取队空与满的条件。,顺序循环队列,4.2 队列,顺序队列,front=(front+1) % length; rear=(rear+1) % length;,顺序循环队列,4.2 队列,顺序队列,顺序循环队列的几个条件： 队空：Q.front =Q. rear 队满： Q.front =(Q.rear + 1) % maxSize 入队: Q.rear = (Q.rear + 1) % maxSize 出队: Q.front = (front + 1) % maxSize; 求队长:(Q.rear-Q

52、.front+maxSize)%maxSize,顺序循环队列,4.2 队列,顺序队列,/顺序循环队列类，最终类，实现队列接口，T元素类型 public final class SeqQueue implements Queue private Object element; /数组 private int front, rear; /队列头尾下标 public SeqQueue(int capacity)/构造空队列 public SeqQueue() /构造空队列 public boolean isEmpty(); /判空 public boolean add(T x); /x入队 publ

53、ic T peek(); /返回队头，没有删除 public T poll(); /出队，返回队头 ,顺序循环队列,4.2 队列,顺序队列,/4.2.2 顺序循环队列 /顺序循环队列类，最终类，实现队列接口，T表示数据元素的数据类型 public final class SeqQueue implements Queue private Object element; /存储队列数据元素的数组 private int front, rear; /front、rear分别为队列头尾下标 public SeqQueue(int length) /构造容量为length的空队列 if (length

54、64) length=64; /设置队列数组容量最小值 this.element = new Objectlength; this.front = this.rear = 0; /设置空队列 public SeqQueue() /构造默认容量的空队列 this(64); ,顺序循环队列,4.2 队列,顺序队列,public boolean isEmpty() /判断队列是否空，若空返回true return this.front=this.rear; public boolean add(T x) /元素x入队，空对象不能入队 if (x=null) return false; / throw

55、 new NullPointerException(x=null); /抛出空对象异常 if (this.front=(this.rear+1)%this.element.length) /若队列满，则扩充数组 Object temp = this.element; this.element = new Objecttemp.length*2; /重新申请一个容量更大的数组 int j=0; for (int i=this.front; i!=this.rear; i=(i+1) % temp.length) /按照队列元素次序复制数组元素 this.elementj+ = tempi; th

56、is.front = 0; this.rear = j; this.elementthis.rear = x; this.rear = (this.rear+1) % this.element.length; return true; ,顺序循环队列,4.2 队列,顺序队列,public T peek() /返回队头元素，没有删除。若队列空，则返回null return this.isEmpty() ? null : (T)this.elementthis.front; public T poll() /出队，返回队头元素，若队列空返回null if (this.isEmpty() return null; T temp = (T)this.elementthis.front; this.front = (this.front+1) % this.element.length; return temp; public String toString() /返回队列所有元素的描述字符串，形式为“(,)”，按照队列元素次序 St