1、综述

1.1 数据结构和算法能起到什么作用？

• 现实世界的数据存储
• 程序员的工具
• 建模

1.2 数据结构的概述

1.3 算法的概述

对于大多数数据结构来说，都需要知道

• 插入一条新的数据项
• 寻找某一特定的数据项
• 删除某一特定的数据项

还需要知道如何迭代的访问某一数据结构中的各项数据，以便进行显示或其他操作。
另外一个重要的算法范畴是排序，排序有很多算法。
递归的概念在设计某些算法时十分重要。

1.4 面向对象编程

• 1.4.1 过程性语言的问题

  面向对象编程语言产生的由于发现过程性语言（诸如C）在处理大型复杂的问题时有些力不从心，主要表现为：

  • 程序与现实世界缺乏对应关系（对现实世界建模无能为力）
  • 程序内部结构出现问题（粗糙的组织结构）

• 1.4.2 对象简述

  将计算机中的事物与现实世界中的事物紧密联系在一起，解决了过程语言中有全局变量造成的麻烦。

2、数组

2.1 Array专题Applet

假设你正在训练少儿棒球联盟的队伍，并且希望知道队中的哪些运动员出现在训练场上，就需要在笔记本上存有一个出勤记录程序，它可以维护参与训练的运动员的数据库。需要用一个简单的数据结构对这些数据进行保存，还可能需要执行以下这些操作：

• 当运动员到场时，向数据结构中插入一条记录。

• 通过在数据结构中查找运动员的号码来查看某个运动员是否出席。

• 当运动员退场时，从数据结构中删除一条记录。

• 插入

新的数据项总是插在数组的第一个空位置上，并且由于数组中已有数据项个数已知，所以算法知道这个控制的具体位置。

• 查找

查找算法（不允许重复数据项）必须平均搜索一半的数据项来查找特定数据值。找数据头部数据较快，找数据尾部数据较慢。假设数据项个数为N，则一个数据项的平均查找长度为N/2。在最坏的情况下，这需要N步才能找到。

• 删除

删除算法暗含一个假设，即数组中不允许有洞。洞值的是一个或几个空单元，后面还有非空数据项（在更高的下标处还有数据项）。如果删除算法中允许有洞，那么算法会更加复杂，以为在查看某一单元的数据项之前还需要判断它是否为空。同样，算法会由于需要找到非空数据项而变得效率更低。因此，非空数据必须连续存储，不能有洞。
删除（不允许重复数据项）需要查找N/2个数据项并平均移动剩下N/2个数据项来填充删除带来的洞。总共是N步。

重复值问题

• 插入

与数据项不可重复插入算法完全一致：插入新数据项只需一步。但需要注意，即使数据项不允许重复，用户也有可能输入相同的关键字，因此插入之前需要先检查已有的数据项。

• 查找

需要N步。

• 删除

本书的applet删除采用第二种含义，将所有相同的数据项都删除。这需要检查N个数据项和移动多于N/2个数据项，这个操作的平均时间依赖于重复数据项在整个数据中的分布。

通常认为N和N/2之间的差异不很重要，除非正在对程序进行微调以达到最优。最重要的是操作是否需要执行1步、n步、log(n)、或n^2。

需要注意一件事情：算法的缓慢和有条不紊的本质特征。除了插入之外，其他算法都需要涉及到一些或者数组所有的数据项。另一些数据结构有更快（更复杂）的算法。

2.2 Java数组中的基础知识

略

2.3 将程序划分为类

略

2.4 类接口

略

2.5 Order专题Applet

为什么要将数据按顺序排列，好处之一就是可以通过二分查询显著地提高查找效率。

猜数游戏

如果是线性查找，从1开始，然后一次是2、3，等等，找到这个数据需要平均猜测50次。在二分查找中，每猜测一次，将可能得值划分为两部分。因此猜测的次数大大减少。表2.2显示了答案为33的游戏过程。

可以看到插入和删除也可以使用二分查找（当它被选中时），由二分查找确定插入和删除的位置。

2.6 有序数组的Java代码

public class OrderArray {private int[] a;private int nElems;public OrderArray(int max) {a = new int[max];nElems = 0;}public int size() {return nElems;}public int find(int searchKey) {int lowerBound = 0;int upperBound = nElems -1;int curIn;while (true) {curIn = (lowerBound + upperBound)/2;if (a[curIn] == searchKey) {return curIn;} else if (lowerBound > upperBound) {return nElems;} else {if (a[curIn] < searchKey) {lowerBound = curIn + 1;} else {upperBound = curIn - 1;}}}}public void insert(int value) {int j;for(j = 0; j < nElems; j++) {if (a[j] > value) {break;}}for(int k = nElems; k > j; k--) {a[k] = a[k-1];}a[j] = value;nElems++;}public boolean delete(int value) {int j = find(value);if (j == nElems) {return false;} else {for(int k = j ; k < nElems; k++) {a[k] = a[k+1];}nElems--;return true;}}public void display() {for (int i = 0; i < nElems; i ++) {System.out.println(a[i]);}}
}public class OrderApp {public static void main(String[] args) {int maxSize = 100;OrderArray arr;arr = new OrderArray(maxSize);arr.insert(77);arr.insert(99);arr.insert(44);arr.insert(55);arr.insert(22);arr.insert(88);arr.insert(11);arr.insert(00);arr.insert(66);arr.insert(33);int searchKey = 55;if (arr.find(searchKey) != arr.size()) {System.out.println("Found " + searchKey);} else {System.out.println("Can't find " + searchKey);}arr.display();arr.delete(00);arr.delete(55);arr.delete(99);arr.display();}
}

