CS-Notes 算法基石：栈与队列的数组、链表实现原理剖析

2026-09-06 18:19:30作者：贡沫苏Truman

本文基于 CS-Notes 算法笔记中的核心章节展开。该章节以最小化的抽象接口 + 数组/链表双实现的方式，完整演示了栈（LIFO）与队列（FIFO）两类基础线性结构的底层构造。读完本文，你将掌握：为什么栈与队列需要区分为逻辑结构与物理实现两层、如何用"动态扩容数组"与"头插法链表"两种思路实现栈、如何在链表上同时维护队首队尾指针实现队列，并能将这套自建结构与 Java 标准库（Stack/LinkedList/ArrayDeque）及剑指 Offer、Leetcode 经典考题对应起来，真正理解面试中"手写栈与队列"的每一个细节。

1. 为什么先抽象"栈与队列"再谈实现

在算法学习路径中，栈与队列是最先接触的两种受限线性表：它们只允许在表的一端（栈顶 / 队尾追加、队首取出）操作元素。CS-Notes 的算法目录将"栈和队列"与算法分析、排序、符号表并列，正是因为它几乎是一切算法题的"脚手架"——函数调用栈、表达式求值、括号匹配、BFS 的辅助队列全部建立在它之上。

原笔记的第一层设计是先定义行为，再选择实现。它给出了两个独立的抽象接口 MyStack 与 MyQueue，二者均继承自 Iterable<Item>，从而统一约定：任何栈或队列都必须支持迭代遍历，且泛型类型 Item 表明这套结构不关心元素具体是什么。

1.1 栈的抽象接口

栈的语义是 Last In First Out（后进先出）。接口中每一个方法的职责如下：

public interface MyStack<Item> extends Iterable<Item> {

    MyStack<Item> push(Item item);   // 压栈：将元素放入栈顶，返回 this 以支持链式调用

    Item pop() throws Exception;     // 弹栈：取出并移除栈顶元素，空栈时抛异常

    boolean isEmpty();               // 判空

    int size();                      // 返回当前元素个数
}

值得注意的两个细节：

push 返回 MyStack<Item> 自身，这是接口层面刻意为之的**链式调用（fluent API）**设计；
pop 声明抛出 Exception，因为"对空栈弹栈"属于调用方错误，接口用受检异常显式标出该边界。

接口只约束"能做什么"，不约束"怎么做"——这正是原笔记随后给出数组、链表两种实现的意义所在。

2. 栈的数组实现：ArrayStack 的动态扩容原理

2.1 数组栈的核心状态

原笔记以 ArrayStack 演示"用数组表达栈"。数组天然适合栈，因为栈顶就是数组的最后一个有效元素，入栈/出栈都只发生在数组尾部，能做到严格的 O(1) 随机读写：

public class ArrayStack<Item> implements MyStack<Item> {

    // 栈元素数组，只能通过转型来创建泛型数组
    private Item[] a = (Item[]) new Object[1];

    // 元素数量
    private int N = 0;

两个状态变量的含义需要精确理解：

a：存放元素的底层数组，a[0..N-1] 是有效区间，a[N-1] 即栈顶；
N：元素个数，它同时充当"下一个可用下标"的指针。

由于 Java 不允许直接 new Item[]，这里必须"创建 Object[] 后强转"——原注释"只能通过转型来创建泛型数组"点明的是 Java 泛型擦除的经典限制。

2.2 push / pop 的实现与"对象游离"问题

    @Override
    public MyStack<Item> push(Item item) {
        check();
        a[N++] = item;
        return this;
    }

    @Override
    public Item pop() throws Exception {

        if (isEmpty()) {
            throw new Exception("stack is empty");
        }

        Item item = a[--N];

        check();

        // 避免对象游离
        a[N] = null;

        return item;
    }

原笔记代码最容易被忽略、却最值得向面试官展示的，是 pop 中的 a[N] = null;：

若仅将 N 减一，数组中 a[N] 位置仍残留旧对象的引用，栈自身不再需要它，但 GC 无法回收——这种"元素已逻辑删除但物理引用仍存在"的现象称为对象游离（loitering）；
显式置空后，对象可以被正常回收，这是"防内存泄漏"级别的细节，也是数组实现相比朴素 N-- 写法的高级之处。

2.3 check 与 resize：栈的伸缩性

如果数组固定大小，栈要么溢出、要么浪费空间。原笔记通过 check() 在每次 push 与 pop 之后评估容量，使数组随栈的大小伸缩：

