封面画师：ツチヤ封面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()），这和预先设计相悖。因此选择使用引用的方式：

123456789101112131415161718192021222324public 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);
    }
}

测试代码：

123456789101112public 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，它选择的是继承：

1public 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();

队列的内部实现是否可以直接使用以前学过的数据结构呢？

答案是肯定的，可以选择使用动态数组、链表。优先选择 双向链表，因为队列只在头尾操作元素。

在队列中引用 双向链表，实现其功能：

123456789101112131415161718192021222324252627public 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);
    }
}

测试代码：

1234567891011121314public 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），只不过这是一个接口。

1public interface Queue<E> extends Collection<E> { ... }

接口区别

入队： boolean offer(E e);

出队： E poll();

获取队列的头元素： E peek();

源码实现

在 JDK 中，队列是一个接口，查看 Queue 的实现类，可以看到有个熟悉的家伙 LinkedList，LinkedList 还实现了队列的接口？

123456public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{ 
	// ...
}

查看 Deque 的源码可知，接口 Deque 继承了 Queue 接口：

1public 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 接口实现

12345678910111213141516171819202122232425262728293031323334353637383940414243/**
 * @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);
    }
}

测试代码：

12345678910111213public 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 接口设计

循环队列的接口与普通队列的接口是一样的，但是需要注意与普通队列的区别，其区别就是在循环二字。

接口基本实现：

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364public 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();
    }
}

注意：添加元素（入队）和删除元素（出队）时，需要进行模运算，其主要原因就是在于循环二字。

测试代码：

12345678910111213141516171819public 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 个元素就会报错，因此需要进行动态扩容。循环队列扩容方式与动态数组的扩容方式类似，但也有所区别，区别也是在循环二字。

只有添加数据（入队）时才需要扩容：

1234567public 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

扩容的具体实现：

12345678910111213141516// 保证要有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 索引映射封装

在代码编写中，多次编写了求循环队列索引的代码，可以将其封装一下，便于复用。

123private int index(int index){
    return (front + index) % elements.length;
}

5. 循环双端队列

5.1 接口设计

循环双端队列 ：可以进行两端添加、删除操作的循环队列。

循环双端队列 就是 循环队列 和 双端队列 的结合。想要实现循环双端队列，需要使用到循环队列和双端队列。在实现循环双端队列时，也是采用与循环队列一样的 数组方式来实现 ，而接口则是 选择双端队列的接口 。

不多 BB，直接看实现：😎

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118public 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() 方法进行计算后，得到的是负数，需要规避这种情况：

1234567private int index(int index) {
    index += front;
    if (index < 0) {
        return index + elements.length;
    }
    return index % elements.length;
}

还需要注意 从队首入队 、从队首出队、从队尾入队、 从队尾出队 四个方法的实现。

5.2 模运算优化

应尽量避免乘、除、模、浮点数运算，因为它们的效率很低下。前文的实现中使用的大量的模运算，可以对这些模运算进行优化。

优化方式可以根据下列代码得出：

1234567891011121314151617public 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) 方法进行优化：

12345private int index(int index){
    index += front;
    // 未考虑负数情况 循环队列中不会出现负数
    return index - (index >= elements.length ? elements.length : 0);
}

还可以对 循环双端队列 进行优化：

1234567private 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 < 2 m。

数据结构之栈与队列

文章目录

1. 栈

1.1 基本含义

2.2 接口设计

2.3 应用举例

2. 队列

2.1 基本含义

2.2 接口设计

2.3 JDK 源码

3. 双端队列

3.1 接口实现

4. 循环队列

4.1 基本含义

4.2 接口设计

4.3 动态扩容

4.4 索引映射封装

5. 循环双端队列

5.1 接口设计

5.2 模运算优化