C1: 天王星貨運系統：堆疊與佇列

歡迎來到天王星軌道站！這裡是太陽系外圍的重要補給站。你需要管理兩種不同的貨物系統：

• 堆疊系統（Stack）：後進先出（LIFO），像一疊盤子
• 佇列系統（Queue）：先進先出（FIFO），像排隊結帳

掌握這兩種數據結構是成為高級程式設計師的關鍵！它們是許多進階演算法的基礎。

堆疊（Stack）- 後進先出

想像一疊盤子：最後放上去的盤子，最先被拿走。

    [3]  ← 最後進入，最先離開
    [2]
    [1]  ← 最先進入，最後離開
   -----

基本操作：

• push(x)：將元素 x 放到頂部
• pop()：移除並返回頂部元素
• peek()：查看頂部元素（不移除）
• is_empty()：檢查是否為空

佇列（Queue）- 先進先出

想像排隊：最先排隊的人，最先被服務。

出口 ← [1] [2] [3] ← 入口
      最先進入    最後進入

基本操作：

• enqueue(x)：將元素 x 加到隊尾
• dequeue()：移除並返回隊首元素
• front()：查看隊首元素（不移除）
• is_empty()：檢查是否為空

Python 實現

堆疊：使用 list

stack = []
stack.append(1)  # push
stack.append(2)
top = stack.pop()  # pop，返回 2

佇列：使用 collections.deque

from collections import deque
queue = deque()
queue.append(1)  # enqueue
queue.append(2)
first = queue.popleft()  # dequeue，返回 1

⚠️ 重要：不要用 list.pop(0) 實現佇列！時間複雜度是 O(N)，非常慢！

範例 1：貨櫃堆疊管理

import sys
# 任務：管理貨櫃堆疊
stack = []
n = int(sys.stdin.readline())  # 操作次數
for _ in range(n):
    command = sys.stdin.readline().strip().split()
    
    if command[0] == "PUSH":
        container_id = command[1]
        stack.append(container_id)
        print(f"✅ 貨櫃 {container_id} 已堆疊")
        
    elif command[0] == "POP":
        if stack:
            removed = stack.pop()
            print(f"📦 移除貨櫃 {removed}")
        else:
            print("❌ 錯誤：堆疊為空")
            
    elif command[0] == "PEEK":
        if stack:
            print(f"👀 頂部貨櫃：{stack[-1]}")
        else:
            print("❌ 堆疊為空")
            
    elif command[0] == "SIZE":
        print(f"📊 堆疊大小：{len(stack)}")
print(f"\n最終堆疊：{stack}")

範例 2：太空船維修佇列

import sys
from collections import deque
# 任務：管理太空船維修佇列
queue = deque()
n = int(sys.stdin.readline())
for _ in range(n):
    command = sys.stdin.readline().strip().split()
    
    if command[0] == "ARRIVE":
        ship_id = command[1]
        queue.append(ship_id)
        print(f"🚀 太空船 {ship_id} 加入維修佇列")
        print(f"   目前排隊：{len(queue)} 艘")
        
    elif command[0] == "SERVICE":
        if queue:
            serviced = queue.popleft()
            print(f"🔧 開始維修太空船 {serviced}")
        else:
            print("✅ 沒有太空船等待維修")
            
    elif command[0] == "NEXT":
        if queue:
            print(f"👉 下一艘：{queue[0]}")
        else:
            print("❌ 佇列為空")
print(f"\n等待維修：{list(queue)}")

範例 3：括號配對檢查（經典堆疊應用）

import sys
# 任務：檢查括號是否正確配對
expression = sys.stdin.readline().strip()
stack = []
pairs = {'(': ')', '[': ']', '{': '}'}
valid = True
for i, char in enumerate(expression):
    if char in pairs:  # 左括號
        stack.append(char)
    elif char in pairs.values():  # 右括號
        if not stack:
            print(f"❌ 錯誤：位置 {i} 的 '{char}' 沒有對應的左括號")
            valid = False
            break
        
        left = stack.pop()
        if pairs[left] != char:
            print(f"❌ 錯誤：位置 {i} 的 '{char}' 與 '{left}' 不匹配")
            valid = False
            break
if valid and stack:
    print(f"❌ 錯誤：還有 {len(stack)} 個左括號未配對")
    valid = False
if valid:
    print("✅ 括號配對正確！")

範例 4：逆波蘭表示法計算器

import sys
# 任務：計算逆波蘭表示法（後綴表示法）
# 例如：3 4 + 5  表示 (3 + 4)  5 = 35
tokens = sys.stdin.readline().strip().split()
stack = []
for token in tokens:
    if token in ['+', '-', '*', '/']:
        # 彈出兩個操作數
        b = stack.pop()
        a = stack.pop()
        
        # 執行運算
        if token == '+':
            result = a + b
        elif token == '-':
            result = a - b
        elif token == '*':
            result = a * b
        elif token == '/':
            result = a // b  # 整數除法
        
        stack.append(result)
        print(f"計算：{a} {token} {b} = {result}")
    else:
        # 數字，壓入堆疊
        stack.append(int(token))
        print(f"壓入：{token}")
print(f"\n最終結果：{stack[0]}")

範例 5：滑動窗口最大值（雙端佇列進階應用）

import sys
from collections import deque
# 任務：找出每個大小為 k 的滑動窗口中的最大值
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().strip().split()))
# 使用雙端佇列儲存索引
dq = deque()
result = []
for i in range(n):
    # 移除超出窗口範圍的元素
    while dq and dq[0] < i - k + 1:
        dq.popleft()
    
    # 移除所有比當前元素小的元素（它們不可能是最大值）
    while dq and arr[dq[-1]] < arr[i]:
        dq.pop()
    
    # 加入當前元素的索引
    dq.append(i)
    
    # 當窗口形成後，記錄最大值
    if i >= k - 1:
        result.append(arr[dq[0]])
print(f"陣列：{arr}")
print(f"窗口大小：{k}")
print(f"每個窗口的最大值：{result}")

關鍵技術點

1. 為什麼佇列要用 deque？

| 操作 | list | deque | |------|------|-------| | 尾部添加 | O(1) | O(1) | | 尾部移除 | O(1) | O(1) | | 頭部添加 | O(N) | O(1) | | 頭部移除 | O(N) | O(1) | 使用 list.pop(0) 會導致所有元素向前移動，非常慢！

1. 括號配對的邏輯

   # 遇到左括號：壓入堆疊
   if char in '([{':
       stack.append(char)
   
   # 遇到右括號：檢查是否匹配
   if char in ')]}':
       if stack and matches(stack[-1], char):
           stack.pop()
       else:
           return False  # 不匹配
   

1. 逆波蘭表示法的優勢
2. 不需要括號
3. 計算機容易處理
4. 使用堆疊即可計算

   中綴：(3 + 4) * 5
   後綴：3 4 + 5 *
   
   計算過程：
   3 → [3]
   4 → [3, 4]
   + → [7]        (彈出 3,4，計算 3+4，壓入 7)
   5 → [7, 5]
    → [35]       (彈出 7,5，計算 75，壓入 35)
   

1. 堆疊與遞迴的關係
2. 遞迴本質上使用系統的「呼叫堆疊」
3. 可以用顯式堆疊模擬遞迴
4. 避免 Python 的遞迴深度限制