用兩個堆疊實現佇列：Java 代碼實現與原理分析

核心思想

利用兩個堆疊 stack1（正向存儲，負責入隊）和 stack2（逆向存儲，負責出隊）模擬佇列的先進先出（FIFO）特性。

Java 完整實現

import java.util.Stack;

public class QueueWithTwoStacks<E> {
    private Stack<E> stack1; // 入隊堆疊
    private Stack<E> stack2; // 出隊堆疊

    public QueueWithTwoStacks() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    // 入隊：直接壓入 stack1
    public void appendTail(E e) {
        stack1.push(e);
    }

    // 出隊：若 stack2 為空，將 stack1 所有元素倒入 stack2，再彈出
    public E deleteHead() throws Exception {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()) {
            throw new Exception("Queue is empty!");
        }
        return stack2.pop();
    }
}

原理圖解

• 入隊時：元素依次壓入 stack1，頂端為最新元素。
• 出隊時：若 stack2 為空，將 stack1 所有元素彈出並壓入 stack2，此時 stack2 頂端即為最早入隊的元素，直接彈出即可。
• 後續出隊：直接從 stack2 彈出，直到為空再觸發倒數。

複雜度分析

• 入隊：O(1)
• 出隊：均攤 O(1)（每個元素最多在兩個堆疊間移動一次）