数据结构：堆栈（栈）Stack

作者：小傅哥
博客：https://bugstack.cn (opens new window)
原文：https://mp.weixin.qq.com/s/gyy8_mwI66FRIGJ9zgrUmA (opens new window)

沉淀、分享、成长，让自己和他人都能有所收获！😄

一、前言

堆栈的历史

堆栈于 1946 年进入计算机科学文献，当时当时 Alan M. Turing 使用术语“bury”和“unbury”作为调用子程序和从子程序返回的一种方式。1945 年， Konrad Zuse 的 Z4 中已经实现了子程序。

慕尼黑工业大学的 Klaus Samelson 和 Friedrich L. Bauer 在 1955 年提出了堆栈的想法，并于 1957 年申请了专利。1988 年 3 月，其中在萨梅尔森去世时，鲍尔因发明堆栈原理而获得了 IEEE 计算机先锋奖。Charles Leonard Hamblin 在 1954 年上半年和Wilhelm Kämmerer [ de ] 在 1958 年独立开发了类似的概念。

二、堆栈数据结构

在计算机科学中，堆栈是一种抽象数据类型，用作元素的集合，具有两个主要的操作；

• PUSH：将元素添加到集合
• POP：删除最近添加但尚未删除的元素

堆栈是一种 LIFO（后进先出）的线性的数据结构，或者更抽象说是一种顺序集合，push 和 pop 操作只发生在结构的一端，称为栈顶。这种结构可以很容易地从堆栈顶部取出一个项目，而要到达堆栈更深处的一个项目可能需要先取出多个其他项目。例如；我们经常看到的浏览器访问记录，总是把最近记录展示给你。还包括：一摞书、一叠盘子、一脑瓜子生活琐事。

• 源码地址：https://github.com/fuzhengwei/java-algorithms (opens new window) - Java 算法与数据结构
• 本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/stack (opens new window)

三、实现堆栈结构

当你真的有场景需要使用后进先出堆栈时，一定是不能使用 Java 提供的 Stack 的。因为这个工具类是在 JDK 1.0 阶段开发的，实现的特别粗糙，包括像 synchronized 锁也是直接加到方法上。同时 JDK Stack 类的注解也提醒，使用 ArrayDeque 替代；

• Deque 接口及其实现提供了一组更完整和一致的 LIFO 堆栈操作，应优先使用此类。所以我们本章也是以 ArrayDeque 为原型做代码实现。
• 当小傅哥去翻看 ArrayDeque 时，发现这又是 Doug Lea 老爷子的作品，只要有这大神的存在，这份代码一定很多骚操作！

1. ArrayDeque 介绍

ArrayDeque 是一个基于数组实现的堆栈数据结构，在数据存放时元素通过二进制与运算获取对应的索引存放元素。当数组长度超过初始空间后，进行2的n次幂左移一位扩容，并将数组内容的元素按照分半分别进行迁移。这块逻辑多一些，接下来的内容会以此进行讲解，同时在学习过程中可以在小傅哥提供的源码中完成断点调试，方便快速掌握。

• 堆栈的数据结构是以2的次幂进行初始化，扩容时候为2的倍数。它之所这样是因为保证了在后续计算元素索引位置时，可以进行与运算。也就说 2的n次幂-1 得到的值是一个011111的范围，在与元素索引位置计算时候，找到两个值之间1的位置即可。
• 数据的压栈，压栈是一个在数组中倒放的方式，通过与运算得到索引值。当发生空间不足时扩容迁移数据，会有2次操作。一次是空间的前半段复制，另外一次是后半段复制。
• 最后在数据弹出时，按照空间的元素数量总数开始，同样通过与运算计算索引值。分为弹出队列中未发生迁移的数据，和已经完全迁移好的数据。凡是迁移的数据，都是保证了一个顺序。
• 综上你可能还不是很理解这个数据结构的精妙设计和使用，接下来小傅哥再带着你从代码实现的角度来看下。

2. 添加元素

源码详见：cn.bugstack.algorithms.data.stack.ArrayDeque#push

