概述#

Stack 與 Queue 的面試題看似簡單，實則可能相當棘手。有些題目只是對資料結構的小改動，另一些則需要更複雜的解法。熟悉這兩種資料結構的底層運作，是解題的基礎。

Implementing a Stack#

Stack 遵循 LIFO（Last-In First-Out，後進先出） 的原則——就像一疊盤子，最後放上去的盤子會最先被取走。

核心操作#

  • pop()：移除並回傳頂端元素
  • push(item)：將元素加入頂端
  • peek()：回傳頂端元素（不移除）
  • isEmpty()：若 stack 為空則回傳 true

Stack 不提供對第 i 個元素的常數時間存取，但對頂端元素的新增與移除都是常數時間（無需位移元素）。

實作範例#

public class MyStack<T> {
    private static class StackNode<T> {
        private T data;
        private StackNode<T> next;

        public StackNode(T data) {
            this.data = data;
        }
    }

    private StackNode<T> top;

    public T pop() {
        if (top == null) throw new EmptyStackException();
        T item = top.data;
        top = top.next;
        return item;
    }

    public void push(T item) {
        StackNode<T> t = new StackNode<T>(item);
        t.next = top;
        top = t;
    }

    public T peek() {
        if (top == null) throw new EmptyStackException();
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
}

Stack 的常見應用#

  • 遞迴演算法：在遞迴過程中，可以將暫存資料推入 stack；當 backtrack 時再取出。
  • 遞迴轉迭代：Stack 可以用來將遞迴演算法改寫為迭代版本。

Implementing a Queue#

Queue 遵循 FIFO（First-In First-Out，先進先出） 的原則——就像排隊買票，先到的人先被服務。

核心操作#

  • add(item)：將元素加入尾端
  • remove()：移除並回傳頭端元素
  • peek()：回傳頭端元素（不移除）
  • isEmpty()：若 queue 為空則回傳 true

Queue 的 first 與 last 節點的更新邏輯容易出錯，請務必仔細確認。

實作範例#

public class MyQueue<T> {
    private static class QueueNode<T> {
        private T data;
        private QueueNode<T> next;

        public QueueNode(T data) {
            this.data = data;
        }
    }

    private QueueNode<T> first;
    private QueueNode<T> last;

    public void add(T item) {
        QueueNode<T> t = new QueueNode<T>(item);
        if (last != null) {
            last.next = t;
        }
        last = t;
        if (first == null) {
            first = last;
        }
    }

    public T remove() {
        if (first == null) throw new NoSuchElementException();
        T data = first.data;
        first = first.next;
        if (first == null) {
            last = null;
        }
        return data;
    }

    public T peek() {
        if (first == null) throw new NoSuchElementException();
        return first.data;
    }

    public boolean isEmpty() {
        return first == null;
    }
}

Queue 的常見應用#

  • 廣度優先搜尋（BFS）：用 queue 儲存待處理的節點。每次處理一個節點，就將其相鄰節點加入 queue 尾端，確保按層次順序處理。
  • Cache 實作：FIFO 的特性適合用於某些快取淘汰策略。

面試題目列表#

題號題目頁碼
3.1Three in One：用一個陣列實作三個 stackpg 227
3.2Stack Min：設計一個支援 min() 操作（O(1) 時間）的 stackpg 232
3.3Stack of Plates：實作 SetOfStacks，超過容量時自動新增 stackpg 233
3.4Queue via Stacks：用兩個 stack 實作 queuepg 236
3.5Sort Stack：對 stack 排序，最小值在頂端，只可用一個額外 stackpg 237
3.6Animal Shelter：實作先進先出的動物收容所，支援按種類領養pg 239
Backward Linked Lists Trees and Graphs Forward