    private void check() {

        if (N >= a.length) {
            resize(2 * a.length);

        } else if (N > 0 && N <= a.length / 4) {
            resize(a.length / 2);
        }
    }

    /**
     * 调整数组大小，使得栈具有伸缩性
     */
    private void resize(int size) {

        Item[] tmp = (Item[]) new Object[size];

        for (int i = 0; i < N; i++) {
            tmp[i] = a[i];
        }

        a = tmp;
    }

resize 本身成本为 O(N)（逐元素拷贝），但两个阈值的配合保证了均摊 O(1)：

扩容：元素个数达到数组容量（N >= a.length）时翻倍为 2 * a.length。因为容量每次翻倍，N 次连续 push 触发的 resize 拷贝总量为 1 + 2 + 4 + ... + N ≈ 2N，均摊到每次 push 仍是常数级；
缩容：元素个数降到容量的四分之一（N <= a.length / 4）时减半为 a.length / 2。注意阈值取 1/4 而非 1/2——这是为了避免"push 扩容、pop 缩容"在临界点附近反复震荡（即扩容后马上因一次 pop 触发缩容的抖动），1/4 → 1/2 之间留出了一倍的缓冲区间。这与 CS-Notes 算法 - 算法分析中"均摊分析"章节讨论的思路一脉相承：以少量操作的昂贵代价换取整体操作的廉价均摊。

2.4 逆序遍历的迭代器

因为栈顶在数组末尾，实现"从栈顶向栈底遍历"只需让迭代器从 i = N 向前递减：

    @Override
    public Iterator<Item> iterator() {

        // 返回逆序遍历的迭代器
        return new Iterator<Item>() {

            private int i = N;

            @Override
            public boolean hasNext() {
                return i > 0;
            }

            @Override
            public Item next() {
                return a[--i];
            }
        };
    }
}

这与后续链表实现的迭代顺序一致——两种实现都约定迭代按"从栈顶到栈底"的顺序进行，从而对使用者屏蔽底层差异。

3. 栈的链表实现：ListStack 与头插法

3.1 为什么必须用"头插法"

原笔记对链表栈的实现动机解释得十分透彻：需要使用链表的头插法来实现。原因在于：

若采用"尾插法"，压栈元素落在链表尾部，弹出栈顶元素时需要定位其前驱节点，而单链表只能从头向后遍历，无法 O(1) 回退；
采用头插法后，最后压栈的元素始终处于链表头部，其 next 指针恰好指向前一个压栈的元素。弹栈时让头部指针后移一位，前一个元素立刻成为新栈顶——入栈、出栈都只需操作头指针，复杂度为 O(1)。

3.2 ListStack 的完整实现

public class ListStack<Item> implements MyStack<Item> {

    private Node top = null;
    private int N = 0;

    private class Node {
        Item item;
        Node next;
    }

    @Override
    public MyStack<Item> push(Item item) {

        Node newTop = new Node();

        newTop.item = item;
        newTop.next = top;   // 新节点指向旧栈顶

        top = newTop;        // 新节点成为栈顶

        N++;

        return this;
    }

    @Override
    public Item pop() throws Exception {

        if (isEmpty()) {
            throw new Exception("stack is empty");
        }

        Item item = top.item;

        top = top.next;      // 栈顶后移，完成"删除"
        N--;

        return item;
    }

    @Override
    public boolean isEmpty() {
        return N == 0;
    }

    @Override
    public int size() {
        return N;
    }

    @Override
    public Iterator<Item> iterator() {

        return new Iterator<Item>() {

            private Node cur = top;

            @Override
            public boolean hasNext() {
                return cur != null;
            }

            @Override
            public Item next() {
                Item item = cur.item;
                cur = cur.next;
                return item;
            }
        };
    }
}

链表实现的几个要点与数组实现形成鲜明对比：

