Queues

The Basics

A queue is a FIFO sequence. Addition takes place only at the tail, and removal takes place only at the head.

The basic operations are:

• enqueue(x): add an item at the tail
• dequeue: remove the item at the head
• peek: return the item at the head (without removing it)
• size: return the number of items in the queue
• isEmpty: return whether the queue has no items

Queues are seen often in computer science. A tiny fraction of their known uses:

• Line of cars at a light
• Line of people at a deli or at Fry's
• Printer buffer
• Packets waiting at a router
• Simulation
• Many more examples

An Interface

Yes, it’s true: there's already a Queue interface in the Java Core API and a whole bunch of implementing subclasses (AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, PriorityBlockingQueue, PriorityQueue, SynchronousQueue), but we're going to write some queues from scratch because:

• This is the best way for you to really learn how queues work behind the scenes
• You need coding practice, especially with linked structures
• Job interviews sometimes involve implementing queues on a whiteboard
• You need to know how to code things up when you find yourself in a very restrictive environment that doesn't have a collections library.

Here is a Java Interface:

/**
 * A small queue interface. You can query the size of the queue and ask whether
 * it is empty, add and remove items, and peek at the front item.
 */
public interface Queue {

    /**
     * Adds the given item to the rear of the queue.
     */
    void enqueue(Object item);

    /**
     * Removes the front item from the queue and returns it.
     * 
     * @exception java.util.NoSuchElementException if the queue is empty.
     */
    Object dequeue();

    /**
     * Returns the front item from the queue without popping it.
     * 
     * @exception java.util.NoSuchElementException if the queue is empty.
     */
    Object peek();

    /**
     * Returns the number of items currently in the queue.
     */
    int size();

    /**
     * Returns whether the queue is empty or not.
     */
    default boolean isEmpty() {
        return size() == 0;
    }
}

Representations

As usual, we have many choices.

Linked Queues

Let’s start with a linked representation. Since we are adding at the tail and removing from the head, we need direct access to both ends. Now we could store direct head and tail links in the object:

You are encouraged to implement the interface with a structure like this, and it is certainly doable, but there are a lot of special cases. When you are learning to program with linked structures, it’s a great exercise. In practice, however, we get a slightly simpler implementation if we store only a link to the tail node and link the tail to the head, like so:

Here is an implementation using the circular queue:

import java.util.NoSuchElementException;

/**
 * An implementation of a queue using a ring of singly linked nodes. The queue
 * object contains only a single link to its tail node (null for the empty queue
 * of course). The tail node's successor is the head of the queue, ensuring O(1)
 * time for both enqueue and dequeue.
 */
public class CircularLinkedQueue implements Queue {

    // We cannot use a record because we have to mutate these nodes
    private static class Node {
        Object data;
        Node next;

        Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node tail = null;
    private int size = 0;

    public void enqueue(Object item) {
        if (isEmpty()) {
            tail = new Node(item, null);
            tail.next = tail;
        } else {
            tail = tail.next = new Node(item, tail.next);
        }
        size++;
    }

    public Object dequeue() {
        var item = peek();
        if (tail.next == tail) {
            // Last node deleted
            tail = null;
        } else {
            // Just "point around" the old head you are deleting
            tail.next = tail.next.next;
        }
        size--;
        return item;
    }

    public Object peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return tail.next.data;
    }

    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return tail == null;
    }
}

A Bounded Array Queue

Now this is going to get really interesting!

We’re going to get a feel for how this works in pictures.

Here’s the code:

import java.util.NoSuchElementException;

/**
 * An implementation of a queue using a fixed, non-expandable array whose
 * capacity is set in its constructor.
 */
public class BoundedQueue implements Queue {
    private Object[] elements;
    private int size = 0;
    private int head = 0; // index of the current front item, if one exists
    private int tail = 0; // index of next item to be added

    public BoundedQueue(int capacity) {
        elements = new Object[capacity];
    }

    public void enqueue(Object item) {
        if (isFull()) {
            throw new IllegalStateException("Cannot add to full queue");
        }
        elements[tail] = item;
        tail = (tail + 1) % elements.length;
        size++;
    }

    public Object dequeue() {
        var item = peek();
        elements[head] = null;
        head = (head + 1) % elements.length;
        size--;
        return item;
    }

    public Object peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return elements[head];
    }

    public int size() {
        return size;
    }

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

    // This is a bonus method that is not part of the interface
    public boolean isFull() {
        return size == elements.length;
    }
}