有序数组的优点：

使用有序数组会给我们带来什么好处？最主要的好处是查找的速度比无序数组快多了。不好的方面是在插入操作中由于所有靠后的数据都需要移动以腾出空间，所以速度较慢。有序数组和无序数据的删除操作都很慢，这是因为数据线必须往前移动来填补已删除数据项的洞。
有序数组在查找频繁的情况下非常有用，但若是插入和删除操作频繁时，则无法高效的工作。例如，有序数组适合公司雇员的数据库。雇佣和解雇雇员同读取一个已存在雇员有关信息或更改薪水、住址等信息比，前两者是不经常发生的。另一方面，零售商店的存货清单不适用有序数组来实现，这是因为频繁的进出货对应的插入与删除操作都会执行比较慢。

2.7 对数

略
通过数学归纳法推导出二分查找的时间复杂度为log2^n。

2.8 存储对象

略

2.9 大O表示法

我们通常需要一种快捷的方法来评价计算机算法的效率。在计算机科学中，这种粗略的度量方法被称为大O表示法。
我们所需的是一个可以描述算法速度是如何与数据项的个数相联系的比较。下面是目前我们所见过的算法的大O表示。

• 无序数组的插入 常数
• 线性查找 与N成正比
• 二分查找 与log^n成正比
• 不要常数
  大O表示法同上面的公式比较类似，但它省去了常数K。当比较算法时，真正需要比较的是对应不同的N值，T是如何变化的，而不是具体的数字。因此不需要常数。
  表2.5总结了目前讨论过的算法的运行时间。

2.10 为什么不用数组表示一切

仅使用数组似乎就可以完成所有的工作，为什么不用他们来进行所有数据的存储呢？
我们已经看到数组的诸多缺点。在一个无序数组中可以很快的进行插入（O(1)时间），但是查找却要花费较慢的O(N)时间。在一个有序数组中可以查找得很快，用O(log^N)的时间，但插入缺花费了O(N)时间。对于这两组数组而言，由于平均半数的数据项为了填补空洞必须移动，所以删除操作平均需要O(N)时间。
如果有一种数据结构进行任何如插入、删除、查找的操作都很快（理想的是O(1)或者O(log^n)时间），那就好了。
数组的另外一个问题是它们被new创建后，大小尺寸就被固定住了。但通常在开始设计程序的时候，并不知道会有多少数据项放入数组中，所以需要猜它的大小。如果猜的数过大，会使数组中的某些单元永远不会被填充而浪费空间。如果猜的过小，会发生数组的溢出，最好的情况下会向用户发出警告消息，最坏的情况则会导致程序崩溃。

3.简单排序

3.1 冒泡排序

以下是要遵守的规则：

1、比较相邻的两个队员。
2、如果左边的队员高，则两队员交换位置。
3、向右移动一个位置，比较下面两个队员。

因为在算法执行的时候，最大的数据项总是通过冒泡到数组的最顶端。所以被称为冒泡排序。

冒泡排序的Java代码

public class ArrayBub {private int[] a;private int nElems;public ArrayBub(int max) {a = new int[max];nElems = 0;}public void insert(int value) {a[nElems] = value;nElems++;}public void display() {for(int i = 0 ; i < nElems ; i ++) {System.out.println(a[i]);}}public void bubbleSort() {int out, in;for(out = nElems - 1 ; out > 0; out--) {for (in = 0 ; in < out ; in ++) {if (a[in] > a[in + 1]) {swap(in, in + 1);}}}}private void swap(int one, int two) {int temp = a[one];a[one] = a[two];a[two] = temp;}  
}public class BubbleSortApp {public static void main(String[] args) {int maxSize = 100;ArrayBub arr;arr = new ArrayBub(maxSize);arr.insert(77);arr.insert(99);arr.insert(44);arr.insert(55);arr.insert(22);arr.insert(88);arr.insert(11);arr.insert(00);arr.insert(66);arr.insert(33);arr.display();arr.bubbleSort();arr.display();}
}

注意，书中此处有个错误，应该是out>0，而不是out>1。

不变性

在许多算法中，有些条件在算法执行时是不变的。这些条件被称为不变性。认识不变性对理解算法是有用的。在一定情况下它们对调试也有用；可以反复的检查不变性是否为真，如果不是的话就标记出错。
在bubbleSort.java程序中，不变性是指out右边的所有数据项为有序。在算法的整个运行过程中这个条件始终为真。（在第一趟排序之前，尚未排序，因为out开始时在数据项的最右边，没有数据项在out的右边。）

冒泡排序的效率

一般来说，数组中有N个数据项，则第一趟排序中有N-1次比较，第二趟中有N-2次，如果类推。这种序列的求和公式如下：
（N-1）+(N-2)+(N-3)+...+ 1 = N * (N-1)/2，这样算法做了约N^2次比较（忽略-1，不会有很大的差别，特别是当N很大时）。
因为只有在需要交换时才交换，所以交换的次数小于比较的次数。如果数据是随机的，那么大概有一半数据需要交换，则交换次数为N^2/4。（不过在最坏的情况下，即初始的数据是逆向的，每次比较都需要交换。）
比较和交换的次数都与N^{2成正比。由于常数不算在大O表示法中，可以忽略2和4，并且认为冒泡排序运行需要O(N}2)时间级别。这种排序算法的速度是很慢的。
无论何时，只要看到一个循环嵌套在另一个循环里，例如冒泡排序和本章节中的其他排序算法中，就可以怀疑这个算法运行时间为O(N^2)级。

