使用只有一個堆棧實現優先級隊列

Question

使用實現隊列或優先級隊列兩個堆棧並不難。

現在的問題是

1. 如何使用時候只有一個堆棧實施優先級隊列？
2. 如何使用只有一個堆棧執行正常隊列？

他們甚至有可能嗎？

p.s.當然，如果需要，您應該使用constant以外的其他空間，而不是一個堆棧。

Answer 1

不，只能使用通過堆棧接口提供的方法（即只使用push和pop方法）並且具有恆定的額外空間。 ^[1]

考慮嘗試使用堆棧來模擬隊列。當排隊時，如果我們簡單地推入堆棧，我們最終會得到另一個元素，我們需要做一些事情來到隊列的前端去出隊。很容易看出，一堆隊列將使下一個出隊不可能佔用一定數量的空間，因爲所有這些入隊的元素都需要彈出才能到達隊列的前端。我們也可以將入隊的元素放在堆棧頂部的常量元素中，但是這並沒有太大幫助 - 它下面的元素需要首先出隊，所以我們遇到了同樣的問題。試圖將入隊的元素放在堆棧頂部的恆定數量的元素之上當然已經佔用了不止一定的空間量。

現在考慮一個優先級隊列，其中每個新項目的優先級低於隊列中已有的所有項目。這與簡單的隊列是同義的，從上面的論述來看，它不能用具有恆定空間的單個堆棧來模擬。

[1]：如果堆棧實現爲數組或鏈接列表，就像它通常那樣，當然可以使用這些功能，但是我確定那不是您要求的。

Answer 2

假設您將n元素推入堆棧。現在你想要它的底部元素（如果你想實現一個隊列）。您將需要額外的O（n）空間來保留其他n-1元素，以便您可以訪問最下面的元素。

=>在您的約束，只有堆棧接口方法，有沒有辦法，你要實現使用單棧和不斷空間的隊列。

Answer 3

如果您只允許標準堆棧操作（pop,push），則無法執行該任務，因爲排隊項目將意味着從堆棧中彈出所有項目，推送新項目，然後推回所有項目。如果您使用恆定時間，則無法彈出所有項目並使用O(1)內存跟蹤它們。

讓我們假設你使用雙向鏈表實現一個堆棧並允許reverse方法 - 這意味着你翻轉堆棧的順序（鏈表尾部變成尾部）。

現在，對於一個普通的隊列，可以執行：

queue - 再次執行reverse，push新項目，reverse。 dequeue - 執行pop。

注意一旦您允許reverse操作，它不再是標準堆棧。

即使您允許reverse，仍然不可能實現優先隊列，因爲您在排隊或出隊時仍需執行各種比較，並仍會遇到無法存儲所需項目的空間問題比較。

Answer 4

下面是一個技術上正確的解決方案，但幾乎可以肯定無用於您的目的。

我們使用隊列（常規或優先級）的堆棧S。我們初始化S以保存一個空隊列。對於任何隊列操作，我們查看S的頂部元素，並將其應用於適當的隊列操作。這樣，S將永遠只保存一個元素。

如果您認爲堆棧「擁有」其所有元素的內存，則使用堆棧外的零內存。