封面画师：ツチヤ     封面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> {
    // 使用之前编写的 ArrayList，而非 JDK 的
    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
/**
 * @author 默烦
 * @date 2020/7/2
 */
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);
        /* 尾 44 33 11 22 首*/
        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<>();
        // 0 1 2 3 4 5 6 7 8 9
        for (int i = 0; i < 10; i++) {
            queue.enQueue(i);
        }
        // null null null null null 5 6 7 8 9
        for (int i = 0; i < 5; i++) {
            queue.deQueue();
        }
        // 15 16 17 18 19 5 6 7 8 9
        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
// 保证要有capacity的容量(不考虑线程安全)
private void ensureCapacity(int capacity){
    // 当前elements.length 为 10，因为默认容量为10
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
    // 新容量为新容量的1.5倍
    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
    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;
    }

    // 保证要有capacity的容量(不考虑线程安全)
    private void ensureCapacity(int capacity) {
        // 当前elements.length 为 10，因为默认容量为10
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        // 新容量为新容量的1.5倍
        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
        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;
    
    // m > 0, n >= 0, n < 2m
    if (n >= m) {
        System.out.println(n - m);
    } else {
        System.out.println(n);
    }

    // m > 0, n >= 0, n < 2m
    // 上述运算等价于：
    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 。