Java 中的栈与队列

「用栈实现队列」听起来像个派对小魔术,直到你意识到它真正在考什么:你是否清楚自己语言里的集合各自要付多少代价,以及你能不能当着面试官的面把摊还时间讲清楚。本课一半是 Java 机制——array、ArrayList、LinkedList、Stack、Queue、Deque 到底怎么表现,细到哪一行声明能不能编译;另一半是经典的栈/队列面试题:LC 232、LC 225、三种写法的 LC 155 Min Stack,以及攻克 LC 84 Largest Rectangle in Histogram 的单调栈。

Java 内存模型:为什么 array 有 O(1) 而 list 没有

Java 里的 array 永远是连续存储。int[] arr 字面上就是 n 个 int 挨着排,所以 arr[i] 只差一次乘法加一次加法——O(1),无需遍历。

再看 Student[] arr = new Student[10]。Student 不是基本类型,所以连续的不是十个 Student 对象——而是十个引用。栈上的变量 arr 指向堆上的一个数组对象,这个数组装着十个指向 Student 对象的指针,而那些对象散落在分配器随手放的任何地方。引用数组本身仍然连续,所以下标访问仍是 O(1);不连续的是对象本身。

相比之下,linked List 完全不连续。每个节点只认识自己的邻居,所以没有下标算术——取第 i 个元素意味着走 i 跳。就这一个事实——连续 vs 串联——生成了下面整张复杂度表;里面没有一项需要死记硬背。

本课顺带复习的一个 Java 基础:访问修饰符。public 到处可见;protected 在包可见的基础上加上子类;default(不写关键字)只在包内可见;private 只在同类内可见。值得花三十秒过一遍,因为一旦你在面试里设计一个类——比如我们接下来要设计的这个——它立刻就用得上。

从零手写一个双向链表

在用 LinkedList 之前,本课先造一个——一道「Design List」练习,顺便当作 Java 构造器和泛型的巡礼。先看节点:

class ListNode<T> {
    public T val;
    public ListNode<T> prev;
    public ListNode<T> next;

    ListNode(T val) { this.val = val; }

    ListNode() {          // 重载:同名,签名不同
        this(null);       // 构造器链——委托给 ListNode(T val)
    }

    ListNode(T val, ListNode<T> next, ListNode<T> prev) {
        this.val = val;
        this.next = next;
        this.prev = prev;
    }
}

class MyLinkedList<T> {
    private ListNode<T> head;
    private ListNode<T> tail;
    private int size;

    public T getVal(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException();  // 比默默返回 null 好
        ListNode<T> cur = head;
        for (int i = 0; i < index; i++) cur = cur.next;  // 没有捷径:O(n) 遍历
        return cur.val;
    }

    public void addFromHead(T val) {
        ListNode<T> newHead = new ListNode<>(val);
        if (head == null) {       // 空表:head 和 tail 是同一个节点
            head = newHead;
            tail = head;
        } else {
            newHead.next = head;
            head.prev = newHead;
            head = newHead;
        }
        size++;
    }

    public void addFromTail(T val) {   // addFromHead 的镜像
        ListNode<T> newTail = new ListNode<>(val);
        if (tail == null) {
            head = newTail;
            tail = head;
        } else {
            newTail.prev = tail;
            tail.next = newTail;
            tail = newTail;
        }
        size++;
    }

    public int getSize() { return size; }
}

那个节点类里有两样东西是纯纯的面试加分项。第一,构造器重载:几个同名构造器,靠签名区分。第二——也是本课老师真正秀了一把的——用 this(...) 做构造器链:无参构造器不重复初始化逻辑,而是带着默认值委托给单参构造器(int 版里是 this(0),泛型化之后是 this(null))。一行代码,零重复,而且它传达出你是真懂这门语言,而不只是会写它的语法。

List 是接口:ArrayList、LinkedList 与声明类型

在 Java 里,List 是一个接口——一份待实现的方法契约:get(i)、set(i, val)、add(val)、add(i, val)、remove(i)、size()、isEmpty()。ArrayList 和 LinkedList 是实现它的类——各自履行整份契约,再各加自己的方法。而且和类不同,接口支持多继承:一个类可以同时实现多个接口,LinkedList 正是靠这一点同时身兼 List、Queue 和 Deque。

