基於陣列和基於列表的堆棧和隊列

Question

我試圖比較堆棧和隊列操作在作爲數組和鏈表實現時的增長率（運行時間和空間）。到目前爲止，我只能找到隊列pop() s的平均情況下運行時間，但沒有全面探索這兩個數據結構並比較它們的運行時間/空間行爲。

具體而言，我想找來比較兩個隊列和棧push()和pop()，如既陣列和鏈表（因此2操作×2種結構×2個實施方式中，或8個值）來實現。

此外，我會很欣賞這兩種方法的最佳，平均值和最差情況值，以及任何與它們消耗的空間量有關的值。

我能找到的最接近的東西就是這個「所有cs作弊表格的母親」pdf，它明顯是高級算法和離散函數的碩士或博士水平作弊表。

我只是在尋找一種方法來確定何時何地我應該使用基於數組的實現與基於列表的實現兩種堆棧和隊列。

Answer 1

有多種不同的方式來實現鏈表和數組的隊列和堆棧，我不確定你在找哪個。不過，在分析這些結構之前，讓我們回顧一下上述數據結構的一些重要的運行時注意事項。

在只有一個頭指針的單鏈表中，預先設置一個值的代價是O（1） - 我們只需創建新元素，將它的指針連接到指向列表的舊頭，然後更新頭指針。刪除第一個元素的代價也是O（1），這是通過更新頭指針指向當前頭後的元素，然後釋放舊頭的內存（如果執行顯式內存管理）來完成的。然而，由於動態分配的花費，這些O（1）項中的常數因子可能很高。由於在每個元素中存儲額外的指針，鏈表的內存開銷通常是O（n）總額外的內存。

在動態數組中，我們可以訪問O（1）時間中的任何元素。我們還可以在amortized O(1)附加一個元素，這意味着n次插入的總時間是O（n），儘管任何插入的實際時間範圍可能會更糟糕。通常情況下，通過將大部分插入追加到預先分配的空間中來實現動態數組，通過將數組容量加倍並複製元素，可以在少量插入的情況下運行Θ（n）時間。有些技術試圖通過分配額外空間並懶惰地複製元素來減少這種情況（例如，參見this data structure）。通常情況下，動態數組的內存使用情況非常好 - 當數組完全滿時，例如，只有O（1）額外開銷 - 雖然在數組大小加倍後可能會有O（n）未使用在數組中分配的元素。由於分配不頻繁且訪問速度很快，動態數組通常比鏈接列表快。

現在，讓我們考慮如何使用鏈表或動態數組實現堆棧和隊列。有很多方法可以做到這一點，所以我會假設你使用的是以下實現：

• 堆棧：
  • 鏈表：與頭指針singly-linked list。
  • 陣列：作爲dynamic array
• 隊列：
  • 鏈表：作爲具有頭和尾指針單鏈接列表。
  • 數組：作爲由數組支持的circular buffer。

讓我們依次考慮。

堆棧由一個單鏈表支持。因爲單鏈表支持O（1）時間前置和先刪除，推入或彈出到鏈接列表支持的堆棧的開銷也是O（1）最差的情況。但是，添加的每個新元素都需要新的分配，並且與其他操作相比，分配可能很昂貴。

堆棧由動態數組支持。推入堆棧可以通過在動態數組中添加一個新元素來實現，該元素需要分攤O（1）次和最壞情況O（n）時間。從棧中彈出可以通過刪除最後一個元素來實現，最後一個元素運行在最壞的情況下O（1）（或者如果您想嘗試回收未使用的空間，則分期運行O（1））。換句話說，最常見的實現有最好的O（1）push和pop，最壞的O（n）push和O（1）pop，並且分攤O（1）push和O（1）pop。

隊列由一個單鏈表支持。排隊到鏈表中可以通過追加到單鏈表的後面來實現，該鏈表使用最壞情況下的時間O（1）。去隊列可以通過去除第一個元素來實現，這也是最壞情況時間O（1）。這也需要每個入隊的新分配，這可能很慢。

隊列由不斷增長的循環緩衝區支持。通過在循環緩衝區中的下一個空閒位置處插入某些內容，可以進入循環緩衝區。這可以通過在必要時增長數組，然後插入新元素來實現。對動態數組使用類似的分析，這需要最佳情況時間O（1），最壞情況時間O（n）和分期時間O（1）。通過去除循環緩衝區的第一個元素從緩衝區中退出，在最壞的情況下花費時間O（1）。總而言之，所有結構都支持在O（n）時間內推送和彈出n個元素。鏈接列表版本具有更好的最壞情況行爲，但由於執行的分配數量可能會導致整體運行時間更差。陣列版本在最壞的情況下速度較慢，但​​如果每次操作的時間不太重要，則整體性能會更好。

您可能想要考慮實現堆棧的另一個選項是VList，它是一個最近的數據結構，它是鏈接列表和動態數組的混合體。它的分配比鏈接列表少，分配的指針也少一些，儘管在最壞的情況下空間使用率會高一點。您可能還想查看chunklists，這是另一種數組和鏈表的混合體，可用於堆棧和隊列。

希望這會有所幫助！

Answer 2

對不起，如果我誤解了你的問題，但如果我沒有，比我相信這是你正在尋找的答案。

使用矢量，只能在容器的末尾有效地添加/刪除元素。 使用deque，可以高效地在容器的開始/結束處添加/刪除元素。 通過列表，您可以高效地在容器中的任何位置插入/刪除元素。

vectors/deque允許隨機訪問迭代器。 列表只允許順序訪問。

您需要如何使用和存儲數據是您如何確定哪個最合適。

編輯：

還有更多的這個有很多，我的回答很普遍。如果我甚至正在跟蹤你的問題是什麼，我可以進一步深入。