解題說明
Validate Stack Sequences
題目描述：
給定兩個整數序列 pushed 和 popped，兩者都是 1 到 n 的排列。判斷 popped 是否可能是某個合法的棧操作序列的彈出順序（pushed 為壓入順序）。
解題思路： 模擬法：
使用一個輔助棧來模擬壓入和彈出過程：
- 按照
pushed的順序依次壓入元素。 - 每壓入一個元素後，檢查棧頂是否等於
popped中當前應該彈出的元素。若相等就彈出，並移動popped的指標。 - 重複步驟 2 直到棧頂不匹配。
- 最終若棧為空（所有元素都成功彈出），則序列合法。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個元素恰好被壓入和彈出各一次。
空間複雜度：O(n) — 輔助棧最多存放 n 個元素。
虛擬碼
1. Initialize an empty stack and pointer j = 0 for popped array.
2. For each value in pushed:
a. Push value onto stack.
b. While stack is not empty AND top == popped[j]:
Pop from stack, increment j.
3. Return true if stack is empty, false otherwise.其他解法
原地模擬（O(1) 額外空間）：利用 pushed 陣列本身模擬棧操作，用一個指標 top 追蹤棧頂位置。這樣不需要額外的棧空間。時間複雜度仍為 O(n)。
逆向驗證：從 popped 的最後一個元素開始，反向模擬壓入操作。邏輯對稱但不太直觀。
延伸思考
- 如果不用額外棧，能否用
pushed陣列本身來模擬？如何實現？ - 給定一個壓入序列，共有多少種合法的彈出序列？這與哪個數學概念相關？
- 如果棧有容量限制（最多 k 個元素），如何判斷彈出序列是否合法？