每次 push 都创建一个 Node，空间按需分配，无扩容之虞；但每个节点需额外存储 next 指针，内存占用高于数组；
pop 无需处理"游离"：节点被摘除后没有任何指针指向它，GC 自动回收，语言层面的内存安全天然规避了数组实现中的 loitering 问题；
top == null 与 N == 0 等价：实现里同时维护 top 与 N，使判空、计数都保持 O(1)，迭代器则从当前 top 出发沿 next 单向走完整个链表。

3.3 两种实现的取舍

结合上面两节，可以整理出适用于面试与工程选型的对照结论：

维度	ArrayStack（动态数组）	ListStack（头插链表）
入栈/出栈	均摊 O(1)，常数更小	稳定 O(1)
空间	预留容量可能浪费；缩容阈值 1/4 兜底	随元素数精确增长，但每节点带指针开销
扩容	需要 resize 整体拷贝	无拷贝
对象回收	需显式置 null 防游离	天然安全
迭代/随机访问	支持下标随机访问	只能顺序访问

在 CS-Notes 的 Java 容器笔记中可看到同样的结论：JDK 层面，ArrayList 基于动态数组、支持随机访问，LinkedList 基于双向链表、只能顺序访问却可快速在中间插入删除，且"LinkedList 还可以用作栈、队列和双向队列"。本文两种手写实现，正是 JDK 容器设计哲学的微观缩影。

4. 队列抽象与链表实现：ListQueue

4.1 队列的抽象接口

队列的语义是 First In First Out（先进先出），接口方法与栈对称但命名不同——用 add（入队）与 remove（出队）刻意区别于栈的 push/pop，从 API 层面强化"两种受限结构不可混用"的心智模型：

public interface MyQueue<Item> extends Iterable<Item> {

    int size();

    boolean isEmpty();

    MyQueue<Item> add(Item item);

    Item remove() throws Exception;
}

4.2 为什么 first 指针在链表头部

原笔记在队列实现前先回答了一个关键设计问题：first 与 last 哪个放在链表开头？

出队操作要求"让队首元素的下一个元素成为新队首"，这需要 O(1) 地拿到当前队首的 next。链表头节点的 next 天然指向第二个节点，因此 first 应作为链表的头部节点；队尾只负责追加，用 last 指向即可，追加时通过 last.next 连接新节点，无需遍历整个链表。

4.3 ListQueue 的完整实现

public class ListQueue<Item> implements MyQueue<Item> {

    private Node first;   // 队首：链表头
    private Node last;    // 队尾：链表尾
    int N = 0;

    private class Node {
        Item item;
        Node next;
    }

    @Override
    public boolean isEmpty() {
        return N == 0;
    }

    @Override
    public int size() {
        return N;
    }

    @Override
    public MyQueue<Item> add(Item item) {

        Node newNode = new Node();
        newNode.item = item;
        newNode.next = null;

        if (isEmpty()) {          // 空队列：first 与 last 同时指向新节点
            last = newNode;
            first = newNode;
        } else {                  // 非空：从队尾接入
            last.next = newNode;
            last = newNode;
        }

        N++;
        return this;
    }

    @Override
    public Item remove() throws Exception {

        if (isEmpty()) {
            throw new Exception("queue is empty");
        }

        Node node = first;        // 取出队首
        first = first.next;       // 队首后移
        N--;

        if (isEmpty()) {          // 队列被清空时，同步置空 last，避免悬挂引用
            last = null;
        }

        return node.item;
    }

    @Override
    public Iterator<Item> iterator() {

        return new Iterator<Item>() {

            Node cur = first;

            @Override
            public boolean hasNext() {
                return cur != null;
            }

            @Override
            public Item next() {
                Item item = cur.item;
                cur = cur.next;
                return item;
            }
        };
    }
}

实现中有两个极易遗漏、而原笔记代码精确覆盖的细节：

remove 出队后 if (isEmpty()) last = null;：当最后一个元素被移除时，first 已变为 null，但 last 仍指向刚被移除的旧节点。若不清空，下一次 add 时 isEmpty() 为真、会走"同时重置 first/last"分支从而覆盖掉它——清空 last 的意义在于让 last 与 first 的状态始终一致（要么都非空，要么都为空），避免逻辑与内存层面的不一致；
add 对空队列分支的合并：last = newNode; first = newNode; 使首个元素同时成为队首与队尾，这是"空转非空"时两个指针必须同步的临界处理。

