跳轉至

小結

重點回顧

  • 堆疊是一種遵循先入後出原則的資料結構,可透過陣列或鏈結串列來實現。
  • 在時間效率方面,堆疊的陣列實現具有較高的平均效率,但在擴容過程中,單次入堆疊操作的時間複雜度會劣化至 \(O(n)\) 。相比之下,堆疊的鏈結串列實現具有更為穩定的效率表現。
  • 在空間效率方面,堆疊的陣列實現可能導致一定程度的空間浪費。但需要注意的是,鏈結串列節點所佔用的記憶體空間比陣列元素更大。
  • 佇列是一種遵循先入先出原則的資料結構,同樣可以透過陣列或鏈結串列來實現。在時間效率和空間效率的對比上,佇列的結論與前述堆疊的結論相似。
  • 雙向佇列是一種具有更高自由度的佇列,它允許在兩端進行元素的新增和刪除操作。

Q & A

Q:瀏覽器的前進後退是否是雙向鏈結串列實現?

瀏覽器的前進後退功能本質上是“堆疊”的體現。當用戶訪問一個新頁面時,該頁面會被新增到堆疊頂;當用戶點選後退按鈕時,該頁面會從堆疊頂彈出。使用雙向佇列可以方便地實現一些額外操作,這個在“雙向佇列”章節有提到。

Q:在出堆疊後,是否需要釋放出堆疊節點的記憶體?

如果後續仍需要使用彈出節點,則不需要釋放記憶體。若之後不需要用到,JavaPython 等語言擁有自動垃圾回收機制,因此不需要手動釋放記憶體;在 CC++ 中需要手動釋放記憶體。

Q:雙向佇列像是兩個堆疊拼接在了一起,它的用途是什麼?

雙向佇列就像是堆疊和佇列的組合或兩個堆疊拼在了一起。它表現的是堆疊 + 佇列的邏輯,因此可以實現堆疊與佇列的所有應用,並且更加靈活。

Q:撤銷(undo)和反撤銷(redo)具體是如何實現的?

使用兩個堆疊,堆疊 A 用於撤銷,堆疊 B 用於反撤銷。

  1. 每當使用者執行一個操作,將這個操作壓入堆疊 A ,並清空堆疊 B
  2. 當用戶執行“撤銷”時,從堆疊 A 中彈出最近的操作,並將其壓入堆疊 B
  3. 當用戶執行“反撤銷”時,從堆疊 B 中彈出最近的操作,並將其壓入堆疊 A