高考申論題
113年
[資訊處理] 資料結構
第 二 題
📖 題組：
四、堆疊（Stack）與佇列（Queue）是常見的資料結構，請回答下列問題： (一)利用雙向佇列（Deque）循序輸入 1, 2, 3, 4, 5, 6, 7，請問能否得到 5174236 的輸出排列？並說明其過程或理由。（10 分） (二)若有 1, 2, 3, 4 四個數字要依序 Push 進堆疊，再於任意時間點 Pop 出堆疊，請列出可能的輸出組合。（15 分）
四、堆疊（Stack）與佇列（Queue）是常見的資料結構，請回答下列問題： (一)利用雙向佇列（Deque）循序輸入 1, 2, 3, 4, 5, 6, 7，請問能否得到 5174236 的輸出排列？並說明其過程或理由。（10 分） (二)若有 1, 2, 3, 4 四個數字要依序 Push 進堆疊，再於任意時間點 Pop 出堆疊，請列出可能的輸出組合。（15 分）
📝 此題為申論題，共 2 小題
小題 (二)
若有 1, 2, 3, 4 四個數字要依序 Push 進堆疊，再於任意時間點 Pop 出堆疊，請列出可能的輸出組合。（15 分）
思路引導 VIP
這是典型的堆疊排列（Stack Permutation）問題。對於 n=4，可能的組合總數符合卡特蘭數 (Catalan Number) $C_4 = rac{1}{n+1} inom{2n}{n} = rac{1}{5} inom{8}{4} = 14$ 種。解題時建議採取系統化的「樹狀列舉」或「排除法」。記住 Stack 的特性是 LIFO，不可能出現「小、大、中」且小的已經在棧底的情況（如 4, 1, 2, 3 是不可能的）。
小題 (一)
利用雙向佇列（Deque）循序輸入 1, 2, 3, 4, 5, 6, 7，請問能否得到 5174236 的輸出排列？並說明其過程或理由。（10 分）
思路引導 VIP
雙向佇列 (Deque) 允許在前端 (Front) 和後端 (Rear) 進行插入和刪除。題目要求按 1-7 順序輸入，目標輸出是 5, 1, 7, 4, 2, 3, 6。解題時要模擬操作過程，若遇到「某個數字被夾在中間且兩端都不是它」的情況，就無法輸出該數字。嘗試模擬每一個輸出的動作。
堆疊排列與卡特蘭數
💡 掌握堆疊 LIFO 特性，並利用卡特蘭數驗算合法輸出組合總數。
| 比較維度 | 堆疊 (Stack) | VS | 佇列 (Queue) |
|---|---|---|---|
| 存取邏輯 | 後進先出 (LIFO) | — | 先進先出 (FIFO) |
| 輸出組合數 | 卡特蘭數 (隨進隨出) | — | 僅 1 種 (循序進出) |
| 限制條件 | 禁止 $p_k < p_i < p_j$ | — | 必須按輸入順序輸出 |
💬堆疊因具備「隨時 Pop」的彈性，使其排列組合遠比佇列複雜。