public void push(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    logger.info("push.idx head：{}", head);
    if (head == tail)
        doubleCapacity();
}

• push 元素的过程相当于找到初始化数组长度的队尾，另外是扩容后从新的队尾开始依次添加元素。此时不用担心元素的输出，因为输出时是从扩容起始点开始输出元素。

3. 扩容空间

源码详见：cn.bugstack.algorithms.data.stack.ArrayDeque#doubleCapacity

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p;
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    /*
     * src      - 源数组
     * srcPos   – 源数组中的起始位置
     * dest     - 目标数组
     * destPos  – 目标数据中的起始位置
     * length   – 要复制的数组元素的数量
     */
    // 第一次拷贝元素：[2、1、4、3] 将数组中的扩容后一半元素拷贝到新数组0开始往后的位置。拷贝4、3
    System.arraycopy(elements, p, a, 0, r);
    // 第二次拷贝元素：[2、1、4、3] 将数组中的前面一半数量的元素，拷贝到新数组后一半开始的位置往后。拷贝2、1
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

• 空间扩容以2的倍数进行操作，以此保证2的幂等。
• System.arraycopy 是操作数据迁移的本地方法，从源数组的某个指定位置，把元素迁移到新数组的指定位置和指定个数个元素。
• 另外是数据迁移，以 [2、1、4、3] 举例；
  • 第一次拷贝元素：[2、1、4、3] 将数组中的扩容后一半元素拷贝到新数组0开始往后的位置。拷贝4、3
  • 第二次拷贝元素：[2、1、4、3] 将数组中的前面一半数量的元素，拷贝到新数组后一半开始的位置往后。拷贝2、1

4. 弹出元素

源码详见：cn.bugstack.algorithms.data.stack.ArrayDeque#pop

public E pop() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    if (result == null) {
        return null;
    }
    elements[h] = null;
    head = (h + 1) & (elements.length - 1);
    logger.info("pop.idx {} = {} & {}", head, Integer.toBinaryString(h + 1), Integer.toBinaryString(elements.length - 1));
    return result;
}

• 按照索引的计算，以此是弹出索引为：6、7、0、1、2、3、4 对应的元素。head 的值从扩容的长度添加元素后逐步减小，所以当前最开始弹出的元素是6索引对应的值。读者可以尝试在添加一个元素，进行验证

四、堆栈功能测试

@Test
public void test_stack() {
    Deque<Integer> deque = new ArrayDeque<>();
    deque.push(1);
    deque.push(2);
    deque.push(3);
    deque.push(4);
    deque.push(5);
    deque.push(6);
    deque.push(7);
    
    logger.info("弹出元素：{}", deque.pop());
    logger.info("弹出元素：{}", deque.pop());
    logger.info("弹出元素：{}", deque.pop());
    logger.info("弹出元素：{}", deque.pop());
    logger.info("弹出元素：{}", deque.pop());
    logger.info("弹出元素：{}", deque.pop());
}

测试结果

07:09:49.407 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head：1
07:09:49.412 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head：0
07:09:49.412 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head：3
07:09:49.412 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head：2
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head：7
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head：6
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head：5
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 6 = 110 & 111
07:09:49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素：7
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 7 = 111 & 111
07:09:49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素：6
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 0 = 1000 & 111
07:09:49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素：5
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 1 = 1 & 111
07:09:49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素：4
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 2 = 10 & 111
07:09:49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素：3
07:09:49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 3 = 11 & 111
07:09:49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素：2

• 从测试结果中可以看到小傅哥添加的日志，打印出所应的添加元素、弹出元素的过程。读者在学习的过程中也可以添加一些额外的日志信息。
• Integer.toBinaryString() 是一个用于打印二进制结果的操作，方便查看二进制的计算。

五、常见面试问题

• 堆栈的使用场景？
• 为什么不是用 Stack 类？
• ArrayDeque 是基于什么实现的？
• ArrayDeque 数据结构使用过程叙述。
• ArrayDeque 为什么要初始化2的n次幂个长度？

六、优秀作业

• 教科书级别栈的数据结构图稿梳理 @Chin (opens new window)