堆栈（STACK）
“堆栈”类似于桌面上堆积的书，取数据的时候从最后一个存储的数据开始，即栈是一种“后进先出（LIFO）”的数据结构。
主要操作
- void push(int data): 将data(数据)插入栈。
- int pop(): 删除并返回最后一个插入栈的元素。
- int top(): 返回最后一个插入的栈的元素，但不会删除。
- int size(): 返回存储在栈中的元素的个数。
- Boolean isEmpty(): 判断栈是否为空。
- Boolean isStackFull(): 判断栈中是否存储满元素。
接口代码
1 | interface Stack { |
栈的应用
- 符号匹配
- 中缀表达式转换为后缀表达式
- 计算后缀表达式
- 实现函数调用
栈的实现
- 基于简单的数组的实现方法
- 基于动态数组的实现方法
- 基于链表的实现方法
简单数组实现
基于简单数组实现栈顶抽象数据类型的方法。如下图所示，从左至右向数组中添加所有元素，并定义一个变量来记录数组当前栈顶元素的下表：
当数组存满了栈元素时，执行入栈（插入元素）操作将抛出栈满异常。当对一个没有存储栈元素的数组执行出栈（删除元素）操作时，将抛出空异常。
实现的代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108// 基于简单数组实现
class ArrayStackDemo implements Stack {
private int size;
private int[] array;
private int capacity;
// 默认大小为5的栈
public ArrayStackDemo() throws Exception {
this(5);
}
// 指定大小的栈
public ArrayStackDemo(int capacity) throws Exception {
if (capacity < 0)
throw new Exception("大小错误!");
this.size = -1;
this.capacity = capacity;
this.array = new int[capacity];
}
// 是否满栈
public Boolean isStackFull() {
return size == capacity-1;
}
// 是否空栈
public Boolean isEmpty() {
return size == -1;
}
// 入栈
public void push(int data) {
if (isStackFull()) {
System.out.println("满栈");
} else {
array[++size] = data;
}
}
// 出栈
public int pop() {
if (isEmpty()) {
System.out.println("空栈");
return -1;
} else {
return array[size--];
}
}
// 栈顶
public int top() {
if (isEmpty()) {
System.out.println("空栈");
return -1;
} else {
return array[size];
}
}
// 获取栈长
public int getSize() {
return size;
}
public void deleteStack() {
size = -1;
}
public String toString() {
if (isEmpty()) {
return "空栈";
} else {
StringBuffer bs = new StringBuffer();
bs.append(array[0]);
for (int i = 1; i < size+1; i++) {
bs.append("->"+array[i]);
}
return "栈低("+bs +")栈顶，"+"栈长度为："+(size+1)+"，栈顶为："+top()+"，是否满栈："+isStackFull();
}
}
}
public class StackTest {
public static void main(String[] args) throws Exception {
ArrayStackDemo as = new ArrayStackDemo();
for (int i = 0; i < 5; i++) {
as.push(i);
}
System.out.println(as);
System.out.print("继续入栈5：");
as.push(5);
System.out.println(as);
System.out.println("出栈："+as.pop());
System.out.println(as);
System.out.print("继续入栈5：");
as.push(5);
System.out.println(as);
}
}
-------------------------------output----------------
栈低(0->1->2->3->4)栈顶，栈长度为：5，栈顶为：4，是否满栈：true
继续入栈5：满栈
栈低(0->1->2->3->4)栈顶，栈长度为：5，栈顶为：4，是否满栈：true
出栈：4
栈低(0->1->2->3)栈顶，栈长度为：4，栈顶为：3，是否满栈：false
继续入栈5：栈低(0->1->2->3->5)栈顶，栈长度为：5，栈顶为：5，是否满栈：true
性能和局限性
性能： 假设n为栈中元素的个数。在基于简单数组的栈实现中，各种栈操作的算法复杂度如下表所示。
| 空间复杂度（用于n次push操作） | $O(n)$ |
|---|---|
| push()的时间复杂度 | $O(1)$ |
| pop()的时间复杂度 | $O(1)$ |
| size()的时间复杂度 | $O(1)$ |
| isEmpty()的时间复杂度 | $O(1)$ |
| isStackFull()的时间复杂度 | $O(1)$ |
| deleteStack()的时间复杂度 | $O(1)$ |
局限性：栈的最大空间必须预先声明且不能改变。
动态数组实现
在上述基于简单数组的栈实现方法中，最大的局限就是在于栈的空间是预先声明且固定不变的，为了改进此缺陷有两种解决方法：
- 递增策略——当满栈时，每次将数组的大小增加1。
- 这种增加数组大小的方法开销太大，复杂度高$O(n^2)$。
- 重复倍增——当满栈时，新建一个比原数组空间大一倍的新数组，然后复制元素。
- 空间浪费，但是入栈的复杂度比递增策略低$O(n)$。
1 | class DynArrayStackDemo implements Stack { |
性能和局限性
性能： 假设n为栈中元素的个数。在基于动态数组的栈实现中，各种栈操作的算法复杂度如下表所示。
| 空间复杂度（用于n次push操作） | $O(n)$ |
|---|---|
| push()的时间复杂度 | $O(1)$ |
| pop()的时间复杂度 | $O(1)$ |
| size()的时间复杂度 | $O(1)$(平均) |
| isEmpty()的时间复杂度 | $O(1)$ |
| isStackFull()的时间复杂度 | $O(1)$ |
| deleteStack()的时间复杂度 | $O(1)$ |
局限性：倍增太多可能导致内存溢出。
链表实现
使用链表也可以实现栈。通过在链表的表头插入元素的方式实现push操作，删除链表的表头节点（栈顶节点）实现pop操作。
1 | class LLStack implements Stack { |
性能和局限性
性能： 假设n为栈中元素的个数。在基于链表的栈实现中，各种栈操作的算法复杂度如下表所示。
| 空间复杂度（用于n次push操作） | $O(n)$ |
|---|---|
| push()的时间复杂度 | $O(1)$ |
| pop()的时间复杂度 | $O(1)$ (平均) |
| size()的时间复杂度 | $O(1)$ |
| isEmpty()的时间复杂度 | $O(1)$ |
| isStackFull()的时间复杂度 | $O(1)$ |
| deleteStack()的时间复杂度 | $O(n)$ |
局限性：空间浪费。
栈的各种实现方法比较
- 递增策略和倍增策略的比较
- 递增策略：实现push操作的平摊时间开销为$O(n)[O(n^n)/n]$。
- 递增策略：实现push操作的平摊时间开销为$O(1)[O(n)/n]$。
- 基于数组和基于链表实现的比较
- 基于数组实现的栈
- 各个操作都是常数时间开销
- 每隔一段时间倍增操作的开销较大
- n个操作的平摊时间为$O(n)$
- 基于链表实现的栈
- 栈规模的增加和减小都很简洁
- 各个操作都是常数时间开销
- 每个操作都要使用额外的空间和时间开销来处理指针
- 基于数组实现的栈
队列（QUEUE）
“队列”就像是超市收银台前排着的队列，就是一种先输入的数据先输出的数据结构。
主要操作
- enQueue(int data)：在队列的队尾插入一个元素。
- int deQueue()：删除并返回队首的元素。
- int Front()：返回队首的元素，但不删除。
- int QueueSize()：返回队列中储存的元素个数。
- Boolean isEmpty()：指明队列是否储存了元素。
1 | interface Queue { |
队列的应用
- 操作系统根据（具有相同优先级的）人物到达的顺序调度（例如，打印队列）。
- 模拟现实世界中的队列，如售票柜台前的队伍，或者任何需要先来服务的场景。
- 多道程序设计。
- 异步数据传输（文件的输入输出、管道、套接字）。
- 客户在呼叫中心的等待时间。
队列的实现
- 基于简单循环数组的实现方法
- 基于动态循环数组的实现方法
- 基于链表的实现方法
为什么需要循环数组？
首先，分析是否可以借鉴基于简单数组实现栈的方法来实现队列。有队列的定义可知，只能在队列一端执行插入操作，而在另一端执行删除操作。当执行多次插入和删除操作后，就可以很容易地发现使用简单数组实现队列的问题。
如下图例所示，可以清除地看到数组中靠前的空间被浪费了，所以基于简单数组实现队列不是一个有效的方法。为了解决这个问题，假设数组是循环存储的方式，即将数组最后一个元素和第一个元素看作连续的。依据这个假设，如果数组前端有空闲的空间指向队尾的指针就能够很容易地移动到下一个空闲的位置。
提醒：基于简单循环数组和动态循环数组来实现队列与基于数组实现栈的方法非常相似。
简单循环数组实现
队列抽象数据类型的这种简单实现使用数组。在数组中，采用循环增加元素的方法，并使用两个变量分别记录队首元素和队尾元素。通常，使用front变量和rear变量分贝表示队列中的队首元素和队尾元素。
注意：初始化时，front和rear变量的值都赋值为-1，表示队列为空。
几个特殊的点
- 空队判断：判断队首是否是初始化值，$front == -1$
- 满队判断：队尾的下一个索引是否等于队首，(rear+1)%capacity == 使用front变量和rear变量分贝表示队列中的队首元素和队尾元素
- 两个索引变换：
- 下一个队尾，rear = （rear+1）% capacity
- 下一个队首，front = （front+1）% capacity
- 队长：分为两种情况
- 如果rear>front：rear-front+1
- 如果rear<front：capacity+rear-front+1
- 合并两者：size = （capacity+rear-front+1）%capacity
1 | class DLLArrayQueue implements Queue { |
性能和局限性
性能：假设n为队列中元素的个数。
| 间复杂度（用于n次enQueue操作） | $O(n)$ |
|---|---|
| enQueue()的时间复杂度 | $O(1)$ |
| deQueue()的时间复杂度 | $O(1)$ |
| isEmpty()的时间复杂度 | $O(1)$ |
| isFull()的时间复杂度 | $O(1)$ |
| queueSize()的时间复杂度 | $O(1)$ |
局限性：用于实现队列的数组的最大空间必须预先声明且不能改变。试图对一个满队执行入队操作会产生一个针对简单数组这种特定实现队列方式的异常。
动态数组实现
1 | class DynAarrayQueue implements Queue { |
注意：队列操作方法和简单数组类似，增加数组倍增！
链表实现
实现队列的另一种方法是使用链表。通过在链表末端插入元素的方法实现入队（EnQueue）操作。通过删除链表表头元素的方法来实现出队操作（DeQueue）。
1 | class LinkedQueue implements Queue{ |
各种队列实现方法对比
各种队列实现方法的比较与栈类似。
