高考申論題
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 小題
小題 (一)
利用雙向佇列（Deque）循序輸入 1, 2, 3, 4, 5, 6, 7，請問能否得到 5174236 的輸出排列？並說明其過程或理由。（10 分）
思路引導 VIP
雙向佇列 (Deque) 允許在前端 (Front) 和後端 (Rear) 進行插入和刪除。題目要求按 1-7 順序輸入，目標輸出是 5, 1, 7, 4, 2, 3, 6。解題時要模擬操作過程，若遇到「某個數字被夾在中間且兩端都不是它」的情況，就無法輸出該數字。嘗試模擬每一個輸出的動作。
小題 (二)
若有 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 是不可能的）。