如何反轉堆棧？

Question

可能是太容易的問題，但請分享如何反轉任何類型的堆棧？

Answer 1

我不說話斯卡拉，但according to the doc you simply call reverse on the stack。

Answer 2

make new stack; 
while (old stack not empty) 
    x = pop(old stack) 
    push x on new stack 

或撥打堆棧reverse，但要注意，如果應用到mutable.Stack返回一個List。如果您使用immutable.Stack，它確實會返回Stack。

Answer 3

只是循環周圍從中彈出值，並推入另一個棧。

Answer 4

public void reverse(Stack st) { 
    int m = (int)st.Pop(); 
    if (st.Count != 1) 
     reverse(st); 
    Push(st , m); 
} 

public void Push(Stack st , int a) { 
    int m = (int)st.Pop(); 
    if (st.Count != 0) 
     Push(st , a); 
    else 
     st.Push(a); 
    st.Push(m); 
} 

Answer 5

正確的答案可能是「不要倒轉堆棧」。

如果某些約束意味着你絕對要扭轉一個堆棧，你的問題已經回答。但是，我忍不住想知道爲什麼想要反轉一個堆棧 - 對我來說，這意味着你正在使用錯誤的數據結構。

如果其所有推，然後反向，那麼所有的持久性有機污染物;這是一個隊列。

如果推動，彈出和反轉按隨機順序混合在一起，您可能需要一個專門支持這些操作的數據結構......當有人讀取「堆棧」但該結構確實是別的東西時，這會令人困惑。

不確定階，但某些語言有雙端隊列特別代表訪問的頭部和尾部元素的線性集合 - 這可能正是你需要的。如果不是，雙鏈表將很好地做到;或者如果一個O（n）012-等效不是一個問題，那麼一個普通的舊列表將會執行。

如果您的pop()等效操作不知道從哪個末端獲取元素（例如，一段代碼正在調用反向，而另一些代碼只是說「給我一個元素」並且不知道是否已調用reverse），請按照以下方式用方向標誌封裝隊列。這將使您獲得相同的功能，而不必實際取消任何操作。

（對不起，我很僞代碼，Scala是不是在我的工具箱）。

ReversableStack { 
    DoublyLinkedList backingStore; 
    Boolean forward; 

    get() { 
     if (forward) return backingStore.take_head(); 
     else return backingStore.take_tail(); 
    } 

    put(item) { 
     if (forward) backingStore.add_head(item); 
     else backingStore.add_tail(item); 
    } 

    reverse() { 
     forward = !forward; 
    } 
}