Solution: Pouring Only When Empty

A stack reverses the order of what passes through it, so passing items through two stacks reverses the order twice and restores the original order. If we pour one stack into another, popping each item and pushing it, the item at the bottom ends up on top.

The simplest design pours on every call: keep all the items in one stack, and for each dequeue, pour everything into the second stack, pop the top (which is the oldest item), and pour everything back. This is correct, but every dequeue moves every item twice: $O (n)$ on every call.

We can do better by not pouring back. Once items have been poured into the second stack, they sit in queue order, oldest on top, and we can serve them one pop at a time with no further work. So the two stacks have different jobs: in receives new items, and out serves items in arrival order. We pour only when out is empty.

public class StackQueue<T> implements Queue<T> {
  private Stack<T> in = new LinkedStack<>();   // receives enqueued items
  private Stack<T> out = new LinkedStack<>();  // serves items, oldest on top

  @Override
  public void enqueue(T item) {
    if (item == null) {
      throw new IllegalArgumentException();
    }
    in.push(item);
  }

  @Override
  public boolean isEmpty() {
    return in.isEmpty() && out.isEmpty();
  }

  @Override
  public T front() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    pour();
    return out.top();
  }

  @Override
  public void dequeue() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    pour();
    out.pop();
  }

  // if out is empty, move everything from in to out, reversing the order
  private void pour() {
    if (out.isEmpty()) {
      while (!in.isEmpty()) {
        T item = in.top();
        in.pop();
        out.push(item);
      }
    }
  }
}

Pouring while out still holds items would put newer items on top of older ones, and the newer ones would be served before the older ones.

Here is a trace. enqueue(4) and then enqueue(9) each push onto in:

     in               out
┌───┐               (empty)
│ 9 │ ◀── top
├───┤
│ 4 │
└───┘

The newest item is on top, which is the opposite of the order the queue has to serve. The first dequeue() finds out empty and pours all items from in to out, reversing their order.

     in               out
(empty)          ┌───┐
                 │ 4 │ ◀── top
                 ├───┤
                 │ 9 │
                 └───┘

Now we dequeue 4, which is on top of out:

     in               out
(empty)          ┌───┐
                 │ 9 │ ◀── top
                 └───┘

Now enqueue(2) pushes onto in. At this point both stacks hold something: 2 is in in while 9 is still in out:

     in               out
┌───┐            ┌───┐
│ 2 │ ◀── top    │ 9 │ ◀── top
└───┘            └───┘

The next dequeue() finds out non-empty, so there is no pour: it just pops 9, and 2 stays in in:

     in               out
┌───┐               (empty)
│ 2 │ ◀── top
└───┘

The last dequeue() finds out empty again, pours 2 into out, and pops it, leaving both stacks empty. The items come out 4, 9, 2, in arrival order, even though 2 was enqueued in the middle of the dequeues.

front also calls pour, and that does not break its contract. The pour moves items between the two internal stacks, but the queue’s contents and their order do not change, and a client that only sees the queue through the four operations cannot tell that anything moved.

What does this cost? enqueue is one push and isEmpty is two checks. Both are $O (1)$ . A dequeue or front that finds out non-empty does a check and a pop, so it is $O (1)$ too. The expensive call is the one that pours. It moves every item in in, and that can be all $n$ items in the queue. So a single dequeue can cost $O (n)$ . But the pour does not happen often.

Let’s count the trace first. It has six queue operations: enqueue(4), enqueue(9), dequeue(), enqueue(2), dequeue(), dequeue(). We will count pushes and pops on the two stacks:

enqueue(4) pushes onto in. That is 1 stack operation.
enqueue(9) pushes onto in. That is 1.
The first dequeue() pours two items, and each poured item is one pop from in and one push onto out. That is 4. Then it pops from out. That is 5 in total.
enqueue(2) pushes onto in. That is 1.
The second dequeue() finds out non-empty, so there is no pour. It pops from out. That is 1.
The last dequeue() pours one item, which is 2, then pops from out. That is 3.

The total is $1 + 1 + 5 + 1 + 1 + 3 = 12$ stack operations for 6 queue operations. That is 2 per queue operation on average, even though one of the dequeues cost 5 by itself.

Now count the same 12 a different way, per item instead of per call. Follow the item 4 from enqueue to dequeue. It was pushed onto in, popped from in, pushed onto out, and popped from out. That is 4 stack operations. The item 9 went through the same four. So did the item 2. Three items, 4 each, is $3 \times 4 = 12$ .

Every item gets pushed onto in exactly once, when it is enqueued. It gets poured at most once, because items never move back from out to in. A pour is one pop and one push per item. And it gets popped from out at most once, when it is dequeued. So each item is responsible for at most 4 stack operations from enqueue to dequeue, no matter how many queue operations happen around it.

Now let’s turn that into a bound. Suppose a client makes $m$ queue operations in total, and $n$ of them are enqueues, so $n$ items enter the queue. Each of the $m$ calls does a fixed number of checks on its own. Call that number $c$ . The items account for at most 4 stack operations each. So

total work \leq c m + 4 n \leq c m + 4 m = (c + 4) m .

The first line adds the per-call checks to the per-item stack operations. The second line uses $n \leq m$ , which holds because every item was enqueued by one of the $m$ calls. The third line factors out $m$ .

So $m$ operations cost at most $(c + 4) m$ , which is $O (m)$ . Divide by $m$ and each operation costs $O (1)$ on average. That is what amortized $O (1)$ means.

This is the same argument we made for push in the MonotonicStack practice problem. There, an item is evicted at most once, so an expensive push is paid for by the cheap pushes that placed the items it evicts. Here an item is poured at most once, so the expensive call is the pour, and the cheap calls that pay for it are the enqueues that put the items into in in the first place.