Week 6: Two Stacks to Make a Queue

This week, we’ll implement a queue using two stacks (as implemented by singly linked lists). Here’s the interface we’d like:

public class LLQueue<E> {
    public LLQueue();
    public void enqueue(E elt);
    public E dequeue();
    public E peek();
    public boolean isEmpty();
}

Your queue will have two linked lists (use java.util.LinkedList), which we’ll use as stacks, calling add(0, ...) and remove(0) to manipulate only the first element of the list. Such an implementation is a nice way to get a queue without having to worry about circular lists, since stacks are so easy to implement using singly-linked lists. It’s also a good implementation for when you have many concurrent processing adding and removing elements at the same time.

Implementation strategy

To turn two stacks into a queue, we’ll use one stack to record inputs as they come in. We’ll use the other stack as the output stack. Whenever we need to output (peek or dequeue), we’ll try to pop something off the output stack. But if the output stack is empty, we’ll transfer the input stack to the output stack in reverse order, i.e., popping from the input and pushing onto the output until the input stack is exhausted.

Since peek and dequeue both need to move the input stack to the output stack, we recommend defining a private helper method to do so.

Your implementation for dequeue should be simple—you just need to put it onto the input list.

The implementation for isEmpty is also quite simple—the queue is empty when both the input and output stacks are empty.

Testing your code

Consider the following code:

  public static void main(String[] args) {
    LLQueue<String> q = new LLQueue<>();
    
    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("c");
    System.out.println(q.peek());
    q.enqueue("d");
    q.enqueue("e");
    q.enqueue("f");
    
    while (!q.isEmpty()) {
      System.out.println(q.dequeue());
    }
  }

If we run this, we should expect the output:

a
a
b
c
d
e
f

If we instrument our private helper method to announce its transfers, we get the output:

transferred 3 items
a
a
b
c
transferred 3 items
d
e
f

Note that the second transfer happens only after the three items transferred after the peek are exhausted.