3.2选择排序

选择排序改进了冒泡排序，将必要的交换次数从O（N^{2）减少到O（N）。不幸的是比较次数扔保持为O（N}2）。然而，选择排序仍然为大量记录的排序提出了一个非常重要的改进。因为这些大量的记录需要在内存中移动，这就使交换的时间与比较的时间相比起来，交换的时间更为重要。（一般来说，在Java语言中不是这种情况，Java中只是改变了引用位置，而实际对象的位置并没有发生改变。）

选择排序的Java代码

public class ArraySel {private int[] a;private int nElems;public ArraySel(int max) {a = new int[max];nElems = 0;}public void insert(int value) {a[nElems] = value;nElems++;}public void display() {for(int i = 0 ; i < nElems ; i ++) {System.out.println(a[i]);}}public void selectionSort() {int out, in, min;for(out = 0 ; out < nElems - 1 ; out ++) {min = out;for(in = out + 1; in < nElems; in ++) {if (a[in] < a[min]) {min = in;}}if (min != out) {swap(out, min);}}}private void swap(int one, int two) {int temp = a[one];a[one] = a[two];a[two] = temp;}}public class SelectSortApp {public static void main(String[] args) {int maxSize = 100;ArraySel arr;arr = new ArraySel(maxSize);arr.insert(77);arr.insert(99);arr.insert(44);arr.insert(55);arr.insert(22);arr.insert(88);arr.insert(11);arr.insert(00);arr.insert(66);arr.insert(33);arr.display();arr.selectionSort();arr.display();}
}

不变性

在ArraySel.java程序中，下标小于或等于out的位置的数据总是有序的

选择排序的效率

当N值很大时，比较的次数是主要的，所以结论是选择排序跟冒泡排序一样运行了O（N^2）时间。但是，选择排序无疑更快，因为它进行的交换少得多。当N值较小时，特别是如果交换的时间级比比较的时间级大的多时，选择排序实际上是相当快的。

3.3插入排序

在大多数情况下，插入排序是本章节描述的基本的排序算法中最好的一种。虽然插入排序算法仍然需要O（N^2）时间，但是在一般的情况下，它比冒泡排序快一倍，比选择排序还要快一点。尽管它比冒泡排序和选择排序算法都更麻烦一些，但它并不是很复杂。它通常用在较复杂的排序算法的最后阶段，例如快速排序。

插入排序的Java代码

public class ArrayIns {private int[] a;private int nElems;public ArrayIns(int max) {a = new int[max];nElems = 0;}public void insert(int value) {a[nElems] = value;nElems++;}public void display() {for(int i = 0 ; i < nElems ; i ++) {System.out.println(a[i]);}}public void insertionSort() {int in, out;for(out = 1; out < nElems ; out ++) {int temp = a[out];in = out;while(in > 0 && a[in -1] >= temp) {a[in] = a[in - 1];-- in;}a[in] = temp;}}
}public class InsertSortApp {public static void main(String[] args) {int maxSize = 100;ArrayIns arr;arr = new ArrayIns(maxSize);arr.insert(77);arr.insert(99);arr.insert(44);arr.insert(55);arr.insert(22);arr.insert(88);arr.insert(11);arr.insert(00);arr.insert(66);arr.insert(33);arr.display();arr.insertionSort();arr.display();}
}

不变性

在每趟结束时，在将temp位置的项插入后，比outer变量下标号小的数据项都是局部有序的。

插入排序的效率

在第一趟排序中，它最多进行一次比较，第二趟最多比较两次，以此类推。最后一趟最多，比较N-1次。因此有1+2+3+...+N-1=N（N-1）/2。
然而，因为在每一趟排序发现插入点之前，前面的数据是局部有序的，平均只有一半的数据项真的进行了比较，我们除以2得到N（N-1）/4。
复制的次数大致等于比较的次数。然后，一次复制与一次交换的时间消耗不同，所以相对于随机的数据，这个算法比冒泡排序快一倍，比选择排序略快。
在任意情况下，和本章其他的排序例程一样，对于随机顺序的数据进行插入排序也需要O（N^2）的时间级。
对于已经有序或者基本有序的数据来说，插入排序要好得多。当数据有序时，while循环的条件总是假，所以它变成了外层循环的一个简单语句，执行N-1次。在这种情况下，算法运行只需要O（N）的时间。
然而对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不比冒泡排序快。

3.4对象排序

略

3.5几种简单排序之间的比较

除了手边没有算法书可参考，一般情况几乎不适用冒泡排序。它过于简单了，以至于可以毫不费力的写出来。然而当数据量很小的时候它会有些应用价值。
选择排序虽然把交换次数降到了最低，但比较次数仍然很大。当数据量很小，并且交换数据相比于比较数据更加耗时的情况下，可以应用选择排序。
在大多数情况下，假设当数据量比较小或基本能有序时，插入排序算法是三种简单排序算法中最好的选择。 对于数据量更大的排序来说，快速排序通常是最快的方法。
除了在速度方面比较排序算法外，还有一种对各种算法衡量标准是算法需要的内存空间有多大。本章中三种算法都可以"就地"完成排序，即除了初始的数组外几乎不需要其他内存空间。所有的排序算法都需要一个额外的变量来暂时存储交换时的数据项。

3.6小结