ArrayList 是一个可变长数组:初始容量 10,空间用完就分配一个 1.5× 大的新数组,把所有东西拷过去。记住这句话——它是下一节摊还分析的关键。

这里有个大多数候选人会漏掉的微妙点。假设 ArrayList 有一个额外方法 myMethod(),它不在 List 接口里:

• ArrayList<Integer> list = new ArrayList<>(); → list.myMethod() 正常编译。
• List<Integer> list = new ArrayList<>(); → list.myMethod() 编译不过。编译器只把 list 当作 List;你得强转:((ArrayList) list).myMethod()。

声明类型决定你能调用哪些方法;运行时类型决定这些方法做什么。笔记点到的一个小 API 细节同理:Integer.parseInt(s) 返回基本类型 int,而 Integer.valueOf(s) 返回 Integer 对象——类型不同,代价不同,在集合里偶尔行为也不同。顺便记一下问长度的三种不一致约定:arr.length(字段)、string.length()(方法)、list.size()(方法)——高压之下,这是笔误级编译错误的经典来源。

ArrayList vs LinkedList:完整复杂度表

本课的招牌表格,重建如下。每一项都从「连续 vs 串联」推出:

有两行值得特别说明,因为面试官恰好会盯着这两处问:

尾部插入,ArrayList。通常有富余容量 → O(1)。偶尔数组满了 → 分配 1.5× 大的新数组,拷贝 n 个元素 → O(n)。但多久一次?从 10 开始增长,扩容发生在大小 10、15、22、33……——按几何间隔分布。n 次追加的总拷贝工作量是 O(n),所以每次追加的平均代价是 O(1)。这就是摊还分析:没有任何单次操作保证便宜,但整个序列便宜。这套论证下面在 LC 232 会原样再出现一次——它是整节课杠杆率最高的概念之一。

「+ 访问时间」那行小字,LinkedList。删除一个你已经攥在手里的节点是 O(1) 的指针手术——这是双向链表诚实的强项。但如果你得先找到那个节点,就得加上 O(n) 的遍历。笔记把这写成「O(1) + 访问时间」——保留这个说法,因为它证明你分得清操作本身和抵达它的路程。

Stack、Queue、Deque:什么能 new,什么不能

Java 的栈/队列版图是一片「它是类还是接口?」的雷区——面试官爱用一行声明语句做快速能力探测。所有情况背后的规则:左边声明的类型必须是右边类型的同一个类、父类,或它所实现的接口。

Stack<Integer> st  = new Stack<>();         // OK —— Stack 是具体类
List<Integer>  st2 = new Stack<>();         // OK —— Stack 实现了 List
List<Integer>  st3 = new LinkedList<>();    // OK —— LinkedList 实现了 List
Stack<Integer> st4 = new LinkedList<>();    // NO —— LinkedList 不是 Stack 的子类

Queue<Integer> q   = new LinkedList<>();    // OK —— LinkedList 实现 Deque ⊂ Queue
Deque<Integer> dq  = new LinkedList<>();    // OK —— 当栈或队列都行
Queue<Integer> q2  = new Queue<>();          // NO —— Queue 是接口,不能 new

PriorityQueue<Integer> pq = new PriorityQueue<>();  // OK —— PriorityQueue 是类
Queue<Integer>         pq2 = new PriorityQueue<>();  // OK —— 这才是惯用写法

一口气讲完这套分类:Stack 是类(你也可以只在头部单端操作,拿 LinkedList 自己撸一个栈);Queue 和 Deque 是接口,最常实例化成 LinkedList;PriorityQueue 是实现了 Queue 的类。Deque 既是 FIFO 又是 FILO——同一个结构,取决于你碰哪一端,既能当队列也能当栈。

Deque 的 API 是一张严格的 2×2×3 网格——头或尾、失败抛异常或返回特殊值、插入/删除/查看:

LC 232 —— 用栈实现队列

一个栈做不到——把 FILO 反转成 FIFO 需要第二次反转。所以:两个栈。设计问题是何时反转,而两个答案的价签天差地别。

