跳轉到

第一部分：基礎路由（續）

< 上一題：路由表設計 | 返回目錄 | 下一題：QoS 優先權管理 >

場景：緩衝區滿了，封包在排隊

路由器的處理速度跟不上封包湧入的速度。監控顯示：緩衝區使用率 95%，封包開始排隊等待處理。

你看著不斷增長的佇列，開始思考：

「封包來了很多，但我一次只能處理一個。誰先處理？」

這不是小問題。不同的處理順序，會導致完全不同的結果：

  • 先來的先處理？ 公平，但緊急封包可能等太久
  • 後來的先處理？ 某些場景有用，但可能餓死舊封包
  • 兩頭都能進出？ 靈活，但實作複雜

更麻煩的是，路由器還要解析**路由規則表達式**，例如：

(src_ip AND dst_port) OR (protocol == TCP)

這種中綴表達式怎麼有效率地計算？

第 2 題：封包排隊 - Stack、Queue、Deque

這道題將帶你探索三種基礎資料結構，以及一個意想不到的數學連結。

(a) FIFO vs LIFO - 選擇處理順序

3 分 ・ 大二

兩種最基本的排隊策略：

  • FIFO（First In, First Out）：先來先服務，用 Queue 實作
  • LIFO（Last In, First Out）：後來先服務，用 Stack 實作

你需要知道：什麼時候用 Queue？什麼時候用 Stack？

題目：

  1. 寫出 Stack 和 Queue 的基本操作及時間複雜度

  2. 解釋以下場景應該用 Stack 還是 Queue：

    • 路由器封包緩衝區
    • 瀏覽器的「上一頁」功能
    • 印表機工作佇列
    • 函數呼叫的 call stack
    • BFS 遍歷圖

  3. 用**兩個 Stack** 實作一個 Queue（提供 enqueue 和 dequeue 操作）

提示
  • Stack：想像一疊盤子，只能從頂部拿
  • Queue：想像排隊買票，先來的先買
  • 兩個 Stack 怎麼「翻轉」順序？
解答

1. 基本操作：

資料結構 操作 時間複雜度
Stack push(x) - 放入頂部 \(O(1)\)
pop() - 取出頂部 \(O(1)\)
top() - 查看頂部 \(O(1)\)
Queue enqueue(x) - 放入尾部 \(O(1)\)
dequeue() - 取出頭部 \(O(1)\)
front() - 查看頭部 \(O(1)\)

2. 場景分析：

場景 選擇 原因
路由器封包緩衝區 Queue 公平性，先來的封包不應該無限等待
瀏覽器「上一頁」 Stack 最近造訪的頁面最先被返回
印表機工作佇列 Queue 先送的文件先印
函數 call stack Stack 最後呼叫的函數最先返回
BFS 遍歷 Queue 先發現的節點先探索（層序）

3. 用兩個 Stack 實作 Queue：

class QueueWithTwoStacks:
    def __init__(self):
        self.stack_in = []   # 用於 enqueue
        self.stack_out = []  # 用於 dequeue

    def enqueue(self, x):
        self.stack_in.append(x)  # O(1)

    def dequeue(self):
        if not self.stack_out:
            # 把 stack_in 全部倒到 stack_out
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()

原理：Stack 是 LIFO，倒一次變成原順序的反序，再倒一次就恢復原順序。

enqueue 1,2,3:  stack_in = [1,2,3]  (top=3)

dequeue:
  倒到 stack_out: stack_out = [3,2,1]  (top=1)
  pop → 1 ✓（第一個進來的）

時間複雜度：每個元素最多被 push/pop 兩次（進 stack_in 一次，倒到 stack_out 一次），攤銷 \(O(1)\)。

為什麼路由器用 Queue 不用 Stack？

想像你在排隊買票。如果用 LIFO：

  • 你排了 1 小時
  • 新來的人直接插到你前面
  • 你可能永遠買不到票（starvation，餓死現象）

網路封包也一樣。TCP 有重傳機制，如果舊封包一直不被處理，會觸發重傳，產生更多封包，惡性循環。

所以絕大多數緩衝區用 FIFO Queue——公平且可預測。

(b) 路由規則解析 - 中綴轉後綴表達式

3 分 ・ 大二

路由規則常用**中綴表達式**（人類習慣的寫法）：

(A AND B) OR (C AND D)

但電腦計算時，後綴表達式（Postfix / Reverse Polish Notation）更有效率：

A B AND C D AND OR