• 本章提到的排序算法都假定了数组作为数据存储结构。
• 排序包括比较数组中数据项的关键字和移动相应的数据项（实际上，是数据项的引用），直到它们排好序为止。
• 本章中所有的排序时间复杂度都是O（N^2）。不过，在某些情况下某个算法可以比其他算法快很多。
• 不变性是指算法运行中保持不变的条件。
• 冒泡排序算法是效率最差的算法，但它最简单。
• 插入排序算法是本章介绍O（N^2）应用最多的。
• 如果具有相同关键字的数据项，经过排序它们的顺序保持不变，这样的排序就是稳定的。
• 本章介绍的所有排序算法除了需要初始数组之外，都只需要一个临时变量。

4.栈和队列

4.1 栈

栈只允许访问一个数据项：即最后插入的数据项。移除这个数据项后才能访问倒数第二个插入数据项，以此类推。这种机制在不少编程环境中都很有用。本节中将看到如何利用栈来校验源程序中的小括号、中括号、大括号的匹配问题。本章的最后会讲到栈在解析算式表达式时起到了及其重要的作用，比如解析3*（4+5）。
栈也是那些应用了相当复杂的数据结构算法的便利工具。比如在第8章"二叉树"中，用栈来辅助遍历树的节点；在第13张的"图"中，利用栈来辅助查找图的顶点（一种可以用来解决迷宫的技术）。
大部分未处理运用基于栈的体系结构。当调用一个方法时，把它的返回地址和参数压入栈，当方法结束返回时，那些数据出栈。栈操作就嵌入在微处理器中。
一些较老的便携式计算器也用基于栈的体系结构。它们不是输入带有括号的算术表达式，而是把中间的结果先存入栈中。

栈中的Java代码

public class StackX {private int maxSize;private int[] stackArray;private int top;public StackX(int s) {maxSize = s;stackArray = new int[maxSize];top = -1;}public void push(int value) {stackArray[++top] = value;}public int pop() {return stackArray[top--];}public int peek() {return stackArray[top];}public boolean isEmpty() {return top == -1;}public boolean isFull() {return top == maxSize - 1;}
}public class StackApp {public static void main(String[] args) {StackX theStack = new StackX(10);theStack.push(20);theStack.push(40);theStack.push(60);theStack.push(80);while (!theStack.isEmpty()) {int value = theStack.pop();System.out.print(value);System.out.print(" ");}System.out.println("");}
}

StackX类中的方法

构造方法首先根据参数规定的容量创建了一个新栈。栈的新域包括表示栈最大容量的变量（即数组的大小）、数组本身以及变量top,它存储栈顶元素的下标。（注意，由于栈是有数组实现的，需要先规定栈的大小。但是，如果使用链表来实现栈，就不需要先规定栈的容量）。
push（）方法中将top值增加1，使它指向原顶端数据项上面的一个位置，并在这个位置上存储一个数据项。再次提醒，top值是在插入数据项之前递增的。
pop（）方法返回top标识的数据项值，然后top减一。这个方法有效的移除了数据项：虽然数据项仍然存在数组中（直到有新的数据项压入栈中覆盖这个数据项），但不能再访问它了。
peek（）方法仅返回了top所指的数据项的值，不对栈做任何改动。
isEmpty（）方法和isFull（）方法分别在栈空和栈满时返回true。栈空是top变量为-1，栈满时top变量为maxSize-1。

图4.3展示了StackX类的方法是如何操作的。

许多栈的类在push（）和pop（）方法内部检查了这些错误，那是更好的方法。Java语言中，对栈来说发现这类错误一个好的方法是抛出异常，异常可以可以被用户捕获并处理。

• 4.1.1 栈实例1：单词逆序

代码清单

public class StackX {private int maxSize;private char[] stackArray;private int top;public StackX(int s) {maxSize = s;stackArray = new char[maxSize];top = -1;}public void push(char j) {stackArray[++top] = j;}public char pop() {return stackArray[top--];}public char peek() {return stackArray[top];}public boolean isEmpty() {return top == -1;}
}public class Reverser {private String input;private String output;public Reverser (String in) {input = in;}public String doRev() {int maxSize = input.length();StackX stackX = new StackX(maxSize);for(int j = 0 ; j < input.length() ; j ++) {char ch = input.charAt(j);stackX.push(ch);}output = "";while (!stackX.isEmpty()) {char ch = stackX.pop();output = output + ch;}return output;}
}public class ReverserApp {public static void main(String[] args) throws IOException{String input, output;while (true) {System.out.print("Enter a String:");System.out.flush();input = getString();if (input.equals("")) {break;}Reverser reverser = new Reverser(input);output = reverser.doRev();System.out.println("Reversed:" + output);}}public static String getString() throws IOException {InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}
}

• 4.1.2 栈实例2：分隔符匹配

看看对下面这个正确的字符串，栈的变化过程：

a{b(c[d]e)f}

表4.1显示了每次从字符串中读取一个字符后栈的情况。表中第二列显示的是栈中的数据项。

代码清单