解法 0 —— push 时重排。始终把「队列顺序」维持在 st 里:每次 push 都把 st 倒进一个缓冲栈,把新元素放到底部,再全部倒回来。pop 和 peek 是 O(1),但每次 push 都是 O(n)。正确,而且有教学价值,因为它把下一个想法衬托得格外漂亮。

解法 1 —— 惰性重排,在 pop/peek 时做。push 永远落进 st1,O(1)。pop 和 peek 从 st2 读——只有 st2 空了才把 st1 整个翻过去。已经躺在 st2 里的元素本来就是反转后(即队列)顺序,所以我们从不把任何东西翻两次:

class MyQueue {
    private Stack<Integer> st1;   // in-stack:所有 push 都进这里
    private Stack<Integer> st2;   // out-stack:装着已经是队列顺序的元素

    public MyQueue() {
        st1 = new Stack<>();
        st2 = new Stack<>();
    }

    public void push(int x) {
        st1.push(x);              // O(1) —— 写路径上不做任何重排
    }

    public int pop() {
        if (!st2.isEmpty()) return st2.pop();
        while (!st1.isEmpty()) {
            st2.push(st1.pop());  // 只有 out-stack 空了才转移
        }
        return st2.pop();
    }

    public int peek() {
        if (!st2.isEmpty()) return st2.peek();
        while (!st1.isEmpty()) {   // 和 pop 一样的转移——可复用逻辑
            st2.push(st1.pop());
        }
        return st2.peek();
    }

    public boolean empty() {
        return st1.isEmpty() && st2.isEmpty();
    }
}

为什么单次 pop 可能 O(n),整体却是摊还 O(1)?追踪一个元素的一生:它被 push 进 st1 一次,transfer 到 st2 一次,pop 出去一次——无论周围发生多少次 pop,它这辈子最多经历三次栈操作。所以 n 个元素总共最多产生约 3n 次操作,平均每次操作 O(1)。这是 ArrayList 扩容那套论证换了身戏服——认出这个模式一次,以后你就再不用在高压下重新推导。

LC 225 —— 用队列实现栈

镜像问题,配一份镜像的解法菜单。解法 1:「用 Deque」——技术上属于队列家族的结构,本课把它归到能证明你懂 API 的玩笑答案一类。解法 2:两个队列——能用,但 push 和 pop 不可能都 O(1),而且在这里玩两个队列什么好处也换不来。解法 3 才是留下的那个:一个队列,push 时旋转。新元素到来时,先入队,再把排在它前面的所有元素依次出队再入队。最新的元素现在到了队头——而且永久待在那儿——所以队头的行为和栈顶一模一样:

class MyStack {
    Queue<Integer> q;

    public MyStack() {
        this.q = new LinkedList<>();
    }

    public void push(int x) {
        q.offer(x);
        for (int i = 0; i < q.size() - 1; i++) {
            q.offer(q.poll());   // 旋转:所有旧元素轮到新元素后面
        }
    }

