Queue: with a circular array and with a linked list

A queue is the checkout line at a supermarket: you join at the back, the one in front leaves. The first to arrive is served first: FIFO (First In, First Out). Printer queues, an operating system’s job queue, packets in a network and matchmaking queues in games are all queues. The only difference from a stack is which end you remove from, but implementing it is more work: you have to track both ends. On the exam, the raw state of a circular array (what is in which cell, what front and rear are) is asked almost every year.

Golden rules:

1. Add at the back (enqueue), remove from the front (dequeue).
2. Don’t shift elements in the array. Advance the front and rear indices, and wrap around to the start with % when you reach the end.
3. front == rear can mean both empty and full. Keep a count to tell them apart.
4. In a linked queue, when the last element comes out, set tail to null too.

The queue ADT

Comparison with a stack: if 1, 2, 3 are inserted in order and then all are removed

stack: 3 2 1 | queue: 1 2 3

Why isn’t a simple array enough?

The first idea: always keep the front at index 0, and on removal shift everyone one step left. It works correctly, but every dequeue does n − 1 moves. The total cost of removing n elements one by one:

n=1000 shifts=499500
n=2000 shifts=1999000
n=4000 shifts=7998000

When n doubles the cost quadruples: O(n²) in total, O(n) per operation. If you advance the front index instead of shifting, this time the start of the array is wasted, and when rear reaches the end it looks as though there is no room left. The solution: think of the array as a ring.

The circular array (circular buffer)

When an index reaches the end it wraps to 0: i = (i + 1) % capacity. For capacity 4 the index order is 0, 1, 2, 3, 0, 1, …

class ArrayQueue {
    private int[] data;
    private int front = 0;   // index of the first element
    private int rear = 0;    // the next free slot
    private int count = 0;

    ArrayQueue(int capacity) { data = new int[capacity]; }

    boolean isEmpty() { return count == 0; }
    boolean isFull()  { return count == data.length; }

    void enqueue(int x) {
        if (isFull()) throw new RuntimeException("Queue overflow");
        data[rear] = x;
        rear = (rear + 1) % data.length;
        count++;
    }

    int dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue underflow");
        int x = data[front];
        front = (front + 1) % data.length;
        count--;
        return x;
    }

    int peek() {
        if (isEmpty()) throw new RuntimeException("Queue underflow");
        return data[front];
    }
}

PITFALL · the meaning of rear. In some books rear is the index of the last element, in others the next free slot. On this page it is the next free slot. On the exam, read the definition in the question; the formulas shift by one accordingly.

Worked trace (capacity 4)

ArrayQueue q = new ArrayQueue(4);
q.enqueue(10); q.enqueue(20); q.enqueue(30);
System.out.println(q.dequeue());
System.out.println(q.raw());
q.enqueue(40); q.enqueue(50);
System.out.println(q.raw());
System.out.println(q.dequeue() + " " + q.dequeue());
System.out.println(q.raw());

10
[10, 20, 30, 0] front=1 rear=3 count=2
[50, 20, 30, 40] front=1 rear=1 count=4
20 30
[50, 20, 30, 40] front=3 rear=1 count=2

enqueue 10,20,30   [10,20,30, _]  front=0 rear=3 count=3
dequeue → 10       [10,20,30, _]  front=1 rear=3 count=2   (10 stayed in the array)
enqueue 40         [10,20,30,40]  front=1 rear=0 count=3   (rear 3 → (3+1)%4 = 0)
enqueue 50         [50,20,30,40]  front=1 rear=1 count=4   (written over the 10, full)
dequeue → 20       front=2
dequeue → 30       front=3, count=2; the queue logically: 40, 50

In the final state the queue consists of 40 and 50. To read from the front, start at front and advance count times with (i + 1) % cap: index 3 (40), index 0 (50).

TIP · Raw array questions. When the exam asks “what are the contents of the array?”, the removed elements are still written in the array. Only a new enqueue overwrites them. At each step write four things: array, front, rear, count.

Queue with a linked list (linked queue)

In a singly linked list, insertion at the head and deletion at the head are O(1), insertion at the end is O(1) if there is a tail, and deletion from the end is O(n). Therefore: insert at the tail, remove at the head.

class LinkedQueue {
    private static class Node { int data; Node next; Node(int d) { data = d; } }
    private Node head, tail;   // head = front, tail = back

    boolean isEmpty() { return head == null; }

    void enqueue(int x) {
        Node n = new Node(x);
        if (tail == null) head = tail = n;   // empty queue
        else { tail.next = n; tail = n; }
    }

    int dequeue() {
        if (head == null) throw new RuntimeException("Queue underflow");
        int x = head.data;
        head = head.next;
        if (head == null) tail = null;       // the queue became empty
        return x;
    }
}

If the line if (head == null) tail = null; is forgotten: after the queue empties, tail keeps pointing to the old node, the next enqueue is linked behind that dead node, and head stays null. The queue looks empty forever.

Queue patterns

Rotating. q.enqueue(q.dequeue()) moves the front element to the back. If you do it k times the queue rotates k steps: 10 20 30 40 50 twice → 30 40 50 10 20.

Reversing. Empty the queue into a stack, then fill it back from the stack into the queue: 1 2 3 4 → 4 3 2 1.

Processing in turn. Taking the front two elements and adding the result to the back sets up a “tournament” or merge operation. The number of elements decreases by one each round; stop when one element remains.

Common mistakes

q.enqueue(5); q.enqueue(3);
System.out.print(q.dequeue() + " ");
q.enqueue(8); q.enqueue(1);
System.out.print(q.dequeue() + " ");
System.out.print(q.dequeue() + " ");
q.enqueue(6);
System.out.println(q.peek());

enqueue(1); enqueue(2); enqueue(3); enqueue(4);
dequeue(); dequeue(); dequeue();
enqueue(5); enqueue(6); enqueue(7);

for (int i = 1; i <= 4; i++) enqueue(i);
dequeue(); dequeue();
enqueue(5); enqueue(6);

void enqueue(int x) {
    if (count == data.length)
        throw new RuntimeException("Queue overflow");
    data[rear] = x;
    rear = (rear + 1) % data.length;   // jump to 0 at the end
    count++;
}

int dequeue() {
    if (count == 0)
        throw new RuntimeException("Queue underflow");
    int x = data[front];
    front = (front + 1) % data.length;
    count--;
    return x;
}

int dequeue() {
    if (head == null)
        throw new RuntimeException("Queue underflow");
    int x = head.data;
    head = head.next;
    if (head == null)   // the last element came out
        tail = null;
    return x;
}

void enqueue(int x) {
    Node n = new Node(x);
    if (tail == null) head = tail = n;
    else { tail.next = n; tail = n; }
}
int dequeue() { int x = head.data; head = head.next; return x; }

enqueue(1); dequeue(); enqueue(2); enqueue(3);

for (int k = 0; k < 2; k++)
    q.enqueue(q.dequeue());

Deque<Integer> st = new ArrayDeque<>();
while (!q.isEmpty()) st.push(q.dequeue());
while (!st.isEmpty()) q.enqueue(st.pop());

try {
    for (int i = 1; i <= 4; i++) {
        q.enqueue(i * 10);
        System.out.print(i * 10 + " ");
    }
} catch (RuntimeException e) {
    System.out.println("-> " + e.getMessage());
}

int total = 0;
while (q.size() > 1) {
    int x = q.dequeue();
    int y = q.dequeue();
    q.enqueue(x + y);
    total += x + y;
}
System.out.println(q.peek() + " " + total);