public class StackX {private int maxSize;private char[] stackArray;private int top;public StackX(int s) {maxSize = s;stackArray = new char[maxSize];top = -1;}public void push(char j) {stackArray[++top] = j;}public char pop() {return stackArray[top--];}public char peek() {return stackArray[top];}public boolean isEmpty() {return top == -1;}
}public class BracketChecker {private String input;public BracketChecker(String in) {input = in;}public void check() {int stackSize = input.length();StackX theStack = new StackX(stackSize);for(int j = 0 ; j < input.length() ; j ++) {char ch = input.charAt(j);switch (ch) {case '{':case '[':case '(':theStack.push(ch);break;case '}':case ']':case ')':if (!theStack.isEmpty()) {char chx = theStack.pop();if (ch == '}' && chx != '{' || ch == ']' && chx != '[' || ch == ')' && chx != '(') {System.out.println("Error: " + ch + " at " + j);}} else {System.out.println("Error: " + ch + " at " + j);break;}default:break;}}if (!theStack.isEmpty()) {System.out.println("Error: missing the right delimiter");}}
}public class BracketsApp {public static void main(String[] args) throws IOException{String input;while (true) {System.out.print("Enter string containing delimiters: ");System.out.flush();input = getString();if (input.equals("")) {break;}BracketChecker theChecker = new BracketChecker(input);theChecker.check();}}public static String getString() throws IOException {InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}
}  

check（）例程从Reverse.java程序中调用了StackX类。请注意重用这个类非常容易，只需要在一个地方添加代码就可以。这是面向对象编程的优点之一。

栈是一个概念上的辅助工具

由上可见，在brackets.java程序中使用栈是多么方便。同样也可以利用普通数组来完成栈的操作，但是那样就不得不老惦记着最后添加的字符的下标值，和某些记账问题一样。栈在抽象概念上更便于使用。栈通过提供限定性的访问方法push（）和pop（），使程序易读且不易出错。（拿木匠的话来说，用正确的工具干活更安全。）

栈的效率

StackX类中现实的栈，数据项入栈和出栈的时间复杂度都为常数O（1）。这也就是说，栈操作所耗的时间不依赖于栈中的数据项的个数，因此操作时间很短。栈不需要比较和移动操作。

4.2 队列

在计算机科学中，队列是一种数据结构，有点类似栈，只是在队列中第一个插入的数据项会最先被移除（先进先出，FIFO），而在栈中，最后插入的数据项最先被移除（LIFO）。队列的作用就像电影院的人们站成的排一样，第一个进入队尾的人将最先到达的队头买票，最后排队的人最后才能买到票。
栈和队列一样也被用作程序员的工具。
在计算机（或网络）操作系统里，有各种队列在安静地工作着。打印作业在打印队列中等待打印。当在键盘上敲击时，也有一个存储键入内容的队列。同样，如果使用一个文字处理程序敲击一个键，而计算机又暂时要做其它的事，敲击的内容不会丢失，它会排在队列中等待，直到文字处理程序有时间来读取它。利用队列保证了键入的内容在处理时其顺序不会改变。

循环队列

计算机在队列中删除一个数据项后，也可以将其他数据项都向前移动，但这样的效率很差。相反，我们通过队头队尾指针的移动保持所有的数据项的位置不变。
这样设计的问题是队尾指针很快就会移动到数组的末端（数组下标最大）。虽然在数组的开始部分有空的数据项单元，这是移除数据项的位置，但是由于因为队尾指针不能再往后移动了，因此不能插入新的数据项。这能怎么办？图4.8显示的就是这样的情况。

环绕式处理

为了避免队列不满却不能插入新的数据项的问题，可以让队头队尾指针绕回到数组开始的位置，这就是循环队列（有时也称为缓冲环）。

队列的Java代码

public class Queue {private int maxSize;private long[] queArray;private int front;private int rear;private int nItems;public Queue(int s) {maxSize = s;queArray = new long[maxSize];front = 0;rear = -1;nItems = 0;}public void insert(long j) {if (rear == maxSize - 1) {rear = -1;}queArray[++rear] = j;nItems++;}public long remove() {long temp = queArray[front++];if (front == maxSize) {front = 0;}nItems--;return temp;}public long peekFront() {return queArray[front];}public boolean isEmpty() {return (nItems == 0);}public boolean isFull() {return (nItems == maxSize);}public int size() {return nItems;}}public class QueueApp {public static void main(String[] args) {Queue theQueue = new Queue(5);theQueue.insert(10);theQueue.insert(20);theQueue.insert(30);theQueue.insert(40);theQueue.remove();theQueue.remove();theQueue.remove();theQueue.insert(50);theQueue.insert(60);theQueue.insert(70);theQueue.insert(80);while(!theQueue.isEmpty()) {long n = theQueue.remove();System.out.print(n);System.out.print(" ");}System.out.print(" ");}
}

程序实现的Queue类中不但有front（队头）和rear（队尾）字段，还有队列中当前数据项个的个数：nItems。有些队列实现中没有这个字段，后面会显示后一种实现方法。

insert（）方法
insert（）方法运行的前提条件是队列不满。在main（）中没有显示这个方法，不过通常应该先调用isFull（）方法并且返回false后，才调用
insert（）方法。（更通用的做法是在insert（）方法加入检查队列是否满的判定，如果出现向已满的队列里插入数据项的情况就抛出异常。）
一般情况，插入操作是rear（队尾指针）加一后，在队尾指针所指向的位置处插入新的数据。但是，当rear指针指向数组的顶端，即maxSize-1位置的时候，在插入数据项之前，它必须回绕到数组的底端。回绕操作把rear设置为-1，因此当rear加1后，它等于0，是数组底端的下标值。最后，nItem加1。

remove（）方法
remove（）方法运行的前置条件是队列不空，在调用这个方法之前应该调用isEmpty（）方法确保队列不空，或者在remove（）方法里加入这种出错检查机制。
移除（remove）操作总是由front指针得到队头数据项的值，然后将front加一。但是，如果这样做使front的值超过数组的顶端，front就必须绕回到数组下标为0的位置。作这种校验的同时，先将返回值临时存储起来。最后nItems减一。

没有数据项计数字段的队列实现

