Solution: Scanning for the Maximum

Let’s start with the four operations we already know how to do. A deque used at one end for adding and the other end for removing is a queue. So we keep the items in a deque called items: enqueue is addLast, dequeue is removeFirst, front is getFirst, and isEmpty is the deque’s isEmpty.

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

  public void enqueue(int item) {
    items.addLast(item);
    size++;
  }

  public void dequeue() {
    if (items.isEmpty()) {
      throw new NoSuchElementException();
    }
    items.removeFirst();
    size--;
  }

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

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

Now getMax. The direct approach is to look at every item in the queue and keep the largest. But the Deque ADT gives us no way to look at the middle. We can only see the two ends. To see every item, we remove it from the front, look at it, and add it back at the back. After we do that once per item, every item has been looked at and the deque is back in its original order. The Deque ADT has no size operation either, which is why the class above counts the items itself in a size field, updated in enqueue and dequeue.

public int getMax() {
  if (items.isEmpty()) {
    throw new NoSuchElementException();
  }
  int max = items.getFirst();
  for (int i = 0; i < size; i++) {
    int item = items.getFirst();
    items.removeFirst();
    if (item > max) {
      max = item;
    }
    items.addLast(item);
  }
  return max;
}

This is correct. Let’s check it against the sequence from the problem statement. After enqueue(7), enqueue(2), enqueue(5), enqueue(1), and enqueue(4), the deque holds 7, 2, 5, 1, 4. The loop removes and re-adds each of the five items and finds 7. After the first dequeue(), the deque holds 2, 5, 1, 4, and the loop finds 5. After the next two, it holds 1, 4, and the loop finds 4. The empty case throws, and duplicates are no problem, since the loop compares values and does not care that two are equal.

What does this cost? enqueue, dequeue, front, and isEmpty are each one deque operation, so they are $O(1)$, with enqueue amortized because addLast may grow the backing array. But getMax moves every item twice, one removeFirst and one addLast, so it is $O(n)$ where $n$ is the number of items in the queue. The problem asks for amortized $O(1)$ on every operation, and this getMax costs $O(n)$ on every call.

Look at what the scan does on the sequence above. The first call finds 7 among five items. The second call, after one dequeue, scans four items to find 5. Nothing about those four items changed between the two calls. Only the 7 left. We are recomputing the answer from scratch, when we could have kept track of it as the items arrived and left.