How to implement a queue using two stacks?
algorithm, data-structures, queue, stack
Solution
Keep 2 stacks, let's call them `inbox` and `outbox`.
Enqueue:
- 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();
}
}
Problem
Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?