Solution: Two Deques

Here is where we started. The items sit in a deque called items, and the four queue operations use one end of it for adding and the other end for removing.

public class MaxQueue {
  private Deque<Integer> items = new ArrayDeque<>();

  // All operations wrap the operations of `items` deque.
}

We add a second deque called candidates. It holds the candidate list from the previous section, oldest at the front, so its front is always the maximum.

private Deque<Integer> candidates = new ArrayDeque<>();

Two of the operations above have to change, and getMax has to be written.

enqueue adds the item to items. Then it removes from the back of candidates every candidate smaller than the item, and adds the item at the back.

public void enqueue(int item) {
  items.addLast(item);
  while (!candidates.isEmpty() && candidates.getLast() < item) {
    candidates.removeLast();
  }
  candidates.addLast(item);
}

dequeue removes the front of items. If that item equals the front of candidates, it removes the front of candidates too.

public void dequeue() {
  if (items.isEmpty()) {
    throw new NoSuchElementException();
  }
  int item = items.getFirst();
  items.removeFirst();
  if (item == candidates.getFirst()) {
    candidates.removeFirst();
  }
}

getMax reads the front of candidates. It checks whether items is empty, since the two deques are empty at the same time.

public int getMax() {
  if (items.isEmpty()) {
    throw new NoSuchElementException();
  }
  return candidates.getFirst();
}

Here is the class in full:

public class MaxQueue {
  private Deque<Integer> items = new ArrayDeque<>();
  private Deque<Integer> candidates = new ArrayDeque<>();

  public void enqueue(int item) {
    items.addLast(item);
    while (!candidates.isEmpty() && candidates.getLast() < item) {
      candidates.removeLast();
    }
    candidates.addLast(item);
  }

  public void dequeue() {
    if (items.isEmpty()) {
      throw new NoSuchElementException();
    }
    int item = items.getFirst();
    items.removeFirst();
    if (item == candidates.getFirst()) {
      candidates.removeFirst();
    }
  }

  public int front() {
    if (items.isEmpty()) {
      throw new NoSuchElementException();
    }
    return items.getFirst();
  }

  public int getMax() {
    if (items.isEmpty()) {
      throw new NoSuchElementException();
    }
    return candidates.getFirst();
  }

  public boolean isEmpty() {
    return items.isEmpty();
  }
}

Notice the strict comparison in enqueue:

candidates.getLast() < item

We remove smaller candidates, but not equal ones. The reason is in dequeue: we decide whether the item that leaves is the front candidate by comparing values. If the queue holds 5, 5 and we removed the older 5 from candidates when the newer one was enqueued, then dequeuing the first 5 would match the only 5 in candidates and remove it, even though another 5 remains in the queue. Keeping both 5s as candidates means each dequeue of a 5 removes one of them.