Problem: Queue with Two Stacks

Let’s look at a problem where we build a queue out of another ADT instead of using a queue as a client.

Suppose the only data structure available to you is the Stack from Chapter 10.

The two contracts look like they conflict. A stack returns items in reverse order: push 4, 9, 2, and the top is 2, the last one in. A queue must return them in arrival order: 4 first. The item the queue needs first is the item at the bottom of the stack, and a stack gives no way to get at its bottom.

push order: 4, 9, 2

┌───┐
│ 2 │ ← top: the stack offers this one first
│ 9 │
│ 4 │ ← but the queue must produce this one first
└───┘

So one stack is not enough.

Here is the skeleton of the class:

public class StackQueue<T> implements Queue<T> {
  private Stack<T> in = new LinkedStack<>();
  private Stack<T> out = new LinkedStack<>();

  // ... the four Queue operations go here
}

A StackQueue is a Queue: all four operations must follow the Queue contract. We want enqueue and isEmpty to run in $O (1)$ time. dequeue and front can run in amortized $O (1)$ time. A single dequeue may cost more than $O (1)$ , so part of this problem is to work out what it costs over a sequence of operations.