如何實現兩個堆棧隊列

Question

今天我有一個數據結構考試。其中一個問題是如何實現排隊和排隊的隊列函數s1和s2。我用過這種方法，這是正確的嗎？

enqueue(& item) 
    if(!s2.isEmpty()) 
     s1.push(s2.pop()); 
    s1.push(item); 
dequeue 
    if(!s1.isEmpty()) 
     s2.push(s1.pop()); 
    return s2.pop(); 

Answer 1

通常，如果你有一組這樣的：

[1,2,3,4] 

這裏的問題是，會彈出想在LIFO爲流行，這意味着它會想流行元素4。一個隊列應該彈出FIFO順序和彈出元素1。

爲了獲得這種行爲，我們基本上需要能夠以相反的順序彈出。第二個堆棧可以讓我們實際上反轉堆棧的內容。想象通過堆循環以上，並從它彈出和推內容到另一個棧：

[1,2,3,4] [] 
[1,2,3] [4] 
[1,2]  [4,3] 
[1]  [4,3,2] 
[]  [4,3,2,1] 

現在當我們從第二堆棧中彈出，我們彈出1如所期望。

但要做到這一點，我們必須先通過所有第一個堆棧的元素，並將它們轉移到第二個。所以在入隊/出隊操作中實際上應該有循環來翻轉（反向）這些棧的內容。

這就是第二個堆棧派上用場的地方：它可以讓你通過傳輸反轉堆棧的內容。但你會需要一個循環，因爲想象排隊4個元素。現在要退出隊列，您需要一個循環來反轉內容。您可以將s1作爲推送堆棧，將s2作爲彈出堆棧。看起來你有正確的想法，但我們需要稍微調整：

enqueue(item): 
    while(!s2.isEmpty()) 
     s1.push(s2.pop()); 
    s1.push(item); 

dequeue(item): 
    while(!s1.isEmpty()) 
     s2.push(s1.pop()); 
    return s2.pop();