棧與隊列 小結(jié)

重點回顧

• 棧是一種遵循先入后出原則的數(shù)據(jù)結(jié)構(gòu)，可通過數(shù)組或鏈表來實現(xiàn)。
• 從時間效率角度看，棧的數(shù)組實現(xiàn)具有較高的平均效率，但在擴容過程中，單次入棧操作的時間復(fù)雜度會降低至 O(n) 。相比之下，基于鏈表實現(xiàn)的棧具有更為穩(wěn)定的效率表現(xiàn)。
• 在空間效率方面，棧的數(shù)組實現(xiàn)可能導(dǎo)致一定程度的空間浪費。但需要注意的是，鏈表節(jié)點所占用的內(nèi)存空間比數(shù)組元素更大。
• 隊列是一種遵循先入先出原則的數(shù)據(jù)結(jié)構(gòu)，同樣可以通過數(shù)組或鏈表來實現(xiàn)。在時間效率和空間效率的對比上，隊列的結(jié)論與前述棧的結(jié)論相似。
• 雙向隊列是一種具有更高自由度的隊列，它允許在兩端進行元素的添加和刪除操作。

Q & A

瀏覽器的前進后退是否是雙向鏈表實現(xiàn)？

瀏覽器的前進后退功能本質(zhì)上是“?！钡捏w現(xiàn)。當用戶訪問一個新頁面時，該頁面會被添加到棧頂；當用戶點擊后退按鈕時，該頁面會從棧頂彈出。使用雙向隊列可以方便實現(xiàn)一些額外操作，這個在雙向隊列章節(jié)有提到。

在出棧后，是否需要釋放出棧節(jié)點的內(nèi)存？

如果后續(xù)仍需要使用彈出節(jié)點，則不需要釋放內(nèi)存。若之后不需要用到，Java 和 Python 等語言擁有自動垃圾回收機制，因此不需要手動釋放內(nèi)存；在 C 和 C++ 中需要手動釋放內(nèi)存。

雙向隊列像是兩個棧拼接在了一起，它的用途是什么？

雙向隊列就像是棧和隊列的組合，或者是兩個棧拼在了一起。它表現(xiàn)的是棧 + 隊列的邏輯，因此可以實現(xiàn)棧與隊列的所有應(yīng)用，并且更加靈活。

撤銷（undo）和反撤銷（redo）具體是如何實現(xiàn)的？

使用兩個堆棧，棧 A 用于撤銷，棧 B 用于反撤銷。

1. 每當用戶執(zhí)行一個操作，將這個操作壓入棧 A ，并清空棧 B 。
2. 當用戶執(zhí)行“撤銷”時，從棧 A 中彈出最近的操作，并將其壓入棧 B 。
3. 當用戶執(zhí)行“反撤銷”時，從棧 B 中彈出最近的操作，并將其壓入棧 A 。