Things to note here:

• The capacity is set at creation time
• Adds have a precondition that the queue isn't already full
• Adding to a full queue is a state exception, not an argument exception
• The array itself is effectively circular
• When removing, we take care to nullify the newly unused slot in the array to prevent a possible memory leak

An Expandable Array Queue

You can do a little “mixing” of the array and linked approaches. Start with an array of reasonable size, then, when it fills up, reallocate a new array (of twice the size), copy the contents over, and add the new element. If the array ever gets too small, allocate a smaller array for the queue and copy into it.

Unit Testing

Here are some things we need to test:

• A queue is empty on construction
• A queue has size 0 on construction
• After n > 0 enqueues to an empty queue, the queue is non empty and its size is n
• If one enqueues x then dequeues, the value dequeued is x.
• If one enqueues x then peeks, the value returned is x, but the size stays the same
• If the size is n, then after n dequeues, the stack is empty and has a size 0
• If one enqueues the values 1 through 50, in order, into an empty queue, then if 50 dequeues are done the values dequeues are 1 through 50.
• Dequeueing from an empty queue throws a NoSuchElementException
• Peeking into an empty queue throws a NoSuchElementException
• For bounded queues only, pushing onto a full stack throws an IllegalStateException

We have multiple implementations to test, so it makes sense to factor out all the common tests into a base test class:

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;

import java.util.NoSuchElementException;

/**
 * Base test for any class that implements the Queue interface.
 */
public abstract class QueueTest {

    /**
     * The queue to use in all the tests: set this in subclasses.
     */
    protected Queue q;

    @Test
    public void testNewQueueIsEmpty() {
        assertTrue(q.isEmpty());
        assertEquals(q.size(), 0);
    }

    @Test
    public void testInsertsToEmptyQueue() {
        int numberOfInserts = 8;
        for (var i = 0; i < numberOfInserts; i++) {
            q.enqueue("zzz");
        }
        assertTrue(!q.isEmpty());
        assertEquals(q.size(), numberOfInserts);
    }

    @Test
    public void testEnqueueThenDequeue() {
        var message = "hello";
        q.enqueue(message);
        assertEquals(q.dequeue(), message);
    }

    @Test
    public void testEnqueueThenPeek() {
        var message = "hello";
        q.enqueue(message);
        var size = q.size();
        assertEquals(q.peek(), message);
        assertEquals(q.size(), size);
    }

    @Test
    public void testFiftyInThenFiftyOut() {
        for (int i = 0; i < 50; i++) {
            q.enqueue(i);
        }
        for (int i = 0; i < 50; i++) {
            assertEquals(((Integer) q.dequeue()).intValue(), i);
        }
    }

    @Test
    public void testRemovingDownToEmpty() {
        int numberOfRemoves = (int) (Math.random() * 20 + 1);
        for (int i = 0; i < numberOfRemoves; i++) {
            q.enqueue("zzz");
        }
        for (int i = 0; i < numberOfRemoves; i++) {
            q.dequeue();
        }
        assertTrue(q.isEmpty());
        assertEquals(q.size(), 0);
    }

    @Test
    public void testRemoveFromEmptyQueueThrows() {
        assertTrue(q.isEmpty());
        assertThrows(NoSuchElementException.class, () -> q.dequeue());
    }

    @Test
    public void testPeekIntoEmptyQueueThrows() {
        assertTrue(q.isEmpty());
        assertThrows(NoSuchElementException.class, () -> q.peek());
    }

}

The concrete test classes instantiate the specific kind of queue. The linked tester needs nothing other than the creation of the test queue:

import org.junit.jupiter.api.BeforeEach;

public class LinkedQueueTest extends QueueTest {

    @BeforeEach
    public void makeLinkedQueue() {
        q = new LinkedQueue();
    }
}

For the bounded queue, we need to test that insertion into a full queue is an error:

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.BeforeEach;
import static org.junit.jupiter.api.Assertions.assertThrows;

public class BoundedQueueTest extends QueueTest {
    private static int CAPACITY = 60;

    @BeforeEach
    public void makeBoundedQueue() {
        q = new BoundedQueue(CAPACITY);
    }

    @Test
    public void testEnqueueToFullQueue() {
        for (int i = 0; i < CAPACITY; i++) {
            q.enqueue("abc");
        }
        assertThrows(IllegalStateException.class, () -> q.enqueue("abc"));
    }
}

An Application of Queues

TODO

Summary