爲什麼使用兩個堆棧來創建一個隊列？

Question

如果使用數組實現，我可以看到使用兩個堆棧的優點，因爲使用數組比堆棧更容易實現堆棧。 但是，如果使用鏈表，優勢是什麼？ 將棧彈出到隊列中的行爲增加了鏈接列表和數組實現的開銷。

Answer 1

這是實現在函數式編程語言隊列單純的功能性的常用方法（不可變的，但在共享結構）列表（例如Clojure中，哈斯克爾，二郎...）：

• 用一雙名單代表第一個列表中的元素處於FIFO順序並且第二個列表中的LIFO順序的隊列
• 通過預先考慮到第二個列表排隊到隊列
• 通過取出隊列中的第一個元素列表
• 如果第一個列表爲空：反轉第二列表，並與它代替第一列表中，並用一個空列表

更換第二列表

（所有的操作除了任何可能的返回值返回新的隊列對象）

關鍵是將一個元素添加到（從）一個純函數列表的前面是O（1），而反向操作是O（n）在所有出列處被分攤，所以它接近於O（ 1），從而爲您提供一個具有不可變數據結構的隊列實現。

Answer 2

這是一個很好的學習經驗，但不是一個實際的。

Answer 3

您可以使用兩個不可變的堆棧來創建一個不可變的隊列。

但是，如果你只是想要一個可變隊列，使用兩個棧是一個很好的方式，使它比使用鏈表更慢和更復雜。

Answer 4

此方法可用於使用兩個原子單鏈表基於堆棧構建lock-free隊列，如由Win32提供的：Interlocked Singly Linked Lists。 該算法可能如liwp's answer中所述，儘管重新打包步驟（第4項）可以進行一些優化。

無鎖數據結構和算法是一個非常令人興奮的（對我們一些人）編程領域，但它們必須非常小心地使用。在一般情況下，基於鎖的算法效率更高。