普通考試
115年
[電信工程] 計算機概要
第 15 題
某程式產出一個資料序列，依 A、B、C 的順序（A 最先）輸入到一個空的堆疊（Stack），藉由推入（Push）、彈出（Pop）的動作以改變原本的資料順序，總共有幾種可能的輸出順序？
- A 6 種
- B 5 種
- C 4 種
- D 3 種
思路引導 VIP
想像你正在將三本書 A、B、C 依序放入一個狹窄的箱子裡。如果你希望最後拿出來的第一本書是 C（也就是箱子最底下的 A 和中間的 B 都還沒被拿出來過），那麼在拿完 C 之後，剩下的 A 和 B 還有選擇誰先誰後的餘地嗎？為什麼？
🤖
AI 詳解
AI 專屬家教
恭喜你精準地掌握了資料結構中**堆疊（Stack）**的核心邏輯！這道題目考查的是經典的「後進先出（LIFO, Last-In-First-Out）」原理，並結合了排列組合的限制條件，是檢驗演算法基礎非常好的切入點。
堆疊運算的組合約束
在處理這類問題時，我們可以觀察到，雖然三個元素 $n=3$ 的全排列共有 $3! = 6$ 種，但堆疊的特性會限制某些序列的產生。當一個元素被彈出（Pop）時，所有比它早進入堆疊且尚未彈出的元素，勢必會被「壓」在下方，並以相反的順序依序產出。以本題為例，若要讓 C 成為第一個輸出的元素，則 A 與 B 必須都已在堆疊中（且 B 在 A 之上），這意味著接下來的順序絕對只能是 B 然後才是 A。因此，序列 「CAB」 在堆疊邏輯下是不可能發生的，這也是唯一被排除的組合。
▼ 還有更多解析內容