在Queue类中包含数据项计数字段nItems会使insert（）方法和remove（）方法增加一点额外的操作，因为insert（）方法和remove（）方法必须分别递增和递减这个变量值。这可能算不上额外的开销，但是如果处理大量的插入和移除操作，这可能会影响性能了。
因此，一些队列的实现不使用数据项计数的字段，而是通过front和rear来计算出队列是否空或者满以及数据项个数。如果这样做，isEmpty（）、isFull（）和size（）历程会相当复杂，因为就像前面讲过的那样，数据项的序列或者被折成两段，或者是连续的一段。
并且，一个奇怪的问题出现了。当队列满的时候，front指针和rear指针指向一定位置，但是当队列为空时，也可能呈现相同的位置关系。于是在同一时间，队列似乎可能是满的，也可能是空的。
这个问题可以这样解决，让数组容量比队列数据项个数的最大值还要大一。

无数据项计数队列的Java代码

public class Queue {private int maxSize;private long[] queArray;private int front;private int rear;public Queue(int s) {maxSize = s + 1;queArray = new long[maxSize];front = 0;rear = -1;}public void insert(long j) {if (rear == maxSize - 1) {rear = -1;}queArray[++rear] = j;}public long remove() {long temp = queArray[front++];if (front == maxSize) {front = 0;}return temp;}public long peekFront() {return queArray[front];}public boolean isEmpty() {return (rear + 1 == front || (front + maxSize - 1 == rear));}public boolean isFull() {return (rear + 2 == front || (front + maxSize - 2 == rear));}public int size() {if (rear >= front) {return rear - front + 1;} else {return (maxSize-front) + (rear + 1);}}}

注意这个类中的isEmpty（）、isFull（）、size（）方法的复杂性。实际上很少用这样的方法实现队列，所以这里就不详细的讨论它了。

队列的效率

和栈一样，队列的插入数据项和移除数据项的时间复杂度均为O（1）。

双端队列

双端队列就是一个两端都有结尾的队列。队列的每一端都可以插入数据项和移除数据项。这些方法可以叫做insertLeft（）和insertRight（），以及removeLeft（）、removeRight（）。
如果严格禁止调用insertLeft（）、removeLeft（）（或禁用右端的操作），双端队列的功能就和栈一样了。
双端队列和栈或者队列相比，是一种多用途的数据结构，在容器类库中有时会用双端队列来提供栈和队列的两种功能。但是，双端队列不像栈和队列常用，因此这里不再深入研究它了。

4.3 优先级队列

优先级队列是比栈和队列更专用的数据结构。但它在很多情况下都很有用。像普通队列一样，优先级队列有一个队头和队尾，并且也是从队头移除数据项。不过在优先级队列中，数据项按关键字有序，这样关键字最小的数据项（或者在某些实现中是关键字最大的数据项）总是在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。
像栈和队列一样，优先级队列也经常用作程序员的工具。在第14章中，可以看到在图的最小生成树算法中应用优先级队列。
像普通队列一样，优先级队列在某些计算机系统中也有很多应用。例如，在抢先式多任务操作系统中，程序排列在优先级队列中，这样优先级高的程序就会先得到时间片并得以运行。
很多情况下需要访问具有最小关键字的数据项（比如要寻找最便宜的方法或者最短的路径去做某件事）。因此，具有最小关键字的数据项具有最高的优先级。本书略微有点专断，假定所有的情况都是这样的，尽管有很多情况下最大关键字具有最高的优先级。
除了可以快速访问最小关键字数据项，优先级队列还应该实现可以快速的插入数据项。因此，正如前面提到过的，优先级队列通常使用一种称为堆的数据结构来实现。在第12章将会介绍堆。本章使用简单数组实现优先级队列。这种实现方法插入比较慢，但是它是比较简单，适用于数据量比较小并且不是特别注重插入速度的情况。
注意，优先级队列的实现没有使用指针回绕。因为要找到合适的位置，所以优先级队列的插入是很慢的，不过删除倒很快。实现指针回绕不能改善这种情况。还要注意队尾指针从不移动，它总指着数组底端下标为0的单元。

优先级队列的Java代码

public class PriorityQ {private int maxSize;private long[] queArray;private int nItems;public PriorityQ(int s) {maxSize = s;queArray = new long[maxSize];nItems = 0;}public void insert(long item) {int j;if (0 == nItems) {queArray[nItems++] = item;} else {for (j = nItems - 1; j >=0 ; j--) {if (item > queArray[j]) {queArray[j+1] = queArray[j];} else {break;}}queArray[j+1] = item;nItems++;}}public long remove() {return queArray[--nItems];}public long peekMin() {return queArray[nItems - 1];}public boolean isEmpty() {return (nItems == 0);}public boolean isFull() {return (nItems == maxSize);}
}public class PriorityQApp {public static void main(String[] args) {PriorityQ thePQ = new PriorityQ(5);thePQ.insert(30);thePQ.insert(50);thePQ.insert(10);thePQ.insert(40);thePQ.insert(20);while (!thePQ.isEmpty()) {long item = thePQ.remove();System.out.print(item + " ");}System.out.println("");}
}

优先级队列不像Queue类那样必须有front和rear字段，它的front总是nItems-1，rear总是等于0。

优先级队列的效率

在本章节实现的优先级队列中，插入操作需要O（N）时间，而删除操作则需要O（1）时间。第12章将介绍如果通过堆来改进插入操作的时间。

4.4 解析算式表达式

