Implementing ArrayQueue

Here is the Queue interface:

public interface Queue<T> {
  void enqueue(T item);  // throws IllegalArgumentException if item is null
  void dequeue();        // throws NoSuchElementException if the queue is empty
  T front();             // throws NoSuchElementException if the queue is empty
  boolean isEmpty();
}

ArrayQueue<T> implements the Queue<T> interface with a backing array used as a circular array. There is no back field:

import java.util.NoSuchElementException;

public class ArrayQueue<T> implements Queue<T> {

  private T[] arr;    // the backing array, used as a circular array
  private int front;  // the index of the front item
  private int size;   // number of items in the queue

  @SuppressWarnings("unchecked")
  public ArrayQueue() {
    arr = (T[]) new Object[10];
    front = 0;
    size = 0;
  }

  // Doubles the capacity of arr.
  private void grow() { /* to implement */ }

  // enqueue, dequeue, front, and isEmpty go here
}

Solution

public boolean isEmpty() {
  return size == 0;
}

public T front() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return arr[front];
}

public void dequeue() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  arr[front] = null;
  front = (front + 1) % arr.length;
  size--;
}

Solution

public void enqueue(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (size == arr.length) {
    grow();
  }
  arr[(front + size) % arr.length] = item;
  size++;
}

Solution

Here is a queue state where a simple grow breaks the queue:

  0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ R │ S │ T │ P │ Q │
└───┴───┴───┴───┴───┘
              ↑
            front

A full, wrapped queue: capacity 5, front is 3, and the items in order are P, Q, R, S, T at indices 3, 4, 0, 1, 2. After a simple grow, we get this:

  0   1   2   3   4   5   6   7   8   9
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ R │ S │ T │ P │ Q │ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
              ↑
            front

If you were to enqueue a new item, it would be placed at index 8, since front is still 3 and size is 5, the next available index is (front + size) % arr.length = (3 + 5) % 10 = 8. The order is lost, and the queue is no longer correctly represented in the array.

If you were to dequeue from this queue, you would remove P and Q, but then the queue would appear empty even though R, S, and T are still in the array.

Solution

private void grow() {
  @SuppressWarnings("unchecked")
  T[] bigger = (T[]) new Object[arr.length * 2];
  for (int i = 0; i < size; i++) {
    bigger[i] = arr[(front + i) % arr.length];
  }
  arr = bigger;
  front = 0;
}

Solution

isEmpty, front, and dequeue are $O (1)$ : each reads or writes front, size, and at most one slot. enqueue is amortized $O (1)$ : it writes one slot, and the $O (n)$ grow runs only when the array is full, which doubling makes rare.

Solution

Both use $O (n)$ space. The array usually has more slots than items, and it keeps its largest capacity after the queue gets smaller. LinkedQueue allocates exactly one node per item, but each node also stores a next reference.