後綴表達式不需要括號，從左到右掃一遍就能計算。

你需要知道：如何把中綴表達式轉成後綴表達式？

題目：

  1. 用 Stack 實作**中綴轉後綴**演算法（Shunting Yard Algorithm）

  2. 將 A + B * C - D 轉成後綴表達式（假設 * 優先於 +、-）

  3. 說明後綴表達式為什麼**不需要括號**也不會有歧義

提示
  • 操作數直接輸出
  • 運算子要考慮優先順序
  • Stack 用來暫存「還不能輸出」的運算子
解答

1. Shunting Yard Algorithm：

def infix_to_postfix(tokens):
    output = []
    op_stack = []
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, 'AND': 1, 'OR': 0}

    for token in tokens:
        if is_operand(token):
            output.append(token)
        elif token == '(':
            op_stack.append(token)
        elif token == ')':
            while op_stack[-1] != '(':
                output.append(op_stack.pop())
            op_stack.pop()  # 丟掉 '('
        else:  # 運算子
            while (op_stack and
                   op_stack[-1] != '(' and
                   precedence.get(op_stack[-1], 0) >= precedence[token]):
                output.append(op_stack.pop())
            op_stack.append(token)

    while op_stack:
        output.append(op_stack.pop())

    return output

核心規則： - 遇到操作數 → 直接輸出 - 遇到 ( → 推入 Stack - 遇到 ) → 彈出直到遇到 ( - 遇到運算子 → 彈出所有優先順序 ≥ 自己的，然後推入

2. 轉換範例：

輸入：A + B * C - D

Token 動作 Output Stack
A 輸出 A
+ 推入 A +
B 輸出 A B +
* 推入（優先於 +） A B + *
C 輸出 A B C + *
- 彈出 *,+（優先 ≥ -），推入 - A B C * + -
D 輸出 A B C * + D -
結束 彈出全部 A B C * + D -

結果：A B C * + D -

3. 後綴表達式不需要括號：

中綴表達式的歧義來自「運算順序」：

  • A + B * C 是 (A + B) * C 還是 A + (B * C)？

需要括號或優先順序規則來消歧義。

後綴表達式**天生無歧義**：運算子緊跟在它的操作數後面。

A B C * +
└─┬─┘
  先算 B*C，結果設為 T
A T +
└─┬─┘
  再算 A+T

從左到右掃描，遇到運算子就「吃掉」前兩個操作數，沒有任何歧義。

數學小結：表達式求值

後綴表達式求值（用 Stack）：

def eval_postfix(tokens):
    stack = []
    for token in tokens:
        if is_operand(token):
            stack.append(value(token))
        else:
            b = stack.pop()
            a = stack.pop()
            stack.append(apply(token, a, b))
    return stack[0]

時間複雜度：\(O(n)\)，每個 token 處理一次。

© Stack 排列數 - Catalan Number

4 分 ・ 大三

你在設計一個封包重排系統：封包依序進入 Stack，可以選擇任意時機 pop 出來。

輸入序列：\(1, 2, 3, ..., n\)（依序 push）

問題：有多少種不同的輸出序列？

例如 \(n = 3\)：

  • 輸入 1, push; 輸入 2, push; 輸入 3, push; pop, pop, pop → 輸出 3, 2, 1
  • 輸入 1, push; pop; 輸入 2, push; pop; 輸入 3, push; pop → 輸出 1, 2, 3
  • ...

你需要知道：\(n\) 個元素通過 Stack 能產生多少種排列？

題目：

  1. 列出 \(n = 3\) 時所有可能的輸出序列

  2. 判斷序列 3, 1, 2 是否為合法的 Stack 排列（輸入 1, 2, 3）

  3. 設 \(f(n)\) 為 \(n\) 個元素的合法排列數，推導遞迴關係並求解（提示：考慮「1 在輸出中的位置」）

提示
  • 合法排列的特徵：不存在 i < j < k 且輸出順序是 k, i, j
  • 1 是第一個 push 的，它 pop 的時機決定了問題的分割
解答

1. \(n = 3\) 的所有排列：

操作序列 輸出
push 1, push 2, push 3, pop, pop, pop 3, 2, 1
push 1, push 2, pop, push 3, pop, pop 2, 3, 1
push 1, push 2, pop, pop, push 3, pop 2, 1, 3
push 1, pop, push 2, push 3, pop, pop 1, 3, 2
push 1, pop, push 2, pop, push 3, pop 1, 2, 3

共 5 種。

2. 3, 1, 2 是否合法？

嘗試模擬：

  • 要先輸出 3，必須先 push 1, 2, 3
  • Stack 狀態：[1, 2, 3]（底到頂）
  • pop 得到 3 ✓
  • 要輸出 1，但 Stack 頂是 2... 無法！

不合法！

判斷法則：對於輸入 \(1, 2, ..., n\)，序列 \(a_1, a_2, ..., a_n\) 是合法 Stack 排列**若且唯若**不存在 \(i < j < k\) 使得 \(a_k < a_i < a_j\)（231-pattern）。

3, 1, 2 中，\(i=1, j=3, k=2\)：\(a_k=1 < a_i=3\)？不對，讓我重新檢查...

實際上是 312-pattern：不存在 \(a_i > a_k > a_j\) 且 \(i < j < k\)。

3. 遞迴關係：

設 \(C_n\) = \(n\) 個元素的合法 Stack 排列數。

考慮 1 在輸出序列中的位置 \(k\)（\(k = 1, 2, ..., n\)）。

  • 1 是第一個 push 的
  • 如果 1 在位置 \(k\) 輸出，表示：
  • 在 1 被 pop 之前，已經有 \(k-1\) 個元素被 push 和 pop（形成輸出的前 \(k-1\) 個）
  • 1 被 pop 後，剩下 \(n-k\) 個元素繼續操作

關鍵洞察：前 \(k-1\) 個輸出必須來自 \(\{2, 3, ..., k\}\)，後 \(n-k\) 個來自 \(\{k+1, ..., n\}\)，兩者獨立。

\[C_n = \sum_{k=1}^{n} C_{k-1} \cdot C_{n-k}\]

初始條件：\(C_0 = 1\)（空序列有一種排列）

這正是 Catalan Number 的遞迴定義！

解析解：

\[C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! \cdot n!}\]
\(n\) \(C_n\)
0 1
1 1
2 2
3 5
4 14
5 42
Catalan Number 的其他應用

