JavaScript 的數組自帶 push 與 pop,行為與經典堆棧完全一致:一端入、同一端出,後進先出(LIFO)。因此不必額外實現棧結構,直接拿數組用就行。
<script type="text/javascript">
var numbers = ["one", "two", "three", "four"];
numbers.push("five");
numbers.push("six");
document.write(numbers.pop()); // six
document.write(numbers.pop()); // five
document.write(numbers.pop()); // four
</script>
push 把元素追加到數組末尾,並返回新的長度。
pop 從末尾取出並刪除一個元素,返回該元素;若數組為空則返回 undefined 而不報錯。
兩者都是原地修改,會直接改變原數組。上例中連續三次 pop 之後,numbers 只剩下 ["one", "two", "three"]。
如果把 push/pop 換成 unshift/shift,就變成「另一端進出」的隊列(FIFO,先進先出):
var queue = [];
queue.push('A'); // 從尾部入隊
queue.push('B');
console.log(queue.shift()); // 'A' —— 最早進去的先出隊
實務上的常見約定是:入隊用 push,出隊用 shift,這樣時間複雜度最合理。反過來(unshift 加 pop)也可以實現隊列,但 unshift 需要搬移所有元素,數據量大時較慢。
用數組模擬棧的典型場景包括:瀏覽器的返回歷史、撤銷操作(undo)棧、遞歸改寫成的顯式棧遍歷,以及同層級菜刀的展開路徑記錄。