第3章栈和队列 本章学习目标  理解栈和队列的基本概念  掌握顺序栈和链栈的各种操作实现  掌握链队列和循环队列的各种操作实现  学会利用栈和队列解决应用问题 栈 和队列是非常重要的两种数据结构，在软件设计中的应用很多。栈和队列也是线性结构，线性表、栈和队列这3种数据结构的数据元素以及数据元素间的逻辑关系完全相同，区别在于线性表的操作不受限制，而栈和队列的操作受到限制。栈的操作只能在表的一端进行； 队列的插入操作在表的一端进行，而其他操作在表的另一端进行。因此，将栈和队列称为操作受限的线性表。 视频讲解 3.1栈的基本概念 3.1.1栈的相关定义 1. 栈 栈(stack)是只允许在表尾端进行插入和删除的线性表。 在插入数据元素时，新插入的数据元素e只能处于线性表的表尾，如图31所示。 在删除数据元素时，只能删除线性表的表尾元素，如图32所示。 图31插入数据元素 图32删除数据元素 2. 栈顶和栈底 表尾端为栈顶(top)，表头端为栈底(bottom)。 3. 进栈和出栈 栈的插入操作称为入栈或进栈(push)，栈的删除操作称为出栈或退栈(pop)。 4. LIFO 最后入栈的数据元素最先出栈，最先入栈的数据元素最后出栈。因此，栈也被称为“后进先出”(Last In First Out，LIFO)的线性表。 图33栈的图示 图33为栈的图示。其中，an是最后入栈的数据元素，an最先出栈； a1是最先入栈的数据元素，a1最后出栈。 在实际生活中有许多类似于栈的例子。例如，刷洗盘子，将洗净的盘子一个接一个地往上放(相当于将元素入栈)； 在取用盘子时，则从最上面一个接一个地往下拿(相当于将元素出栈)。 3.1.2栈的抽象数据类型 ADT Stack{ 数据对象： D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系： R={|ai-1,ai∈D,i=2,…,n} 基本操作： (1) int Count()： 求栈的长度。 操作结果： 返回栈中数据元素的个数。 (2) boolean IsEmpty()： 判断栈是否为空。 操作结果： 如果栈为空，则返回TRUE，否则，返回FALSE。 (3) Clear()： 清空操作。 操作结果： 使栈为空。 (4) Push(T item)： 入栈操作。 操作结果： 将值为item的新的数据元素添加到栈顶，栈发生变化。 (5) T Pop()： 出栈操作。 初始条件： 栈不为空。 操作结果： 将栈顶元素从栈中取出，栈发生变化。 (6) T GetTop()： 取栈顶元素。 初始条件： 栈不为空。 操作结果： 返回栈顶元素的值，栈不发生变化。 } 关于栈抽象数据类型中D的说明： D是n个数据元素的集合，D是ElemSet的子集。ElemSet表示某个集合，集合中的数据元素类型相同，如整数集、自然数集等。 关于栈抽象数据类型中R的说明： R是数据元素之间关系的集合，表示ai-1和ai之间互为前驱和后继的逻辑关系。约定an端为栈顶，a1端为栈底。 栈的数据对象和数据关系与线性表相同。 关于栈抽象数据类型中基本操作的说明： (1) 栈的数据元素类型用T表示，T可以是原子类型，也可以是结构类型。整型用int表示，逻辑型用boolean表示。 (2) 栈的基本操作是定义于逻辑结构上的基本操作，是向使用者提供的使用说明。基本操作只有在存储结构确定之后才能实现。如果栈采用的存储结构不同，则栈的基本操作实现算法也不相同。 (3) 基本操作的种类和数量可以根据实际需要决定。但是，栈是操作受限的线性表，不能任意地定义基本操作。例如，不能在栈的第i个位置插入数据元素。 (4) 基本操作名称，形式参数数量、名称、类型，返回值类型等由设计者决定。使用者根据设计者的设计规则使用基本操作。 在Java程序设计语言中，用接口表示栈的抽象数据类型如下。 interface IStack { int Count(); // 求栈的长度 boolean IsEmpty(); // 判断栈是否为空 void Clear(); // 清空操作 void Push(T item); // 入栈操作 T Pop(); // 出栈操作 T GetTop(); // 取栈顶元素 } 与线性表相同，栈也有两种存储方式： 顺序存储和链式存储。 视频讲解 3.2栈的顺序存储 3.2.1栈的顺序存储定义 将栈的数据元素存放在一组地址连续的存储单元中。假设每个元素占用l个存储单元，栈中第一个元素(即栈底元素)的存储地址是LOC(a1)=b，那么栈中最后一个元素(即栈顶元素)的存储地址是多少？ 栈中第一个元素的存储地址是b，第二个元素的存储地址是b+l，第三个元素的存储地址是b+2l，…，以此类推，第n个元素的存储地址是b+(n-1)l，如图34所示。栈的顺序存储结构简称顺序栈。 在Java语言的层面上讨论时，栈的顺序存储是将栈的数据元素自栈底至栈顶放在一维数组中。同时，附设一个top指示器指向栈顶元素，如图35所示。top的值就是栈顶元素在数组中的下标。也可以让top指示器指向栈顶元素的下一个位置。 图34栈中元素的存储地址 图35top指示器 3.2.2顺序栈基本操作分析 1. 进栈操作 进栈操作即插入元素e为新的栈顶元素。栈的插入操作是往栈顶位置插入(即表尾位置)，所以不需要移动数据元素，直接插入即可。 进栈操作的步骤如下： (1) 令top值加1。 (2) 令栈顶元素等于e。 进栈操作如图36所示。 图36进栈操作 2. 出栈操作 出栈操作即删除S的栈顶元素并返回其值。栈的删除操作是删除栈顶元素，所以不需要移动数据元素，直接删除即可。 出栈操作的步骤如下： (1) 令变量=栈顶元素。 (2) 令top值减1，并返回变量的值。 出栈操作如图37所示。 图37出栈操作 3.2.3顺序栈源码实现 1. 顺序栈类的实现 (1) 定义顺序栈类SeqStack，实现接口IStack。 public class SeqStack implements IStack (2) 创建顺序栈类SeqStack中的属性成员。 public class SeqStack implements IStack { public T［］ data; //数组，用于存储顺序栈中的数据元素 public int maxsize; //顺序栈的容量 public int top; //指示顺序栈的栈顶,值是栈顶元素在数组中的下标 } 关于属性成员的几点说明： ① Java语言中的数组在内存中占用的存储空间是一组地址连续的存储单元。因此，在Java虚拟处理器中考虑问题时，认为栈的顺序存储就是将栈的数据元素存放到数组中。 ② maxsize表示数组的容量。数组的容量可以用data的Length属性即data.length来表示，但为了说明顺序栈的最大长度(顺序栈的容量)，在SeqStack类中用字段maxsize来表示。 ③ top指示顺序栈的栈顶，值是栈顶元素在数组中的下标。 (3) 创建顺序栈类SeqStack的构造方法。 public SeqStack(int size) { data = (T［］)new Object［size］;; //类型为T、长度为size的数组存放栈中元素 maxsize = size; //栈的容量等于数组长度 top = -1; //空栈top的值为-1 } 2. 基本操作的实现 (1) 求顺序栈的长度。 由于数组是0基数组，即数组的最小索引为0，因此，顺序栈的长度就是栈中最后一个元素的索引top加1。 求顺序栈长度的算法实现如下。 public int Count(){ return top + 1; } (2) 清空操作。 清除顺序栈中的数据元素是指使顺序栈为空，此时top等于-1。 清空顺序栈的算法实现如下。 public void Clear() { top = -1; } (3) 判断顺序栈是否为空。 如果顺序栈的top为-1，则顺序栈为空，返回true； 否则，返回false。 判断顺序栈是否为空的算法实现如下。 public boolean IsEmpty(){ if (top == -1) return true; else return false; } (4) 判断顺序栈是否为满。 如果顺序栈为满，top等于maxsize-1，则返回true； 否则，返回false。 判断顺序栈是否为满的算法实现如下。 public boolean IsFull(){ if (top == maxsize - 1) return true; else return false; } (5) 入栈操作。 入栈操作是指在顺序栈未满的情况下，先使栈顶指示器top加1，然后在栈顶添加一个新元素。 入栈操作的算法实现如下。 public void Push(T item){ if(top == maxsize - 1){//栈满 System.out.println("Stack is full");//提示信息 return; } data［++top］ = item;//先使栈顶指示器top加1，然后在栈顶添加一个新元素 } (6) 出栈操作。 顺序栈的出栈操作是指在栈不为空的情况下，使栈顶指示器top减1。 出栈操作的算法实现如下。 public T Pop(){ T tmp ; //T类型tmp if (IsEmpty()){ throw new RuntimeException("栈为空，无法删除" ); } tmp = data［top］; //栈非空， tmp等于栈顶元素 top--; //栈顶指示器减1 return tmp; //返回tmp } (7) 取栈顶元素。 如果顺序栈不为空，则返回栈顶元素的值； 否则，返回特殊值，表示栈为空。 取栈顶元素操作的算法实现如下。 public T Getop(){ T tmp ; //T类型tmp if (IsEmpty()){ throw new RuntimeException("栈为空，无法删除" ); } tmp = data［top］; //栈非空， tmp等于栈顶元素 //没有栈顶指示器减1 return tmp; //返回tmp } 3.2.4Java基础类库中的顺序栈 Java语言的推出者设计开发了顺序栈类java.util.Stack，供应用程序员使用。在开发软件时，可以利用继承和覆盖技术在java.util.Stack的基础上开发新的顺序栈类，以便切合软件的实际功能需求。java.util.Stack中的部分构造和普通方法如表31和表32所示，读者可以结合java.util.Stack源代码与本书中的SeqStack栈比较。 表31构造方法及功能说明 构 造 方 法功 能 说 明 Stack()创建一个空堆栈 表32普通方法及功能说明 返回值类型普 通 方 法功 能 说 明 booleanempty()测试堆栈是否为空 Tpeek()查看堆栈顶部的对象，但不从堆栈中移除它 Tpop()移除堆栈顶部的对象，并作为此函数的值返回该对象 Tpush(T item)将数据元素压入堆栈顶部 intsearch(Object o)返回对象在堆栈中的位置，以1为基数 3.3栈的链式存储 3.3.1栈的链式存储定义 栈的另一种存储方式是链式存储，即将栈中的数据元素存放在一组任意的存储单元中，简称为链栈(linked stack)。链栈通常用单链表来表示， 图38链栈结点 它的实现是单链表的简化。因此，链栈结点的结构与单链表结点的结构相同，如图38所示。 由于链栈的操作只是在一端进行，因此为了操作方便，将栈顶设在链表的头部，并且不需要头结点。栈(a1，a2，a3，a4，a5，a6)的链式存储结构如图39所示。 图39链栈 3.3.2链栈源码实现 链栈用单链表来表示，其结点结构与单链表结点结构相同，因此这里仍然采用单链表中定义的结点类(Node)作为链栈中的结点类。 定义链栈泛型类LinkStack，实现接口IStack。在LinkStack类中，用字段top 表示栈顶结点地址。由于链栈的栈顶指示器不能指示栈的数据元素的个数，因此，在求链栈的长度时，必须将栈中的数据元素一个一个计数，每前进一步就将计数器增加1，直至到达栈底。这种算法的时间复杂度比较高，为此需要在LinkStack类中增设字段num 表示链栈中结点的个数，以牺牲空间效率换取求长度等操作时间效率的提高。 链栈泛型类LinkStack中的属性成员和构造方法如下。 public class LinkStack implements IStack{ public Node top;// 栈顶指示器 public int num;// 栈中结点的个数 // 构造器 public LinkStack(){ top = null; num = 0; } // 其他方法 } 在Java语言中，一个基本操作表现为类中的一个方法。LinkList类除了必须实现接口IListDS中的方法外，还可添加一些另外的成员方法。链栈基本操作的实现如下。 (1) 求链栈的长度。 num的大小表示链栈中数据元素的个数，通过返回num的值可以求链栈的长度。求链栈长度的算法实现如下。 public int GetLength() { return num; } (2) 清空操作。 清空操作是指清除链栈中的结点，使链栈为空。此时，栈顶指示器 top 等于 null,并且 num 等于0。清空链栈的算法实现如下。 public void Clear(){ top = null; num = 0; } (3) 判断链栈是否为空。 如果链栈的栈底指示器为null且num等于0，则链栈为空，返回true； 否则，返回false。判断链栈是否为空的算法实现如下。 public boolean IsEmpty(){ if ((top == null) && (num == 0)) return true; else return false; } (4) 入栈操作。 链栈的入栈操作是指在栈顶添加一个新结点，top指向新的结点，num加1，栈发生变化。入栈操作的算法实现如下。 public void Push(T item) { Node q = new Node(item); if (top == null) top = q; else { q.next = top; top = q; } ++num; } (5) 出栈操作。 出栈操作是指在栈不为空的情况下，先取出栈顶结点的值，然后将栈顶指示器指向栈顶结点的直接后继结点，使其成为新的栈顶结点，num 减 1，栈发生变化。 出栈操作的算法实现如下。 public T Pop() { if (IsEmpty()) { throw new RuntimeException("Stack is empty!"); } Node p = top; top = top.next; --num; return p.data; } (6) 取栈顶元素。 如果链栈不为空，则返回栈顶结点的值； 否则，抛出异常，栈不发生变化。 取栈顶元素操作的算法实现如下。 public T GetTop() { if (IsEmpty()) { throw new RuntimeException("Stack is empty!"); } return top.data; } 3.4栈的应用举例 由于栈结构具有后进先出的固有特性，因此栈成为程序设计的有力工具。本节讨论两个栈应用的典型示例。 视频讲解 3.4.1数制转换 十进制与其他数制的转换是计算机实现计算的基本问题，下面以十进制和八进制为例讲解如何转换。 1. 八进制转换为十进制 (2504)8(1348)10 该数制转换的运算过程如下。 (2504)8=4×80+0×81+5×82+2×83=4+0+5×64+2×512=4+320+1024 =(1348)10 怎样利用计算机来完成这个过程？ 要求： 输入一个任意八进制整数，打印输出与其等值的十进制数。 该过程实现较为简单，可以考虑利用堆栈实现。将八进制的各个数位依次入栈并出栈，出栈时乘以各个数位的权值，然后求加权和即可得到与其等值的十进制数。八进制转换为十进制的代码如下。 public static void OtoD() throws IOException { System.out.println("请输入八进制数,按Enter键结束："); char c; int n = 0; int dec = 0, i = 0; SeqStack s = new SeqStack(15); while ((c = (char) System.in.read()) != '＼r') { // 从键盘读取字符，遇到Enter键则跳出循环 s.Push(c - '0'); // 数字字符转换为整型数入栈 } while (!s.IsEmpty()) { n = s.Pop(); dec = dec + n*(int) Math.pow(8, i); i = i + 1; } System.out.println("转换的十进制数是：" + dec); } 2. 十进制转换为八进制 (1348)10(2504)8 该进制转换的运算过程如下。 NN div 8N mod 8 13481684 168210 2125 202 怎样利用计算机来完成这个过程？ 要求： 输入一个任意十进制整数，打印输出与其等值的八进制数。 计算过程： 从低位到高位顺序产生八进制的各个数位4、0、5、2。 输出： 从高位到低位输出各个数位2、5、0、4。 这个过程符合后产生先输出的原则，可以考虑利用堆栈实现，具体代码如下。 public static void DtoO() { int n; System.out.println("请输入要转换的十进制数："); Scanner reader = new Scanner(System.in); // 实例化Scanner类对象reader // 调用reader对象的相应方法，读取键盘数据 n = reader.nextInt(); SeqStack s = new SeqStack(15); // 产生的各个余数位依次入栈 while (n > 0) {// 商等于0时退出循环 s.Push(n % 8); // 余数位入栈 n = n / 8; // 整型数相除，结果只保留整数 } // 输出栈中元素，最后产生的余数位最先输出 System.out.println("转换的八进制数是："); while (!s.IsEmpty()) { n = s.Pop(); System.out.print(n); } reader.close(); } 3.4.2表达式求值 表达式求值是程序设计语言编译中的一个基本问题，其实现是栈应用的又一典型示例。 在Java语言中，任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。运算符和界限符合称算符。例如，算术表达式(4+2)×3-9/5由操作数4、2、3、9、5，运算符+、-、×、/，界限符(、)组成。 为了叙述简洁，本书仅讨论简单算术表达式的求值问题，这种算术表达式只含加、减、乘、除4种运算符，操作数是一位整数，读者不难由此推广到更一般的表达式上。简单算术表达式的运算规则如下。 (1) 先乘除，后加减。 (2) 同级运算时先左后右。 (3) 先括号内，后括号外。 根据上述3条规则，任意两个相继出现的运算符θ1和θ2之间的优先关系如表33所示，其中“#”是表达式结束符。 表33运算符间的优先关系 θ1 θ2+-×/()# +>><<<>> ->><<<>> ×>>>><>> />>>><>> (<<<<<=无 )>>>>无>> #<<<<<无= θ1和θ2之间的优先关系通常为如下3种关系。 (1) θ1<θ2： θ1的优先权低于θ2。 (2) θ1=θ2： θ1的优先权等于θ2。 (3) θ1>θ2： θ1的优先权高于θ2。 在表33中，θ1和θ2是相继出现的，先出现θ1，后出现θ2。θ1和θ2可以是同一运算符。如果θ1和θ2都是两个加号，则第一个加号的优先权高。先做第一个加法运算，再做第二个加法运算。 在表33中，“#”是表达式结束符，为了算法简洁，在表达式的最左边也虚设一个“#”构成表达式的一对括号。表中的“(”=“)”表示当左、右括号相遇时，括号内的运算已完成，同理“#”=“#”表示整个表达式求值完毕。表中的3处“无”表示在表达式中不允许它们相继出现，一旦遇到这种情况，表示出现了语法错误。在下面的讨论中，假设输入的表达式不会出现语法错误。 在处理表达式前，需要先设置两个栈。 (1) 操作数栈(OPRD)存放处理表达式过程中的操作数。 (2) 运算符栈(OPTR)存放处理表达式过程中的运算符。开始时，在运算符栈中的栈底压入一个表达式的结束符“#”。 在处理表达式时，从左到右依次读出表达式中的各个符号(操作数或运算符)，每读出一个符号后，根据运算规则进行如下处理。 (1) 假如是操作数，则将其压入OPRD，并依次读下一个符号。 (2) 假如是运算符，则令θ1＝OPTR栈顶运算符，θ2＝读出的运算符。根据θ1和θ2关系的不同，分以下3种情况分别处理。 ① θ1<θ2： θ2入OPTR。 ② θ1=θ2： θ1出OPTR，处理θ2之后的下一运算符。 ③ θ1>θ2： θ1出OPTR，操作数出OPRD，计算aθ1b，计算结果入操作数栈，重新处理θ2。 其中，b为先出OPRD的操作数，a为后出OPRD的操作数。 (3) OPRD中剩下的数就是计算结果。 【例31】写出求解表达式#4+3×5#时的堆栈变化情况。 分析： 表达式的求解步骤如下。 (1) #入OPTR，剩余表达式部分为4+3×5#。 (2) 4入OPRD，剩余表达式部分为+3×5#。 (3) 因#<+，+入OPTR，剩余表达式部分为3×5#。 (4) 3入OPRD，剩余表达式部分为×5#。 (5) 因+<×，×入OPTR，剩余表达式部分为5#。 (6) 5入OPRD，剩余表达式部分为#。 (7) 因×>#，×出OPTR，5和3出OPRD，计算3×5=15，15入OPRD，继续处理#。 (8) 因+>#，+出OPTR，15和4出OPRD，计算4+15=19，19入OPRD，继续处理#。 (9) 因#=#，#出OPTR。此时，表达式求值完毕。返回Getop(OPRD)，即19。 堆栈变化情况如表34所示。 表34求解表达式#4+3×5#时的堆栈变化情况 步骤OPTROPRD剩余表达式部分 (1)#4+3×5# (2)#4+3×5# (3)#，+4，3，53×5# (4)#，+4，3×5# (5)#，+，×4，35# (6)#，+，×4，3，5# (7)#，+4，15# (8)#19# (9)19 算术表达式求值的算法实现如下。 public static int EvaluateExpression() { SeqStack optr = new SeqStack(20); SeqStack opnd = new SeqStack(20); optr.Push('#'); char c = (char) System.in.read(); char theta = ' '; int a = 0; int b = 0; while (c != '#') { if ((c != '+') && (c != '-') && (c != '*') && (c != '/') && (c != '(') && (c != ')')) { optr.Push(c); } else { switch (Precede(optr.Getop(), c)) { case '<': optr.Push(c); c = (char) System.in.read(); break; case '=': optr.Pop(); c = (char) System.in.read(); break; case '>': theta = optr.Pop(); a = opnd.Pop(); b = opnd.Pop(); opnd.Push(Operate(a, theta, b)); break; } } } return opnd.Getop(); } 上述算法调用了两个方法。其中，Precede是判定optr栈顶运算符与读入运算符之间的优先级关系的方法，Operate是进行二元运算的方法。这两个方法读者可作为练习自行实现。 视频讲解 3.5队列的基本概念 3.5.1队列的相关定义 1. 队列 队列(queue)是一种只允许在表尾端进行插入，在表头端进行删除的线性表。 插入数据元素时，新插入的数据元素e只能处于线性表的表尾，如图310所示。 删除数据元素时，只能删除线性表的表头元素，如图311所示。 图310插入数据元素 图311删除数据元素 2. 队头和队尾 队头(front)即表头，队尾(end)即表尾。 3. 入队列和出队列 入队列是队列的插入操作，出队列是队列的删除操作。 4. FIFO 队头元素a1是最先进队列的，也是最先出队列的； 队尾元素an是最后进队列的，因而也是最后出队列的。因此，队列也被称为“先进先出”(First In First Out,FIFO)线性表。 3.5.2队列的抽象数据类型 ADT Queue{ 数据对象: D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系： R={|ai-1,ai∈D,i=2,…,n} 基本操作P： (1) int Count()： 求队列的长度。 操作结果： 返回队列中数据元素的个数。 (2) boolean IsEmpty()： 判断队列是否为空。 操作结果： 如果队列为空，则返回TRUE； 否则，返回FALSE。 (3) Clear()： 清空操作。 操作结果： 使队列为空。 (4) In(T item)： 入队列操作。 操作结果： 将值为item的新数据元素添加到队尾，队列发生变化。 (5) T Out()： 出队列操作。 初始条件： 队列不为空。 操作结果： 将队头元素从队列中取出，队列发生变化。 (6) T GetFront()： 取队头元素。 初始条件： 队列不为空。 操作结果： 返回队头元素的值，队列不发生变化。 } 关于队列抽象数据类型中D的说明： D是n个数据元素的集合，D是ElemSet的子集。ElemSet表示某个集合，集合中的数据元素类型相同，如整数集、自然数集等。 关于队列抽象数据类型中R的说明： R是数据元素之间关系的集合，表示ai-1和ai之间互为前驱和后继的逻辑关系。约定an端为队尾，a1端为队头。 队列的数据对象和数据关系与线性表是相同的。 关于队列抽象数据类型中基本操作的说明： (1) 队列中的数据元素类型用T表示，T可以是原子类型，也可以是结构类型。整型用int表示，逻辑型用boolean表示。 (2) 队列的基本操作是定义于逻辑结构上的基本操作，是向使用者提供的使用说明。基本操作只有在存储结构确定之后才能实现。如果队列采用的存储结构不同，则队列的基本操作实现算法也不相同。 (3) 基本操作的种类和数量可以根据实际需要决定。但是，队列是操作受限的线性表，不能任意地定义基本操作。例如，不能在队列的第i个位置插入数据元素。 (4) 基本操作名称，形式参数数量、名称、类型，返回值类型等由设计者决定。使用者根据设计者的设计规则使用基本操作。 在Java程序设计语言中，用接口表示队列的抽象数据类型如下。 interface IQueue { int Count();// 求队列的长度 boolean IsEmpty(); // 判断队列是否为空 void Clear(); // 清空操作 void In(T item); // 入队列操作 T Out(); // 出队列操作 T GetFront(); // 取队头元素 } 与线性表相同，队列也有两种存储方式： 顺序存储和链式存储。 3.6队列的链式存储 3.6.1队列的链式存储定义 队列的链式存储是指将队列的数据元素存放在一组任意的存储单元中(编号可以不连续)。队列的链式存储结构简称链队列。 由于数据的存储没有规律，无法根据当前元素的地址算出它的后继元素的地址，因此无法确定它的后继元素。必须在数据元素后面附设一个引用，作为后继元素的地址。 队列q=(a1，a2,…,an)的链式存储结构如图312所示。 图312链队列 与线性表相同，为了操作方便，一般在第一个结点之前增加一个头结点。带头结点的链队列如图313所示。 图313带头结点的链队列 头结点的类型与其他结点一样，分为数据部分和引用部分。头结点的数据部分为空，引用部分指向链队列的第一个数据元素结点。 只要知道头结点的地址，就能“顺藤摸瓜”确定队列的每一个数据元素。头结点的地址用front来表示，称front为队头引用。 因为队列的插入操作都是在队尾进行的，为了提高插入操作的效率，附设一个引用rear指示队尾元素的地址，称rear为队尾引用。以数据的冗余换取入队操作时间效率的提高。带尾引用的链队列如图314所示。 图314带尾引用的链队列 本教材链队列基本操作的实现指的是带尾引用的链队列基础上实现的。 视频讲解 3.6.2链队列基本操作分析 1. 出队列 出队列即删除队列的第一个数据元素，令头结点的引用指向第二个结点，如图315所示。 图315出队列操作 2. 入队列 入队列即插入e为队列新的队尾元素，其操作步骤如下。 (1) 建立新结点s，数据部分是e，引用部分为NULL。 (2) an引用指向结点s。 (3) 队尾引用rear指向结点s。 入队列操作如图316所示。 图316入队列操作 视频讲解 3.6.3链队列源码实现 链队列用单链表来表示，其结点结构与单链表结点结构相同，因此这里仍然采用单链表中定义的结点类(Node)作为链队列中的结点类。 定义链队列泛型类LinkQueue,实现接口IQueue。 本书用队头引用和队尾引用的组合来表示队列，即LinkQueue类中有两个引用front和rear。 链队列泛型类 LinkQueue中的属性成员和构造方法如下。 public class LinkQueue implements IQueue { // 链队列类LinkQueue public Node front; // 队头指示器 public Node rear; // 队尾指示器 // 无参构造器 ，构造了一个只有头结点的空队列 public LinkQueue() { front = rear = new Node(); // 头结点数据域等于T类型默认值，引用域为空 } //其他方法 } 在Java语言中，一个基本操作表现为类中的一个方法。LinkList类除了必须实现接口IQueue中的方法外，还可添加一些另外的成员方法。链队列基本操作的实现如下。 (1) 求链队列的长度。 从队头引用开始，一个结点一个结点地计数，直到队尾。求链队列长度的代码如下。 public int Count() { Node p = front; // 新建结点p等于头引用 int len = 0;// len值初始化为0 while (p != null) { ++len; p = p.next; } // 此循环执行完毕后， len值为链表结点的个数(包含头结点) return len - 1; // 链表结点的个数减1即为队列的元素个数 } (2) 清空操作。 清空操作是指清除队列中的结点，使队列为空。当队列为空时，头引用front.next等于null，rear等于front。清空操作如图317所示，具体代码如下。 public void Clear() { front.next = null; // 令头引用front.next等于null rear = front; } 图317清空操作 (3) 判断链队列是否为空。 队列非空和空的状态如图318所示。如果链队列的队头指示器等于队尾指示器，则表示链队列为空，返回true； 否则,返回false。判断链队列是否为空的代码如下。 public boolean IsEmpty() { if (front == rear) return true; else return false; } 图318队列非空和空状态示意图 当队列为空时，队头指示器front的引用域为空，代码也可以写成如下形式。 public boolean IsEmpty() { if (front.next == null) return true; else return false; } (4) 入队操作。 链队列的入队操作是指在队尾添加一个新结点，队尾指示器rear指向新的结点。入队操作的算法实现如下。 public void In(T item) { Node q = new Node(item); // 建立新结点q rear.next = q; // 最后一个结点的引用域指向新结点 rear = q; // rear指向新的结点 } (5) 出队操作。 出队操作是指在链队列不为空的情况下，将第1个元素出队列。链队列头结点的引用域指向第二个结点，队列发生改变。 如果队列中只有一个元素，则出队列后队列为空，此时需要修改尾引用指向头结点。 出队操作的算法实现如下。 public T Out() { if (IsEmpty()) { throw new RuntimeException("队列为空，无法删除"); } Node p = front.next; // p指向第一个结点 front.next = p.next; // 头引用的next域指向第二个结点 if(Count()==0) rear=front; //如果元素出队列后，队列变为空状态，则修改尾引用 return p.data; // 返回第一个结点的数据 } (6) 获取链队列头结点的值。 如果链队列不为空，则返回链队列第一个结点的值； 否则，返回提示信息，表示队列为空，队列不发生改变。获取链队列头结点的值的算法实现如下。 public T GetFront() { if (IsEmpty()) { throw new RuntimeException("队列为空，无法获取"); } Node p = front.next; // p指向第一个结点 return p.data; // 返回第一个结点的数据 } 3.7队列的顺序存储 3.7.1队列的顺序存储定义 队列的顺序存储是指将队列的数据元素存放在一组地址连续的存储单元中，在Java语言中就是将数据元素存放在一维数组中。由于队列的删除位置只能是队列的第一个位置，因此为了避免删除数据元素时大量地移动数据元素，附设一个front指示队头元素在数组中的下标，同时附设一个整型的rear指示队尾元素在数组中的位置，其值等于队尾元素在数组中的下标加1。队列的顺序存储结构简称为顺序队列。 队列(J1,J2,J3)的顺序存储结构如图319所示，其中front=0,rear=3。 空队列如图320所示，其中rear=front=0。 图319队列(J1,J2,J3)的顺序存储结构 图320空队列 视频讲解 3.7.2顺序队列基本操作分析 1. 入队操作 顺序队列入队操作是指在rear处插入元素，然后将rear值加1，如图321所示。 图321入队列 2. 出队操作 顺序队列出队操作是指删除front处的队头元素，即队头指示器front加1，如图322所示。 经过若干插入、删除操作之后，某一时刻队列的状态如图323所示。 图322出队列 图323某一时刻队列的状态 此时,队尾rear已经指向了数组的最后一个位置，若再有元素入列，则会导致“溢出”，即元素下标超出队尾rear的最大值。在图323中，虽然队尾rear已经指向了最后一个位置，但事实上数组中还有空位置。也就是说，数组的存储空间并没有满，但队列却发生了溢出，将这种现象称为假溢出。如何处理假溢出？正确的做法是： 将数组的空间想象成一个环状的空间，将第0个位置看成是最后一个位置的下一位置。在第5个位置插入数据元素J6后，rear指向第0个位置，如图324所示。 如果J7需要入队列，则在第0个位置插入数据元素J7后，rear后移并指向第1个位置，如图325所示。此时，队列的逻辑结构是(J4，J5，J6，J7)。 顺序队列中的rear和front达到最大值后都可以从0重新开始循环，所以顺序队列又称为循环顺序队列，简称为循环队列。 循环队列存在一个问题： 队满和队空的标志均为front=rear，如图326所示，如何区分队满和队空？ 解决方案： 少用一个空间，当队列中的元素个数达到数组的长度减1时，就标志队列已满，数据元素不能再入队列了，如图327所示。 图324rear指向第0个位置 图325rear指向第1个位置 图326队满和队空(无法区分) 图327队满和队空(可区分) 视频讲解 3.7.3循环顺序队列源码实现 1. 循环顺序队列类的实现 (1) 定义循环顺序队列类CSeqQueue，实现接口IQueue。 public class CSeqQueue implements IQueue (2) 创建循环顺序队列类CSeqQueue 中的属性成员。 public class CSeqQueue implements IQueue { public T［］ data; //数组，用于存储队列中的数据元素 public int maxsize; public int front; //队头，front的变化范围是0~maxsize-1 public int rear; //队尾，rear的变化范围也是0~maxsize-1 } 关于属性成员的几点说明： ① Java语言中的数组在内存中占用的存储空间就是一组地址连续的存储单元，因此，在Java虚拟处理器中考虑问题时，认为队列的顺序存储就是将队列的数据元素存放到数组中。 ② maxsize表示数组的容量。 ③ 队头front的变化范围是0~maxsize-1，队尾rear的变化范围也是0~maxsize-1。 (3) 创建循环顺序队列类CSeqQueue的构造方法。 public CSeqQueue(int size) { data = (T［］) new Object［size］; maxsize = size; front = rear = 0; } 2. 基本操作的实现 (1) 求顺序队列的长度。 ① rear>front，如图328(a)所示。此时，循环顺序队列的长度为rear-front。 ② 当rear到达数组的上限后又从数组的底端开始，rearfront时(见图329(a))，如果循环顺序队列为满，则有(rear+1)% maxsize==front成立。 ② 当rear s = new SeqStack(50);// 建立堆栈s CSeqQueue q = new CSeqQueue(50); // 建立队列q System.out.println("请输入字符串,按Enter键结束"); char c; while ((c = (char) System.in.read()) != '＼r') { // 从键盘读入字符，遇到Enter键则跳出循环 s.Push(c); // 字符入栈 q.In(c); // 字符入队列 } while (!s.IsEmpty() && !q.IsEmpty()) { // 队列和栈均不空，进行以下比较 if (s.Pop() != q.Out()) { // 出栈和出队列元素不相等，退出循环 break; } } if (!s.IsEmpty() && !q.IsEmpty()) { // 栈或队列非空，是从break语句退出循环 System.out.println("这不是回文!"); } else { // 栈和队列均为空，不是从break语句退出循环 System.out.println("这是回文!"); } } 本章小结 本章内容分成两大部分： 栈和队列。栈和队列均是操作受限的线性表。第一部分首先介绍了栈的基本概念和抽象数据类型栈； 然后介绍了栈的两种存储结构： 顺序栈和链栈，基于顺序栈和链栈实现了抽象数据类型栈中的基本操作，并介绍了Java基础类库中的顺序栈java.util.Stack的部分代表性方法的功能，供读者分析比较； 最后讲了栈的应用，利用栈实现了数制转换和表达式求值。第二部分首先介绍了队列的基本概念和抽象数据类型队列； 然后介绍了队列的两种存储结构： 带尾引用的单向链队列和循环顺序队列，基于链队列和循环顺序队列实现了抽象数据类中队列中的基本操作，并介绍了Java基础类库中java.util.Queue接口的部分方法及实现该接口的类，供读者分析比较； 最后讲了队列的应用，综合利用队列和栈判断一个字符串是否为回文。 在线测试 习题3 一、 选择题 1. 若一个栈的输入序列是1，2，3，…，n，且输出序列的第一个元素是n，则第k个输出元素是()。 A. kB. n-k-1C. n-k+1D. 不确定 2. 栈与队列都是()。 A. 链式存储的线性结构B.链式存储的非线性结构 C. 限制存取点的线性结构D.限制存取点的非线性结构 3. 在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个()结构。 A. 堆栈B. 队列C. 数组D. 线性表 4. 循环队列的队头和队尾引用分别为front和rear，判断一个循环队列Q(最多n个元素)为满的条件是()。 A. Q.rear==Q.frontB. Q.rear==Q.front+1 C. Q.front==(Q.rear+1)%n D. Q.front==(Q.rear-1)%n 5. 假设用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为()。 A. 1和5B. 2和4C. 4和2D. 5和1 6. 队列的插入操作是在()。 A. 队尾B. 队头 C. 队列任意位置D. 队头元素后 7. 循环队列的队头和队尾引用分别为front和rear，则判断循环队列为空的条件是()。 A. front==rearB. front==0 C. rear==0D. front=rear+1 8. 假设有一个顺序栈S，其栈顶引用为top，则将元素e入栈的操作是()。 A. S.top=e;S.top++B. S.top++;S.top=e C. S.top=eD. S.top=e 9. 栈的插入和删除操作在()。 A. 栈底B. 栈顶C. 任意位置D. 指定位置 10. 判定一个顺序栈S(栈空间大小为n)为空的条件是()。 A. S.top==0B. S.top!=0 C. S.top==nD. S.top!=n 11. 在一个链队列中，front和rear分别为头引用和尾引用，则插入一个结点s的操作为()。 A. front=front.next B. s.next=rear;rear=s C. rear.next=s;rear=sD. s.next=front;front=s 12. 若一个队列的入队序列是1，2，3，4，则队列的出队序列是()。 A. 1，2，3，4B. 4，3，2，1 C. 1，4，3，2D. 3，4，1，2 13. 当用大小为N的数组存储顺序循环队列时，该队列的最大长度为()。 A. NB. N+1C. N-1D. N-2 14. 队列的删除操作是在()。 A. 队首B. 队尾C. 队前D. 队后 15. 循环队列用数组A［0..m-1］存放其元素值，已知其头尾引用分别是front和rear，则当前队列中的元素个数是()。 A. (rear-front+m)%mB. rear-front+1 C. rear-front-1D. rear-front 16. 在一个链队列中，假设front和rear分别为队头引用和队尾引用，则删除一个结点的操作是()。 A. front=front.nextB. rear=rear.next C. rear.next=frontD. front.next=rear 17. 队列和栈的主要区别是()。 A. 逻辑结构不同B. 存储结构不同 C. 所包含的运算个数不同D. 限定插入和删除的位置不同 二、 填空题 1. 栈是限定在一端进行插入或删除操作的线性表。在栈中，允许插入和删除操作的一端称为，而另一端称为。不含元素的栈称为。 2. 在栈的运算中，栈的插入操作称为，栈的删除操作称为。 3. 根据栈的定义，每一次进栈的元素都在原栈顶元素之上，并成为新的； 每一次出栈的元素总是当前的，最后进栈的元素总是最先出栈。因此，栈也称为后进先出线性表，简称为表。 4. 栈是一种操作受到限制的线性表，是一种特殊的线性表。因此，栈也有和两种存储结构，分别称为和。 5. 队列也是一种特殊的线性表。在队列中，允许插入的一端称为，允许删除的一端称为。 6. 已知栈的输入序列为1，2，3，…，n，输出序列为a1，a2，…，an，符合a2= =n的输出序列的个数为。 7. 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q。若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是。 8. 设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为。 三、 判断题 1. 栈和队列都是限制存取点的线性结构。() 2. 不同的入栈和出栈组合可能得到相同的输出序列。() 3. 循环队列是顺序存储结构。() 4. 当循环队列满时，rear==front。() 5. 在对链队列(带头结点)进行出队操作时，不会改变front引用的值。() 四、 综合题 1. 设有4个元素A、B、C和D进栈，试给出它们所有可能的出栈顺序。 2. 假设以带头结点的循环链表表示队列，只设一个引用指向队尾结点，且不设头引用，请写出图330相应的入队列算法。 图330习题4.2图 五、 实验题 1. 编写程序，从键盘输入一个十进制数，输出与其等值的八进制数。 2. 编写程序，利用栈和队列实现判断一个字符串是否为回文。