如何反转堆栈？

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; 
    } 
}