呼叫次數來確定堆棧/隊列

Question

問題1

的大小您有ñ條目和空抽象隊列（幫助）一個抽象的棧。大約需要多少個電話才能確定n？之後堆棧需要保持不變。

問題2

同樣的問題，但你開始用abstrack隊列，並有一個空abstrack棧。從堆棧

我的推理

流行 - >推到隊列 - >從隊列中取得 - >放在棧 - >從堆棧彈出 - >推到隊列 - >從隊列中取得 - >把堆棧。我們在某個地方扔了一個計數器，並使其8 * n個呼叫（如果計數器呼叫計數，則爲9 * n）。我看不出還有什麼可以彈出堆棧中的物品，然後以正確的順序將它們取回。 有沒有更好的方法？

Answer 1

Q1。一個更好的解決辦法是：

1. 彈出
2. 排隊
3. 離隊
4. 推

通過這樣做，你會得到4個* n個操作。

例如，讓被堆疊：1，2，3（用1爲頂部）

讓是S中的棧和q中的隊列中。

q.enqueue（s.pop（）），所以現在S = [2,3]和q = [1]

q.enqueue（s.pop（）），所以現在S = [ 3]和q = [1，2]

q.enqueue（s.pop（）），所以現在S = []和q = [1，2，3]

s.push（q .dequeue（）），現在s = [1]和q = [2,3]

s.push（q.dequeue（）），所以現在s = [2,1]和q = [3 ]

s.push（q.deque所以現在s = [2,1]和q = [3]，所以現在s = [3,2,1]並且q = []

q.enqueue（s.pop（））， ]

q.enqueue（s.pop（）），所以現在S = [1]和q = [3,2]

q.enqueue（s.pop（）），所以現在S = []和q = [3,2，1]

s.push（q.dequeue（）），所以現在S = [3]和q = [2,1]

s.push（ q.dequeue（）），所以現在s = [2,3]並且q = [1]

s.push（q。（），所以現在s = [1,2,3]和q = []

我不認爲這可能是最好的解決方案，但是更好的解決方案（9 * n vs 4 * n ，總是爲O（n））

Q2。我認爲，前一種情況相同（不是最佳的）算法可以現在用...

主要的想法是，當你從堆棧得到一個項目，這將是最後的隊列，導致兩個數據結構有不同的輸入方式。

希望這可以幫助你:-)