从某种意义上来说本节内容应作为选学内容。它并不是本书后面章节的必修内容，并且除非是专门编写编译器或者是要设计便携式计算器的程序员，人们不会每天编写代码来解析算数表达式。另外，此应用的详细代码也比以前的程序复杂得多。但是这个重要的应用对于学习栈很有意义，并且应用本身引起的问题也非常有意思 。
事实上，至少对计算机的算法来说如果直接求算数表达式的值，还是相当困难的。因此分为两步实现算法会更容易:
1、将算术表达式转化为另一种形式：后缀表达式。
2、计算后缀表达式的值。
第一个步骤比较难，第二个步骤比较简单。但是不管怎么说，这种分两步的算法比直接解析算术表达式的方法容易。当然，对人类来说，还是解析普通的算术表达式容易。稍后将会再讨论人类和计算机的方法的区别。

后缀表达式

日常算数表达式是将操作符（+，-，*，/）放到两个操作数（数字或者代表数字的字母）的之间的。因为操作符写在操作数之间，所以把这种写法称为中缀表达式。于是，日常我们写的算术表达式就行如2+2，4/7，或者用字母代替数字，如A+B和A/B等。
在后缀表达式[也称为波兰逆序表达式（Reverse Polish Notation），或者RPN，它是由以为波兰的数学家发明的]，操作符跟在两个操作数后面。这样，A+B就成为AB+，A/B称为AB/。更复杂的中缀表达式同样可以转化为后缀表达式，如表4.2所示。稍后会解释后缀表达式是如何产生的。

有些计算机语言也用一个操作符表示乘方（通常，用^表示），但在这里不讨论暂不讨论这种表示。
除了中缀和后缀表达式，还有一种前缀表达式法，操作符写在两个操作符前面。这种表达式跟后缀表达式功能类似，但是很少使用。

把中缀表达式转化为后缀表达式

人是如何计算中缀表达式的值

粗略来说，“解”算术表达式的时候，应该遵循下列几条规则：
1、从左到右读取算术。（至少，假设这样。有时候人们会跳过算式前面的部分，但是为了便于讨论，需要假定从左边开始系统的读表达式。）
2、已经读到了可以计算值的两个操作数和一个操作符时，就可以计算，并用计算结果代替那两个操作数和那个操作符。（可能需要处理左边一些没有解决的操作，稍后可以看到）
3、重复这个过程-从左到右，能算就算-指导表达式的结尾。
表4.3、4.4和4.5显示了三个非常简单的中缀表达式求值的例子。在后面的表4.6、4.7和4.8中，可以看到这些求值过程与中缀到后缀的转换是多么的相似。

人类如何将中缀表达式转换成后缀表达式

将中缀表达式转换成后缀表达式的规则和计算中缀表达式值的规则基本类似。但是，还是有点变化的。将中缀表达式转换成后缀表达式不用做算术运算。它不求中缀表达式的值，只是把操作数和操作符重新排列成另一种形式：后缀表示法。然后再求后缀表达式的结果。
和以前一样，从左往右地读取中缀表达式，顺序的查看每一个字符。在此过程中，将这些操作数和操作符复制到后缀表达式输出的字符串中。关键是要知道这个字符该何时输出。
如果中缀字符串中的字符是操作数，则立即把它复制到后缀字符串中。读到操作数就复制它们，而不去管多久后才能复制和它们关联的操作符 。
决定何时复制操作符更复杂一些，但它的规则和计算中缀表达式时一样。一旦可以利用操作符求中缀表达式的某部分的值，就把该运算法复制到后缀字符串中。

在栈中保存操作符

在表4.7、表4.8中，可以看到从中缀到后缀的转换过程中，操作符的顺序是颠倒的。因为第一个操作符必须等第二个操作符输出后才能输出，所以操作符在后缀字符串中的顺序和中缀字符串中的顺序是相反的。一个较长的表达式可以更清楚地表明这一点。表4.9展示了将中缀表达式A+B*(C-D)转换成后缀的过程。

转换规则

中缀表达式转换成后缀表达式的Java代码

public class StackX {private int maxSize;private char[] stackArray;private int top;public StackX(int s) {maxSize = s;stackArray = new char[maxSize];top = -1;}public void push(char j) {stackArray[++top] = j;}public char pop() {return stackArray[top--];}public char peek() {return stackArray[top];}public boolean isEmpty() {return (top == -1);}public int size() {return top+1;}public char peekN(int n) {return stackArray[n];}public void displayStack(String s) {System.out.print(s);System.out.println("Stack (bottom-->top): ");for (int j = 0; j < size(); j ++) {System.out.print(peekN(j));System.out.print(' ');}System.out.println("");}
}public class InToPost {private StackX theStack;private String input;private String output = "";public InToPost(String in) {input = in;int stackSize = input.length();theStack = new StackX(stackSize);}public String doTrans() {for (int j = 0; j < input.length() ; j ++) {char ch = input.charAt(j);theStack.displayStack("For " + ch + " ");switch (ch) {case '+' :case '-' :gotOper(ch, 1);break;case '*' :case '/' :gotOper(ch, 2);break;case '(' :theStack.push(ch);break;case ')' :gotParen(ch);break;default:output = output + ch;break;}}while (!theStack.isEmpty()) {theStack.displayStack("While ");output = output + theStack.pop();}theStack.displayStack("End ");return output;}public void gotOper(char opThis, int prec1) {while (!theStack.isEmpty()) {char opTop = theStack.pop();if (opTop == '(') {theStack.push(opTop);break;} else {int prec2;if (opTop == '+' || opTop == '-') {prec2 = 1;} else {prec2 = 2;}if (prec2 < prec1) {theStack.push(opTop);break;} else {output = output + opTop;}}}theStack.push(opThis);}public void gotParen(char ch) {while (!theStack.isEmpty()) {char chx = theStack.pop();if (chx == '(') {break;} else {output = output + chx;}}}}public class InfixApp {public static void main(String[] args) throws IOException{String input, output;while (true) {System.out.print("Enter infix: ");System.out.flush();input = getString();if (input.equals("")) {break;}InToPost theTrans = new InToPost(input);output = theTrans.doTrans();System.out.println("Postfix is " + output + '\n');}}public static String getString() throws IOException {InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}}