同一個數列出現在很多組合問題中：

問題 對應
\(n\) 對括號的合法配對數 ((())), (()()), ...
\(n+1\) 個節點的不同 BST 數量 每種結構對應一種中序遍歷
凸 \(n+2\) 邊形的三角剖分數 用對角線分成三角形
\(n \times n\) 格子從 \((0,0)\) 到 \((n,n)\) 不越過對角線的路徑數 只能往右或往上

這些問題都有相同的遞迴結構！

(d) Deque - 兩頭都能操作

3 分 ・ 大三

有些場景需要更靈活的操作：Deque（Double-Ended Queue），兩頭都能插入和刪除。

你需要知道：Deque 能做什麼 Stack 和 Queue 做不到的事？

題目：

  1. 寫出 Deque 的基本操作及時間複雜度

  2. 說明如何用 Deque 同時實現 Stack 和 Queue

  3. 滑動窗口最大值問題：給定陣列 nums 和窗口大小 k，求每個窗口的最大值。設計 \(O(n)\) 演算法（提示：Monotonic Deque）

提示
  • Deque = Stack + Queue 的超集
  • Monotonic Deque：維護一個「單調遞減」的 deque
解答

1. Deque 基本操作：

操作 說明 時間複雜度
push_front(x) 從前面插入 \(O(1)\)
push_back(x) 從後面插入 \(O(1)\)
pop_front() 從前面刪除 \(O(1)\)
pop_back() 從後面刪除 \(O(1)\)
front() 查看前面 \(O(1)\)
back() 查看後面 \(O(1)\)

2. 模擬 Stack 和 Queue：

  • Stack：只用一端（如 back）
  • push = push_back

  • pop = pop_back

  • Queue：用兩端

  • enqueue = push_back
  • dequeue = pop_front

3. 滑動窗口最大值（Monotonic Deque）：

def max_sliding_window(nums, k):
    result = []
    dq = collections.deque()  # 存 index

    for i, num in enumerate(nums):
        # 移除超出窗口的元素
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # 維護單調遞減：移除所有比 num 小的
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # 窗口形成後，記錄最大值
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

原理：

  • Deque 存的是 index，對應的值單調遞減
  • dq[0] 永遠是當前窗口的最大值
  • 新元素進來時，把所有比它小的都踢掉（它們不可能成為未來窗口的最大值）

時間複雜度：\(O(n)\)，每個元素最多進出 deque 各一次。

