封面画师：ツチヤ 封面ID：80414367
本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第一季）
源码仓库：mofan212/data-structure-and-algorithm (github.com)
辅助学习网址：数据结构和算法动态可视化
1. 栈
1.1 基本含义
栈（Stack）是一种特殊的线性表，只能在一端 进行操作。
往栈中添加元素的操作，一般叫做 入栈（push）；从栈中移除元素的操作，一般叫做 出栈（pop），由于只能移除栈顶元素，因此也叫作“弹出栈顶元素”。
栈遵循 后进先出 的原则，Last In First Out，缩写为：LIFO。
注意： 这里所说的“栈”与内存中的“栈空间”是两个不同的概念，但肯定也有相似处，不然为啥都带个栈。
2.2 接口设计
元素的数量： int size();
是否为空： boolean isEmpty();
入栈： void push(E element);
出栈： E pop();
获取栈顶元素： E top();
实现栈可以使用以前学习过的数据结构，比如：动态数组、链表。具体选用哪个都可以，因为栈只能在末尾添加元素，使用这两种数据结构在末尾添加元素的复杂度都是 O(1)。
既然如此，选择使用动态数组实现栈。有两种方式，一种是继承，一种是引用。但是继承有坏处，如果继承动态数组 ArrayList，那么可以在栈中使用动态数组的一些方法（比如 get()、remove()），这和预先设计相悖。因此选择使用引用的方式：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class Stack<E> {
private List<E> list = new ArrayList<>();
public int size(){
return list.size();
}
public boolean isEmpty(){
return list.isEmpty();
}
public void push(E element){
list.add(element);
}
public E pop(){
return list.remove(list.size() - 1);
}
public E top(){
return list.get(list.size() - 1);
}
}
|
测试代码：
1
2
3
4
5
6
7
8
9
10
11
12
| public class Main {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(11);
stack.push(22);
stack.push(33);
stack.push(44);
while (!stack.isEmpty()){
System.out.println(stack.pop());
}
}
}
|
JDK 官方也提供了栈的实现，名字也叫 Stack，它选择的是继承：
1
| public class Stack<E> extends Vector<E> { ... }
|
它继承了 Vector，Vector 和动态数组类似，但它是线程安全的，因此使用官方 JDK 的 Stack 可以使用动态数组的方法。
2.3 应用举例
浏览器的前进、后退就使用了栈，只不过是两个栈的结合使用。
应用说明
假设现在有两个栈，分别叫 A、B。
先访问网址 a，a 的信息存入栈 A；然后又访问网址 b，将 b 的信息存入栈 A；最后访问网址 c，将 c 的信息存入栈 A。这时栈 A 的栈顶是网址 c，浏览器上显示的也是网址 c 的信息。
如果点击浏览器上的“后退”，此时会将栈 A 的栈顶元素弹出并放入到栈 B 中。这种情况下，栈 A 的栈顶元素是 b，浏览器上也将显示网址 b 的信息。再点击“后退”，将栈 A 的栈顶元素弹出并放入到栈 B 中。此刻，栈 A 的栈顶元素是 a，浏览器上显示的也是网址 a 的信息。
如果点击“前进”，那么会将栈 B 的栈顶元素弹出并放入到栈 A 中。此刻，栈 A 的栈顶元素是 b，浏览器上显示的也是网址 b 的信息。
如果又访问了网址 d，那么就会将 d 的信息存入栈 A，而栈 B 会被清空。
此时，栈 A 中的信息为 d - b - a ，而栈 B 是空栈，这代表无法使用“前进”或“后退”访问网址 c 。
再比如，软件的撤销（Undo）、恢复（Redo）功能，也都使用了栈。
2. 队列
2.1 基本含义
队列（Queue）是一种特殊的线性表，只能在 头尾两端 进行操作。
队尾（rear）：只能从队尾添加元素，一般叫做 enQueue，入队。
队头（front）：只能从队头移除元素，一般叫做 deQueue，出队。
队列遵循 先进先出 的原则，First In First Out，缩写为：FIFO。
2.2 接口设计
元素的数量： int size();
是否为空： boolean isEmpty();
入队： void enQueue(E element);
出队： E deQueue();
获取队列的头元素： E font();
队列的内部实现是否可以直接使用以前学过的数据结构呢？
答案是肯定的，可以选择使用动态数组、链表。 优先选择 双向链表，因为队列只在 头尾 操作元素。
在队列中引用 双向链表，实现其功能：
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
| public class Queue<E> {
private List<E> list = new LinkedList<>();
public int size(){
return list.size();
}
public boolean isEmpty(){
return list.isEmpty();
}
public void clear(){
list.clear();
}
public void enQueue(E element){
list.add(element);
}
public E deQueue(){
return list.remove(0);
}
public E front(){
return list.get(0);
}
}
|
测试代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new Queue<>();
queue.enQueue(11);
queue.enQueue(22);
queue.enQueue(33);
queue.enQueue(44);
while (!queue.isEmpty()){
System.out.println(queue.deQueue());
}
}
}
|
2.3 JDK 源码
JDK 官方也提供了队列（Queue），只不过这是一个接口。
1
| public interface Queue<E> extends Collection<E> { ... }
|
接口区别
入队 ： boolean offer(E e);
出队： E poll();
获取队列的头元素： E peek();
源码实现
在 JDK 中，队列是一个接口，查看 Queue 的实现类，可以看到有个熟悉的家伙 LinkedList，LinkedList 还实现了队列的接口？
1
2
3
4
5
6
| public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
}
|
查看 Deque 的源码可知，接口 Deque 继承了 Queue 接口：
1
| public interface Deque<E> extends Queue<E> { ... }
|
Deque 表示双端队列，接着往下看👇
3. 双端队列
双端队列是指能在 头尾 两端 添加 、 删除 的队列。
英文 Deque 是 double ended queue 的简称。
接口设计
元素的数量： int size();
是否为空： boolean isEmpty();
从队尾入队： void enQueueRear(E element);
从队头出队： E deQueueFront();
从队头入队： void enQueueFront(E element);
从队尾出队： E deQueueRear();
获取队列的头元素： E front();
获取队列的尾元素： E rear();
3.1 接口实现
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
|
public class Deque<E> {
private List<E> list = new LinkedList<>();
public int size(){
return list.size();
}
public boolean isEmpty(){
return list.isEmpty();
}
public void clear(){
list.clear();
}
public void enQueueRear(E element){
list.add(element);
}
public E deQueueFront(){
return list.remove(0);
}
public void enQueueFront(E element){
list.add(0, element);
}
public E deQueueRear(){
return list.remove(list.size() - 1);
}
public E front(){
return list.get(0);
}
public E rear(){
return list.get(list.size() - 1);
}
}
|
测试代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class Main {
public static void main(String[] args) {
Deque<Integer> deque = new Deque<>();
deque.enQueueFront(11);
deque.enQueueFront(22);
deque.enQueueRear(33);
deque.enQueueRear(44);
while (!deque.isEmpty()){
System.out.println(deque.deQueueRear());
}
}
}
|
4. 循环队列
4.1 基本含义
循环队列 （Circle Queue）底层是用数组实现的。
当需要删除一个元素（出队）时，就将队头指针指向的数据删除，之后使对头指针指向下一个元素。如：上图所示队列需要出队，那么删除元素 11，然后将 front 指向索引 1。
如果需要添加一个元素（入队），直接在末位索引后添加元素即可。如：上图所示队列需要入队元素 66，直接在索引 5 位置添加元素 66 即可。
似乎并没有循环？并不是！
还是针对上图所示队列，先出队两个元素（11、22），这时对头指针 front 指向索引 2 的元素，之后进行入队操作，先入队两个元素（66、77），这时数组似乎已满？
其实也不是，索引 1、2 的位置并没有元素。如果要进一步入队元素 88，可以将元素 88 添加至索引 0 的位置。等到整个数组空间全部用完，再进行动态扩容。（这个原理很像动态数组的扩容）
其实队列底层也可以使用 动态数组 实现，并且各项接口也可以优化到 O(1) 的时间复杂度，这个用数组实现并且优化之后的队列就叫作：循环队列 。
4.2 接口设计
循环队列的接口与普通队列的接口是一样的，但是需要注意与普通队列的区别，其区别就是在 循环 二字。
接口基本实现：
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
| public class CircleQueue<E> {
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear(){
for (int i = 0; i < size; i++) {
elements[(front + i) % elements.length] = null;
}
size = 0;
front = 0;
}
public void enQueue(E element) {
elements[(front + size) % elements.length] = element;
size++;
}
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
front = (front + 1) % elements.length;
size--;
return frontElement;
}
public E front() {
return elements[front];
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("capacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
builder.append(", ");
}
builder.append(elements[i]);
}
builder.append("]");
return builder.toString();
}
}
|
注意： 添加元素（入队）和删除元素（出队）时，需要进行模运算，其主要原因就是在于循环二字。
测试代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public static void test2(){
CircleQueue<Integer> queue = new CircleQueue<>();
for (int i = 0; i < 10; i++) {
queue.enQueue(i);
}
for (int i = 0; i < 5; i++) {
queue.deQueue();
}
for (int i = 15; i < 20; i++) {
queue.enQueue(i);
}
System.out.println(queue);
while (!queue.isEmpty()){
System.out.println(queue.deQueue());
}
}
|
4.3 动态扩容
现在队列的默认容量是 10 ，如果插入超过 10 个元素就会报错，因此需要进行动态扩容。循环队列扩容方式与动态数组的扩容方式类似，但也有所区别，区别也是在 循环 二字。
只有添加数据（入队）时才需要扩容：
1
2
3
4
5
6
7
| public void enQueue(E element) {
ensureCapacity(size + 1);
elements[(front + size) % elements.length] = element;
size++;
}
|
扩容步骤：
- 比较所需队列（数组）长度 B 与当前队列（数组）长度 A；
- 如果
A >= B ，直接返回，不进行扩容
- 反之，进行扩容：
- 设置新容量 C 为当前长度（容量）A 的 1.5 倍
- 创建新数组，其长度为 C
- 将原数组（队列）的元素复制到新数组中。 注意头指针 front！
- 将原数组赋值为新数组
- 重置 front
扩容的具体实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
private void ensureCapacity(int capacity){
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(i + front) % elements.length];
}
elements = newElements;
front = 0;
}
|
设置好动态扩容后，可以尝试插入超过默认容量的数据来进行测试。
4.4 索引映射封装
在代码编写中，多次编写了求循环队列索引的代码，可以将其封装一下，便于复用。
1
2
3
| private int index(int index){
return (front + index) % elements.length;
}
|
5. 循环双端队列
5.1 接口设计
循环双端队列 ：可以进行 两端 添加、删除操作的循环队列。
循环双端队列 就是 循环队列 和 双端队列 的结合。想要实现循环双端队列，需要使用到循环队列和双端队列。在实现循环双端队列时，也是采用与循环队列一样的 数组方式来实现 ，而接口则是 选择双端队列的接口 。
不多 BB，直接看实现：😎
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
109
110
111
112
113
114
115
116
117
118
| public class CircleDeque<E> {
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear(){
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
size = 0;
front = 0;
}
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
public E deQueueFront() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
public void enQueueFront(E element) {
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size++;
}
public E deQueueRear() {
int rearIndex = index(size - 1);
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
public E front() {
return elements[front];
}
public E rear() {
return elements[index(size - 1)];
}
private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
}
return index % elements.length;
}
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[index(i)];
}
elements = newElements;
front = 0;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("capacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
builder.append(", ");
}
builder.append(elements[i]);
}
builder.append("]");
return builder.toString();
}
}
|
动态扩容、toString() 与循环队列一样，可以直接沿用逻辑。
但是因为循环双端队列可以从队首、队尾操作，因此将队列指定索引转换为底层数组索引的 int index(int index) 方法要发生改变。
当传入的 index 是负数，且队首元素位于数组索引 0 的位置时，调用 index() 方法进行计算后，得到的是负数，需要规避这种情况：
1
2
3
4
5
6
7
| private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
}
return index % elements.length;
}
|
还需要注意 从队首入队、从队首出队、从队尾入队、从队尾出队 四个方法的实现。
5.2 模运算优化
应尽量避免乘、除、模、浮点数运算，因为它们的效率很低下。前文的实现中使用的大量的模运算，可以对这些模运算进行优化。
优化方式可以根据下列代码得出：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public static void main(String[] args) {
int n = 19;
int m = 10;
if (n >= m) {
System.out.println(n - m);
} else {
System.out.println(n);
}
System.out.println(n - (n >= m ? m : 0));
System.out.println(n % m);
}
|
按照上述代码给出的思路，可以对 循环队列 的 int index(int index) 方法进行优化：
1
2
3
4
5
| private int index(int index){
index += front;
return index - (index >= elements.length ? elements.length : 0);
}
|
还可以对 循环双端队列 进行优化：
1
2
3
4
5
6
7
| private int index(int index) {
index += front;
if (index < 0) {
return index + elements.length;
}
return index - (index >= elements.length ? elements.length : 0);
}
|
已知 n >= 0 ，m > 0，那么 n % m 等价于 n - (m > n ? 0 : m) 的前提条件是：n < 2m 。
