您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 面試必考：棧與隊列 6 大經典手寫題深度解析

編輯：Java 相關知識

前言

棧與隊列是數據結構面試的「雙子星」，不僅考察基本操作，更常以「兩個棧實現隊列」「兩個隊列實現棧」「帶 min() 的 O(1) 棧」「合法出棧序列判斷」等變體題目檢驗候選人的邏輯建模與代碼實現能力。本文逐題拆解 6 道高頻面試題，提供完整可運行代碼與核心邏輯圖解，助你面試零失手。

題目一：鏈表實現棧——後進先出 (LIFO)

核心思路

維護 head（底部）與 current（頂部）指針。
入棧：新節點 pre 指向舊 current，current 後移。
出棧：取出 current，current 退回 pre。

public class MyStack {
    private Node head, current;

    public void push(int data) {
        if (head == null) {
            head = current = new Node(data);
        } else {
            Node node = new Node(data);
            node.pre = current;
            current = node;
        }
    }

    public Node pop() {
        if (current == null) return null;
        Node node = current;
        current = current.pre;
        return node;
    }

    static class Node {
        int data;
        Node pre;
        Node(int data) { this.data = data; }
    }
}

題目二：鏈表實現隊列——先進先出 (FIFO)

核心思路

維護 head（隊頭）與 curent（隊尾）指針。
入隊：尾插法，curent.next = newNode，curent 後移。
出隊：取出 head，head 後移。

public class MyQueue {
    private Node head, curent;

    public void add(int data) {
        if (head == null) {
            head = curent = new Node(data);
        } else {
            curent.next = new Node(data);
            curent = curent.next;
        }
    }

    public int pop() throws Exception {
        if (head == null) throw new Exception("隊列為空");
        int val = head.data;
        head = head.next;
        return val;
    }

    static class Node {
        int data;
        Node next;
        Node(int data) { this.data = data; }
    }
}

題目三：兩個棧實現一個隊列

核心邏輯：負負得正

stack1 負責入隊，stack2 負責出隊。出隊時若 stack2 為空，將 stack1 全部彈出壓入 stack2，順序反轉兩次，符合 FIFO。

public class TwoStackQueue {
    private Stack<Integer> stack1 = new Stack<>(); // 入隊棧
    private Stack<Integer> stack2 = new Stack<>(); // 出隊棧

    public void push(int data) { stack1.push(data); }

    public int pop() throws Exception {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) stack2.push(stack1.pop());
        }
        if (stack2.isEmpty()) throw new Exception("隊列為空");
        return stack2.pop();
    }
}

關鍵細節：僅當 stack2 為空時才倒數據，否則會破壞順序。

題目四：兩個隊列實現一個棧

核心邏輯：留底換桶

入隊始終進 queue1。出棧時，將 queue1 前 n-1 個元素移至 queue2，最後一個元素即為棧頂彈出；隨後交換兩隊列引用。

public class TwoQueueStack {
    private Queue<Integer> q1 = new ArrayDeque<>();
    private Queue<Integer> q2 = new ArrayDeque<>();

    public void push(int data) { q1.add(data); }

    public int pop() throws Exception {
        if (q1.isEmpty()) throw new Exception("棧為空");
        while (q1.size() > 1) q2.add(q1.poll());
        int top = q1.poll();
        Queue<Integer> tmp = q1; q1 = q2; q2 = tmp; // 交換引用
        return top;
    }
}

題目五：設計含 O(1) min() 的棧

空間換時間：輔助棧同步維護最小值

主棧正常存數據。
輔助棧 minStack 棧頂始終保存當前主棧最小值。
入棧：新元素 ≤ minStack.peek() 時壓入新元素，否則複製當前最小值。
出棧：兩棧同步彈出。

public class MinStack {
    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int data) {
        stack.push(data);
        if (minStack.isEmpty() || data <= minStack.peek()) {
            minStack.push(data);
        } else {
            minStack.push(minStack.peek());
        }
    }

    public int pop() {
        if (stack.isEmpty()) throw new RuntimeException("棧空");
        minStack.pop();
        return stack.pop();
    }

    public int min() {
        if (minStack.isEmpty()) throw new RuntimeException("棧空");
        return minStack.peek();
    }
}

題目六：判斷棧的彈出序列是否合法

模擬入棧出棧過程

用一個輔助棧模擬 pushSeq 入棧，每入一個元素嘗試匹配 popSeq 當前位置，匹配則彈出並前移 popSeq 指針。最終輔助棧為空即合法。

public class StackSequenceValidator {
    public static boolean isValidPopOrder(int[] pushSeq, int[] popSeq) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int v : pushSeq) {
            stack.push(v);
            while (!stack.isEmpty() && stack.peek() == popSeq[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}