AY 22-23 Final Exam - Question A3 (ArrayStack 實作與 LIFO 追蹤)

教授的直觀模型與比喻

把 Stack 想成一個只能從上方開口的品客洋芋片罐，遵守 Last-In-First-Out (LIFO) 原則。
在程式實作上（ArrayStack），你可以把它想像成一個垂直的置物櫃（陣列），而 top 是管理員的手，永遠指向「最後放進去的那件物品」。初始狀態下置物櫃是空的，所以 top 的初始值為 -1（地下室）。

Part 1：堆疊操作實戰演練 (Question A3b)

一開始為空堆疊。依序執行下列 6 個動作，寫出堆疊由 底層到頂層 的內容（Content）。可以做的動作包含：

(i) Push 400

目前 Content： [400]

(ii) Push 500（提示：把 500 疊在 400 上面）

目前 Content： [400, 500]

(iii) Pop（提示：最上面的 500 被拿走了）

目前 Content： [400]

(iv) Pop（提示：又把最上面的 400 拿走了）

目前 Content： []（空）

(v) Push 300

目前 Content： [300]

(vi) Top（教授提示：top 只是偷看，不會把東西拿走）

目前 Content： [300]

補充：此動作會 return 300 給程式，但不會改變堆疊內容。

Part 2：ArrayStack 程式碼實作與批改 (Question A3a)

（i）size() 方法的批改

❌ 錯誤的答案：

return array[i];

問題：這會回傳陣列內容，且程式中並未定義變數 i。題目要求的是「元素數量」。

✅ 正確答案：

return top + 1;

解析：陣列索引從 0 開始，當 top 為 0 時代表有 1 個元素；因此數量為 top + 1。

（ii）isEmpty() 方法的批改

❌ 錯誤的答案：

if (array[i] == 0) { return true; } else { return false; }

問題：判斷堆疊是否為空應該檢查 top 指標，而不是去檢查陣列內容。

✅ 正確答案：

return top == -1;

解析：當 top 等於 -1 時，代表堆疊為空。寫成 return size() == 0; 也完全可以接受。

（iii）pop() 方法的批改

❌ 錯誤的答案：

return array[i];

問題：這只是回傳元素，並沒有改變指標把它從堆疊中「移除」。

✅ 正確答案：

return array[top--];

解析：pop() 要「移除並回傳」。使用後置遞減 top-- 可以先回傳目前 top 指向的元素，然後再把 top 減一。若不想用一行寫法，也可拆成三行：

Object item = array[top];
top--;
return item;

核心操作總結與考試必背

所有操作都圍繞著 top 指標轉動：

💡 教授的精華句（建議背誦以應對簡答題）：
  1. The top pointer is initialized to -1, indicating an empty stack.
  2. The pop operation removes and returns the top element of the stack.
  3. The postfix decrement top-- is used in pop() to return the current element and then decrease the pointer.

結語與下一步

把這個陣列堆疊（ArrayStack）的運作機制搞懂後，面對變形題（例如限制型別、擴充容量、或回傳錯誤處理）都能輕鬆應對。準備好了就可以繼續進入 Section A 的最後一題：Question A4（Queue 與 Circular Array）。