遍历方向也与物理语义一致：迭代器从 first 出发沿 next 走到 last，恰好就是元素的出队顺序（FIFO），队列天然可以顺序遍历，这正是它频繁用作 BFS 层级遍历辅助结构的原因。

若要在数组上实现队列，还可选择"环形缓冲区 + 头尾下标"的方案（JDK ArrayDeque 即此思路），以模运算复用已出队空间——原笔记未展开该实现，本文在此不做过度发挥，仅提示这一常见进阶方向。

5. 栈与队列的互相转化：从数据结构到算法题

手写基础实现之外，栈与队列关系的经典考点是如何用它们互相模拟。CS-Notes 分别在剑指 Offer 与 Leetcode 两个系列的笔记中收录了对应原题，可作为本章节的配套练习：

5.1 用两个栈实现队列（剑指 Offer 9）

剑指 Offer 题解 - 9. 用两个栈实现队列的思路是：in 栈负责入队，out 栈负责出队。一个元素进入 in 栈后顺序被反转一次；需要出队时先整体倒入 out 栈，顺序被第二次反转——两次反转相互抵消，最终输出顺序与最初入队顺序一致，即先进入的元素先退出，恰好等价于队列。

其核心实现如下：

Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();

public void push(int node) {
    in.push(node);
}

public int pop() throws Exception {
    if (out.isEmpty())
        while (!in.isEmpty())
            out.push(in.pop());

    if (out.isEmpty())
        throw new Exception("queue is empty");

    return out.pop();
}

这段代码体现的**"只在 out 为空时才批量倒栈"**策略非常关键：它保证每个元素至多被"倒腾"两次（进 in、倒 out），使得 pop 的均摊复杂度为 O(1)，而不是每次出队都全量迁移。

5.2 Leetcode 栈与队列专题

Leetcode 题解 - 栈和队列围绕同一主题收录了六道经典题目，形成完整训练闭环：

用栈实现队列（232）：in2out() 双栈延迟迁移的完整 OO 封装；
用队列实现栈（225）：插入队尾后循环轮转 queue.add(queue.poll())，使新元素最终位于队首，维护后进先出；
最小值栈（155）：用辅助 minStack 同步记录每一步的最小值，将 getMin() 降到 O(1)，对应剑指 Offer 30. 包含 min 函数的栈；
用栈实现括号匹配（20）：遇到左括号压栈、右括号弹栈比对，字符串遍历结束后栈为空则匹配成功；
739 / 503 单调栈问题：利用"栈内元素单调"的性质，一趟扫描找出"下一个更大元素"及其距离/取值。

其中 739 与 503 两题把栈从"容器"升级为"算法武器"：遍历时用栈暂存"尚未找到答案"的下标，一旦当前元素大于栈顶元素，栈顶的答案即被确定并弹出——这正是栈作为最近相关性结构在算法中的典型运用，可作为读完基础实现后的进阶延伸。

6. 小结与延伸阅读

本篇围绕算法 - 栈和队列的完整脉络，梳理了：

抽象先行：MyStack/MyQueue 接口只约定 LIFO/FIFO 行为与迭代能力，为多实现留出空间；
数组栈：动态扩容缩容（翻倍扩容、1/4 阈值缩容）获得均摊 O(1)，pop 显式置 null 规避对象游离；
链表栈：头插法使 push/pop 都只需 O(1) 操作头指针；
链表队列：first 置于链表头以支持 O(1) 出队，出队清空时同步复位 last；
互为镜像的应用：双栈模拟队列、单队列循环轮转模拟栈，并延伸到单调栈等高频面试模型。

建议按仓库内既定路径继续深入：先对照算法 - 算法分析理解本文扩容与倒栈的均摊代价分析，再完成剑指 Offer 题解中 9、30、31 题与 Leetcode 栈和队列专题的全部六题，最后回到 Java 容器看 JDK 中 LinkedList、ArrayDeque、Stack 的实现取舍，即可形成"原理 → 手写 → 真题 → 标准库"的完整知识闭环。

CS-Notes

:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计

项目地址：https://gitcode.com/GitHub_Trending/cs/CS-Notes

登录后查看全文