棧與隊(duì)列 小結(jié)

重點(diǎn)回顧

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

Q & A

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

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

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

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

雙向隊(duì)列像是兩個(gè)棧拼接在了一起，它的用途是什么？

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

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

使用兩個(gè)堆棧，棧 A 用于撤銷，棧 B 用于反撤銷。

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