How to reverse the Stack?

May be it is too easy question bu开发者_Python百科t Please share how to reverse any kind of stack?

---

The right answer may be "don't reverse a stack."

If some constraint means you absolutely have to reverse a stack, your question is already answered. But, I can't help but wonder why you want to reverse a stack -- to me, that means you are using the wrong data structure.

If its all pushes, then the reverse, then all pops; thats a queue.

If pushes, pops, and reverses are mixed in random order, you probably want a data structure that specifically supports those operations... it will be confusing when someone reads "stack" but the structure is really something else.

Not sure about scala, but some languages have a double-ended queue to specifically represent a linear collection with access to the head and tail elements -- that may be exactly what you need. If not, a doubly-linked list will do nicely; or a plain old list will do if an O(n) pop()-equivalent isn't an issue.

If your pop() equivalent operation isn't aware of which end to get an element from (e.g., one piece of code is calling reverse, and some other code just says "give me an element" and isn't aware of whether or not reverse has been called), encapsulate the queue with a flag for direction as follows. This will give you the same functionality without having to actually reverse anything.

(sorry for the very-pseudo code, scala isn't in my toolbox).

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

---

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

Or call reverse on the stack, but note that that returns a List if applied to a mutable.Stack. It does return a Stack if you use immutable.Stack.

---

I don't speak Scala, but according to the doc you simply call reverse on the stack.

---

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

---

Just loop around popping values from it and pushing them into another stack.