Using Stack as Queue

Question

Suppose we have two stacks and no other temporary variable . Is to possible to use it as a queue provided we have associated API i.e push,pop for stack and insert and remove for queue operations.

Answer 1

The time complexities would be worse, though. A good queue implementation does everything in constant time.

Answer 2

Brian's answer is the classically correct one. In fact, this is one of the best ways to implement persistent functional queues with amortized constant time. This is so because in functional programming we have a very nice persistent stack (linked list). By using two lists in the way Brian describes, it is possible to implement a fast queue without requiring an obscene amount of copying.

As a minor aside, it is possible to prove that you can do anything with two stacks. This is because a two-stack operation completely fulfills the definition of a universal Turing machine. However, as Forth demonstrates, it isn't always easy. :-)

Answer 3

You'll have to pop everything off the stack to get the bottom element and then put them all back on for every "dequeue" operation.

Answer 4

Keep 2 stacks, let's call them inbox and outbox.

Queue:
- Push the new element onto inbox

Dequeue:
- If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
- Pop and return the top element from outbox

Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.

Here's an implementation in Java:

public class Queue<E>
{

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}

Answer 5

You can even simulate a queue using only one stack. The second (temporary) stack can be simulated by the call stack of recursive calls to the insert method.

The principle stays the same when inserting a new element into the queue:

• You need to transfer elements from one stack to another temporary stack, to reverse their order.
• Then push the new element to be inserted, onto the temporary stack
• Then transfer the elements back to the original stack
• The new element will be on the bottom of the stack, and the oldest element is on top (first to be popped)

A Queue class using only one Stack, would be as follows:

public class SimulatedQueue<E> {
    private java.util.Stack<E> stack = new java.util.Stack<E>();

    public void insert(E elem) {
        if (!stack.empty()) {
            E topElem = stack.pop();
            insert(elem);
            stack.push(topElem);
        }
        else
            stack.push(elem);
    }

    public E remove() {
        return stack.pop();
    }
}