The Queue ADT

Here is the queue ADT:

public interface Queue<T> {
  void enqueue(T item);
  void dequeue();
  T front();
  boolean isEmpty();
}

Like the stack, it is a small interface with only four methods. The enqueue method adds an item to the back of the queue. The dequeue method removes the item at the front. The front method returns the item at the front without removing it. The isEmpty method tells us whether the queue is empty.

The names enqueue and dequeue are the traditional ones: to enqueue is to join the queue, and to dequeue is to leave it. Notice again what is not here. There is no operation to get an item at an index, and no way to add or remove anywhere except the two ends.

You might also notice that dequeue does not return the removed item. That is the same design choice I made for the stack: looking and removing are separate operations.

It helps to picture the queue as a horizontal row of items, like people standing in line.

         ┌─────────────────┬─────┬─────────────────┐
front →  │ 1st item added  │ ... │ nth item added  │  ← back
         └─────────────────┴─────┴─────────────────┘
          leave from here                 join here

The queue has “first in, first out” (FIFO) behavior. The first item you enqueue is the first one you will dequeue. Compare that with the stack’s LIFO behavior. A stack adds and removes at the same end. A queue adds at one end and removes at the other.