    public int pop()  { return q.poll(); }   // 队头 == 栈顶
    public int top()  { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

代价:push O(n),pop 和 top O(1)。注意它和 LC 232 的不对称——那边,惰性给我们换来两边都摊还 O(1);这边,旋转必须在 push 时急切地做,因为队列没法免费反转自己。能说清楚为什么这两道题不完美对称,恰恰是那种把「正确答案」升级成「强答案」的观察。

LC 155 —— Min Stack 的三种写法

设计一个支持 push、pop、top、getMin 的栈——全部 O(1)。三种解法层层递进才是真正的课:每一种都用多一点巧劲换少一点内存。

解法 1 —— 两个同步栈。一个数据栈加一个亦步亦趋的 min 栈:每次 push 也 push min(x, minStack.peek()),每次 pop 两个都弹。轻松正确,O(n) 额外空间,不需要任何巧思——一个完全合格的第一答案。

解法 2 —— 一个栈,min 改变时把旧 min 压进去。只保留一个 min 变量;诀窍在于记住之前的最小值。每当一个新值成为新的最小值,就把即将退位的旧最小值压在它下面当面包屑:

class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<>();

    public void push(int x) {
        if (x <= min) {          // min 即将改变:先把旧 min 埋进去
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        if (stack.pop() == min) min = stack.pop();  // 挖出上一个 min
    }

    public int top()    { return stack.peek(); }
    public int getMin() { return min; }
}

注意 push 里用的是 <= 而不是 <——当最小值有重复时,每一份都必须留下自己的面包屑,否则弹出其中一个重复值时会过早地恢复一个更旧的 min。

解法 3 —— 一个栈,存差值。炫技版:压入 x - min(用 long,因为差值可能溢出 int)而不是 x。一个存进去的负值就是「这次 push 时最小值变过」的化石记录——于是 pop 时,负值告诉你要恢复 min = min - pop;top 时,一个非正的 peek 意味着当前值本身就是 min。一个栈,一个变量,不存重复数据——同时也漂亮地演示了「额外信息」可以编码成一个增量,而不必原样存下来。

本课还抛出一道同一路子的收尾谜题:只用栈做选择排序(两三个栈,汉诺塔风格)。st1 装所有值;把它们倒进 st2,同时记录这一轮的最小值;把最小值停到第三个栈里(或倒回去、把 min 单独留下),重复。它是 O(n²),没人会真拿去用——但它逼你思考一次两栈之间的倾倒会保留下什么信息,而这正是 LC 232 和 Min Stack 锻炼的同一块肌肉。

LC 84 —— Largest Rectangle in Histogram

本课最难的一题,也是一件将在你余下面试生涯里持续收租的工具的首秀:单调栈。给定柱子高度,求能塞进直方图下方的最大矩形。暴力枚举每个 (左, 右) 对——O(n²)。单调栈一趟搞定:

public class Solution {
    public int largestRectangleArea(int[] height) {
        int len = height.length;
        Stack<Integer> s = new Stack<>();     // 存的是一段非递减序列的下标
        int maxArea = 0;
        for (int i = 0; i <= len; i++) {
            int h = (i == len ? 0 : height[i]); // 末尾高度为 0 的哨兵把栈清空
            if (s.isEmpty() || h >= height[s.peek()]) {
                s.push(i);                       // 还在爬升——先不下判断
            } else {
                int tp = s.pop();                // 这根柱子的矩形现在定了
                maxArea = Math.max(maxArea,
                    height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
                i--;                             // 让 i 和下一个栈顶重新比较
            }
        }
        return maxArea;
    }
}

不变量:栈里保存的下标,其对应高度是非递减的。只要柱子还在往上爬,就没有任何矩形的命运被敲定——压栈,继续走。一旦来了一根更矮的柱子,栈里每一根更高的柱子都刚刚找到了它的右边界,于是逐个弹出并结算它的最佳矩形:高度是 height[tp],宽度是新栈顶和 i 之间敞开的走廊。

每个下标压入一次、弹出一次——2n 次栈操作,总计 O(n)。同一套「先搁置,直到撞上你的边界」模式驱动着 Daily Temperatures、Trapping Rain Water 和 Maximal Rectangle;LC 84 是它的经典入口。

更小的栈套路:去重与计算器

两个快速套路给工具箱收尾,都值得在你的脑内索引里占一句话:

消除相邻重复。一个栈能把 abbbacd → abacd → acd 这样的字符串塌缩:扫描字符,当进来的字符和栈顶匹配(或和栈顶凑成一段可消除的连续段)时,弹出而不是压入——并注意删除是如何级联的,因为删掉那段 b 让两个 a 相遇。这就是 Remove All Adjacent Duplicates 家族(LC 1047 及其计数变体)背后的引擎。

表达式求值。对于像 a + b * c 这样的中缀表达式,跑两个栈——一个装数字,一个装运算符——把低优先级运算符搁置,让高优先级的先解决;这就是 Basic Calculator 系列(LC 224 / 227)的骨架。而本课收尾抛出的编译原理级妙语是:先把表达式转成逆波兰式(a*b+c*d → ab*cd*+),求值就只需要一个栈——见到数字就压,见到运算符就弹两个、算、压回去。这就是 LC 150 Evaluate Reverse Polish Notation,也正是机器实际求值表达式的方式:第二个栈从头到尾只是为了处理优先级,而 RPN 把优先级烘焙进了顺序里。

刷题清单