範例：

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0: dq=[0]           (值: 1)
i=1: dq=[1]           (值: 3)，1 被踢掉
i=2: dq=[1,2]         (值: 3,-1)，窗口 [1,3,-1]，max=3
i=3: dq=[1,2,3]       (值: 3,-1,-3)，窗口 [3,-1,-3]，max=3
i=4: dq=[4]           (值: 5)，全被踢掉，窗口 [-1,-3,5]，max=5
i=5: dq=[4,5]         (值: 5,3)，窗口 [-3,5,3]，max=5
i=6: dq=[6]           (值: 6)，窗口 [5,3,6]，max=6
i=7: dq=[7]           (值: 7)，窗口 [3,6,7]，max=7

輸出: [3, 3, 5, 5, 6, 7]

進階挑戰：用 Stack 模擬 Deque

3 分 ・ 大三

你需要知道：能否用 Stack 實現 Deque 的所有操作？攤銷時間複雜度是多少？

題目：

  1. 設計一個資料結構，用 兩個 Stack 模擬 Deque 的四個操作

  2. 分析每個操作的**攤銷時間複雜度**

提示
  • 類似用兩個 Stack 模擬 Queue 的想法
  • 關鍵是「何時重新平衡」
解答

1. 設計：

class DequeWithTwoStacks:
    def __init__(self):
        self.front_stack = []  # 存前半部分（頂部是 front）
        self.back_stack = []   # 存後半部分（頂部是 back）

    def push_front(self, x):
        self.front_stack.append(x)

    def push_back(self, x):
        self.back_stack.append(x)

    def pop_front(self):
        if not self.front_stack:
            self._rebalance_to_front()
        return self.front_stack.pop()

    def pop_back(self):
        if not self.back_stack:
            self._rebalance_to_back()
        return self.back_stack.pop()

    def _rebalance_to_front(self):
        # 把 back_stack 的一半搬到 front_stack
        n = len(self.back_stack)
        mid = n // 2
        temp = []
        # 先把後半部分暫存
        for _ in range(n - mid):
            temp.append(self.back_stack.pop())
        # 把前半部分搬到 front_stack
        while self.back_stack:
            self.front_stack.append(self.back_stack.pop())
        # 把後半部分放回 back_stack
        while temp:
            self.back_stack.append(temp.pop())

    def _rebalance_to_back(self):
        # 對稱操作
        n = len(self.front_stack)
        mid = n // 2
        temp = []
        for _ in range(n - mid):
            temp.append(self.front_stack.pop())
        while self.front_stack:
            self.back_stack.append(self.front_stack.pop())
        while temp:
            self.front_stack.append(temp.pop())

2. 攤銷分析：

使用**勢能法（Potential Method）**：

定義勢能 \(\Phi = |\) |front_stack| - |back_stack| \(|\)

  • push_front/back：實際成本 1，勢能變化 ≤ 1，攤銷成本 ≤ 2
  • pop_front/back（不需 rebalance）：實際成本 1，勢能變化 ≤ 1，攤銷成本 ≤ 2
  • pop（需 rebalance）：假設要搬 \(n\) 個元素，實際成本 \(O(n)\)，但勢能從 \(n\) 降到 0，攤銷成本 \(O(1)\)

結論：所有操作攤銷 \(O(1)\)。

第 2 題小結：你的排隊工具箱

「封包排隊，誰先處理？」
    │
    ├─► (a) 先來先服務？→ Queue (FIFO)
    │       → enqueue/dequeue 都是 O(1)
    │
    ├─► (a) 後來先服務？→ Stack (LIFO)
    │       → push/pop 都是 O(1)
    │       → 用於 call stack、括號配對、undo
    │
    ├─► (b) 解析路由規則？→ 中綴轉後綴
    │       → Shunting Yard Algorithm
    │       → 後綴表達式無歧義、O(n) 求值
    │
    ├─► (c) 排列有多少種？→ Catalan Number
    │       → C_n = (2n)! / ((n+1)! n!)
    │       → 出現在 BST 數量、括號配對等問題
    │
    └─► (d) 兩頭都要操作？→ Deque
            → 四個操作都是 O(1)
            → Monotonic Deque 解決滑動窗口問題
資料結構 特性 典型應用
Stack LIFO，只能從頂部操作 括號配對、call stack、DFS
Queue FIFO，一端進另一端出 任務佇列、BFS、緩衝區
Deque 兩端都能進出 滑動窗口、回文檢查

< 上一題：路由表設計 | 返回目錄 | 下一題：QoS 優先權管理 >