入栈，头插入，list.insert(0,x); O(1)list.heada0?an-1∧list.heada0入栈，尾插入，list.insert(x); O(n)?an-1∧
出栈，头删除，list.remove(0); O(1)（a） 头插入和头删除出栈，尾删除，list.remove(list.size()-1); 两次遍历，O(n)（b） 尾插入和尾删除图4.2 使用单链表对象作为栈成员变量的操作效率分析
③ 使用一个循环单链表、双链表或循环分析省双链表对象作为栈的成员变量，入栈和出栈操作效率省略。
（4） 栈的应用
4-5 写出中缀表达式A+B*(C-D*(E+F)/G+H)-(I+J)*K对应的后缀表达式。
【答】ABCDEF+*G/-H+*+IJ+K*-
4.2 队列
1. 队列 （1） 队列定义
4-6 什么是队列？有何特点？说明在什么情况下需要使用队列。
【答】队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。队列的特点是“先进先出”。广度优先搜索遍历算法需要使用队列作为辅助结构。
4-7 已知入队序列为{A,B,C,D}，有几种出队序列？ 【答】一种{A,B,C,D}。 （2） 队列的实现方案讨论
4-8 能否使用一个线性表作为队列，或将队列声明为继承线性表？为什么？
【答】都不能。因为队列和线性表是不同的抽象数据类型，队列不支持中间插入和删除操作。
① 如果使用一个线性表对象作为队列，有逻辑错。例如：
SeqList
queue.insert(i,x); //语法正确，逻辑错，因线性表支持中间插入操作，但队列不支持
② 如果声明队列为继承线性表如下，则队列类继承了顺序表类的
- 38 -
isEmpty()、insert(i,x)、remove(i)等成员方法，而队列不支持中间插入和删除操作。
public class SeqQueue
public class LinkedQueue
4-9 使用一个顺序表对象作为顺序队列的成员变量，分析入队、出队操作的时间效率。
【答】见教材第98页图4.11。
4-10 什么是队列的假溢出？为什么顺序队列会出现假溢出？怎样解决队列的假溢出问题？顺序栈会出现假溢出吗？链式队列会出现假溢出吗？为什么？
【答】① 顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序队列设计成循环结构。
② 顺序栈不会出现假溢出。因为顺序栈的存储单元可以重复使用，如果数组容量不够，则是数据溢出，而不是假溢出。
③ 链式队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。
4-11 使用一个链式存储的线性表对象作为链式队列的成员变量，分析入队、出队操作的时间效率。
【答】见教材第100页图4.14。
2. 优先队列
习4-13 已知一个对象由“(关键字,优先级)”表示，对象序列如下，画出将这些对象依次全部进队的结果图，分别使用一个顺序表、排序顺序表、单链表、排序单链表、循环双链表、排序循环双链表作为优先队列的成员变量，讨论优先队列的入队和出队操作的效率。
{(E,4),(D,3),(A,1),(F,3),(B,2),(C,1)}
【答】如图4.1所示，设优先队列长度为n。
(a) 使用顺序表作为成员变量，入队操作执行顺序表尾插入，时间
- 39 -
复杂度是O(1)；出队操作执行中间删除，顺序查找首个优先级最高元素并将其删除，求最大值算法需要遍历顺序表，时间复杂度是O(n)，平均移动n/2个元素。
(b) 使用排序顺序表作为成员变量，元素按优先级升序排序，队头元素优先级最高，入队操作执行顺序表中间插入，顺序查找根据优先级确定元素的插入位置，移动若干元素，时间复杂度是O(n)；出队操作执行顺序表头删除，时间复杂度是O(n)。
(c) 使用单链表作为成员变量，入队操作执行单链表尾插入，时间复杂度是O(n)；出队操作执行中间删除，顺序查找优先级最高的元素并将其删除，时间复杂度是O(n)。
(d) 使用排序单链表作为成员变量，元素按优先级升序排序，队头元素优先级最高，入队操作执行单链表中间插入，顺序查找根据优先级确定元素的插入位置，时间复杂度是O(n)；出队操作执行单链表头删除，时间复杂度是O(1)。
(e) 使用循环双链表作为成员变量，入队操作执行循环双链表尾插
入，时间复杂度为O(1)；出队操作执行中间删除，时间复杂度是O(n)。
(f) 使用排序循环双链表作为成员变量，入队操作执行中间插入，时间复杂度是O(n)；出队操作执行循环双链表头删除，时间复杂度是O(1)。
- 40 -
序号01?n-1?length-1顺序表list(E,4)(D,3)(A,1)(F,3)(B,2)(C,1)入队，尾插入，O(1)出队，查找到尾再中间删除，O(n)（a）使用顺序表作为成员变量序号01?n-1?length-1排序顺序表list(A,1)(C,1)(B,2)(D,3)(F,3)(E,4)出队，头删除，O(n)（b）使用排序顺序表作为成员变量head(E,4)(D,3)(A,1)(F,3)(B,2)(C,1)∧入队，尾插入，O(n)入队，中间插入，O(n)出队，查找到尾再中间删除，O(n)（c）使用单链表作为成员变量head(A,1)出队，头删除，O(1)（d）使用排序单链表作为成员变量head入队，尾插入，O(1)(E,4)(D,3)(A,1)(C,1)(B,2)(D,3)(F,3)
(E,4)∧入队，中间插入，O(n)(F,3)(B,2)(C,1)出队，查找到尾再中间删除，O(n)（e）使用循环双链表作为成员变量head(A,1)出队，头删除，O(1)(C,1)(B,2)(D,3)入队，中间插入，O(n)(F,3)(E,4)（f）使用排序循环双链表作为成员变量图4.3 使用各种线性表对象作为优先队列成员变量的操作效率比较
综上所述，出队时间是O(1)的优先队列有两种，分别使用排序单链表和排序循环双链表，前者仅支持按优先级升序排序，后者支持升序和降序。
4.3 递归
【习4.1】 打印数字塔。
打印如下形式的数字塔：
1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 5 6 5 4 3 2 1
- 41 -
1 2 3 4 5 6 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 题目本身虽不是递归定义的，但可以用递归算法求解。程序如下：
public class DigitTower {
public static void i,int n) line(int //输出一行，递归方法
{ System.out.print(String.format(\ if (i { line(i+1,n); System.out.print(String.format(\ } } public static void main(String args[]) { int n=9; for(int i=1; i<=n; i++) { System.out.print(String.format(\')); //前导空格 line(1,i); System.out.println(); } } } - 42 -