algorithm - 如何反转堆栈？

Question

可能是这个问题太简单了，但请分享如何反转任何类型的堆栈？

Answer 1

正确的答案可能是“不要反转堆栈”。

如果某些约束意味着您绝对必须反转堆栈，那么您的问题已经得到解答。但是，我忍不住想知道为什么你想要反转堆栈——对我来说，这意味着你使用了错误的数据结构。

如果全推，则反之，则全弹出；那是一个队列。

如果压入、弹出和反转以随机顺序混合，您可能需要一个专门支持这些操作的数据结构……当有人读到“堆栈”时会感到困惑，但该结构实际​​上是另一回事。

不确定 scala，但有些语言有一个双端队列来专门表示一个线性集合，可以访问头元素和尾元素——这可能正是您所需要的。如果没有，双向链表就可以了；或者如果 O(n) pop() 等价物不是问题，那么一个普通的旧列表就可以了。

如果您的 pop() 等效操作不知道从哪一端获取元素(例如，一段代码正在调用 reverse，而其他一些代码只是说“给我一个元素”并且不知道是否已调用 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;
    }
}