如何反转堆栈？

Question

可能是这个问题太容易但请分享如何扭转任何一种堆栈？

Answer 1

正确的答案可能是"不要反转堆栈".

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

如果它全部推动,那么相反,然后所有的弹出; 那是一个队列.

如果推送,弹出和反转以随机顺序混合,您可能需要一个专门支持这些操作的数据结构......当有人读取"堆栈"但结构确实是其他内容时,它会让人感到困惑.

不确定scala,但有些语言有一个双端队列来专门代表一个线性集合,可以访问头部和尾部元素 - 这可能正是你所需要的.如果没有,双重链表就会很好; 如果O(n) - pop()等价不是问题,那么一个普通的旧清单就可以了.

如果您的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;
    }
}

Answer 2

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

或者调用reverse堆栈,但请注意,List如果应用于a ,则返回a mutable.Stack.Stack如果你使用它确实会返回immutable.Stack.

Answer 3

我不会说Scala,但根据文档,你只需要调用reverse堆栈.