StackX类有一个displayStack（）方法，它显示栈中所有的数据项，理论上来说，这样做是不合规则的；原则上只能访问栈顶元素。但是，作为一个诊断错误的辅助工具，当需要查看转换过程中每一步栈的情况时，这个例程还是很有用的。

运行结果：

Enter infix: A*(B+C)-D/(E+F)
For A Stack (bottom-->top): 
For * Stack (bottom-->top): 
For ( Stack (bottom-->top): * 
For B Stack (bottom-->top): * ( 
For + Stack (bottom-->top): * ( 
For C Stack (bottom-->top): * ( + 
For ) Stack (bottom-->top): * ( + 
For - Stack (bottom-->top): * 
For D Stack (bottom-->top): - 
For / Stack (bottom-->top): - 
For ( Stack (bottom-->top): - / 
For E Stack (bottom-->top): - / ( 
For + Stack (bottom-->top): - / ( 
For F Stack (bottom-->top): - / ( + 
For ) Stack (bottom-->top): - / ( + 
While Stack (bottom-->top): - / 
While Stack (bottom-->top): - 
End Stack (bottom-->top): 
Postfix is ABC+*DEF+/-Enter infix: Process finished with exit code 0

后缀表达式求值

人类如何用后缀表达式求值

后缀表达式求值规则

后缀表达式求值的Java代码

public class StackX {private int maxSize;private int[] stackArray;private int top;public StackX(int size) {maxSize = size;stackArray = new int[maxSize];top = -1;}public void push(int j) {stackArray[++top] = j;}public int pop() {return stackArray[top--];}public int peek() {return stackArray[top];}public boolean isEmpty() {return (top == -1);}public boolean isFull() {return (top == maxSize - 1);}public int size() {return top + 1;}public int peekN(int n) {return stackArray[n];}public void displayStack(String s) {System.out.print(s);System.out.print("Stack (bottom-->top): ");for (int j = 0; j < size(); j ++) {System.out.print(peekN(j));System.out.print(' ');}System.out.println("");}
}public class ParsePost {private StackX theStack;private String input;public ParsePost(String s) {input = s;}public int doParse() {theStack = new StackX(20);char ch;int j;int num1, num2, interAns;for (j = 0; j < input.length(); j ++) {ch = input.charAt(j);theStack.displayStack("" + ch + " ");if (ch >= '0' && ch <= '9') {theStack.push((int) (ch-'0'));} else {num2 = theStack.pop();num1 = theStack.pop();switch (ch) {case '+' :interAns = num1 + num2;break;case '-' :interAns = num1 - num2;break;case '*' :interAns = num1 * num2;break;case '/' :interAns = num1 / num2;break;default:interAns = 0;}theStack.push(interAns);}}interAns = theStack.pop();return interAns;}
}public class PostfixApp {public static void main(String[] args) throws IOException{String input;int output;while (true) {System.out.print("Enter postfix: ");System.out.flush();input = getString();if (input.equals("")) {break;}ParsePost aParser = new ParsePost(input);output = aParser.doParse();System.out.println("Evaluates to " + output);}}public static String getString() throws IOException {InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;}
}

运行结果：

Enter postfix: 345+*612+/-
3 Stack (bottom-->top): 
4 Stack (bottom-->top): 3 
5 Stack (bottom-->top): 3 4 
+ Stack (bottom-->top): 3 4 5 
* Stack (bottom-->top): 3 9 
6 Stack (bottom-->top): 27 
1 Stack (bottom-->top): 27 6 
2 Stack (bottom-->top): 27 6 1 
+ Stack (bottom-->top): 27 6 1 2 
/ Stack (bottom-->top): 27 6 3 
- Stack (bottom-->top): 27 2 
Evaluates to 25
Enter postfix: Process finished with exit code 0

4.5 小结

• 栈、队列和优先级队列经常用于简化某些程序的数据结构。
• 在这些数据结构中，只有一个数据项可以被访问。
• 栈允许访问最后一个插入的数据项。
• 栈中重要的操作时在栈顶插入（压入）一个数据项，以及从栈顶移除（弹出）一个数据项。
• 队列只允许访问第一个插入的数据项。
• 队列的重要操作是在队尾插入数据项和在队头移除数据项。
• 队列可以实现为循环队列，它基于数组，数组下标可以从数组末端回绕到数组的开始位置。
• 优先级队列允许访问最小（或者有时最大）的数据项。
• 这些数据结构可以用数组实现，也可以用其他机制（例如链表）来实现。
• 普通算术表达式是用中缀表达式表示的，这种命名的原因是操作符写在两个操作数的中间。
• 在后缀表达式中，操作符跟在两个操作数后面。
• 算术表达式求值通常都是先转换成后缀表达式，然后再求后缀表达式的值。
• 在中缀表达式转换成后缀表达式以及求后缀表达式的值的过程中，栈都是很有用的工具。