Chapter 8: Queues and Deques

8.1The queue ADT

A data structure can be described at two levels: what it does (its operations, what each changes and returns) and how (how the data sits in memory and what steps each operation takes). A description at the first level is an abstract data type (ADT). This section treats the queue at that level, apart from any implementation.

8.1.1What is a queue?

Think of a supermarket checkout. Newcomers join at the back, the cashier serves the person at the front, and everyone behind moves up; nobody cuts in or jumps ahead. Ticket windows, bank tellers, and toll booths follow the same rule: first come, first served.

A queue imitates this. Its items form a line whose ends have separate jobs: new items join at the rear, and removal happens at the front. The item that leaves is always the one that has waited longest.

A stack inserts and removes at the same end, so the last item in is the first out (LIFO); a queue uses opposite ends, so the first in is the first out. Push 1, 2, 3 into each and remove three times: the stack returns 3, 2, 1, the queue 1, 2, 3. A queue exists to hold work in order of arrival and hand it back in that order.

Each end of a queue is used in one direction only. The queue is a linear structure: every item but the first has one predecessor, every item but the last one successor, and nothing branches.

8.1.2The basic operations

A queue has two basic operations, whose names are used throughout the course:

• Insertion (enqueue) adds an item at the rear — joining the line.
• Removal (dequeue) removes and returns the front item, the first one in.

In a good implementation both run in O(1) time, however many items the queue holds. That requires reaching both ends directly, without searching, and the whole design of the array and linked versions serves this goal.

Items in the middle cannot be reached. This restriction is deliberate: client code cannot break the order or let an item skip ahead, and the implementation only has to make two ends fast.

8.1.3Operations and interface of the queue ADT

A few helper operations complete the queue ADT (Table 8.1).

Only enqueue and dequeue change the queue; the rest just report. first() differs from dequeue() as top() differs from pop() on a stack: both return the front item, but first() leaves it in place, which is what you want when you must look before deciding whether to remove.

isFull() makes sense only for a fixed capacity. A linked queue, or one that grows when full, is never "full" while memory lasts.

In Java an ADT is naturally written as an interface, which gives method signatures without bodies. Here is a shortened form of the queue interface from the textbook by Goodrich, Tamassia, and Goldwasser:

public interface Queue<E> {
    int size();
    boolean isEmpty();
    void enqueue(E e);
    E first();    // null if empty
    E dequeue();  // null if empty
}

E is a type parameter fixed when the queue is created: Queue<Integer> holds integers, Queue<String> strings. Classes and interfaces with type parameters are generic. The interface omits rear(), which basic use doesn't need, and deliberately omits isFull() so that it also covers unbounded queues.

The comments record a contract: on an empty queue, first() and dequeue() return null. Removing from an empty queue is underflow; adding to a full fixed-capacity queue is overflow. How to report these errors is a design choice. Goodrich's interface returns null, other implementations throw; in these notes the circular queue and the linked queue throw and the deque returns null. The caller feels the difference: an unchecked null lets the error travel silently, while an exception stops the program at once.

8.1.4Queue operations step by step

Apply enqueue(20), enqueue(10), enqueue(15), and three dequeue() calls to an empty queue whose end references are named front and rear.

Two edge cases matter. The first insertion into an empty queue must update both references, since that item is both front and rear; removing the last item must reset rear to null along with front. Most queue bugs come from these two cases.

A tip for exercises: after each operation, write the contents on one line from front to rear with the returned value beside them. Writing always in one direction keeps you from removing at the wrong end.

8.1.5Queues in Java: java.util.Queue

Java provides the java.util.Queue<E> interface, in which each operation comes in two forms: one throws an exception on failure, the other returns a special value (Table 8.2).

On an empty queue, remove() and element() throw NoSuchElementException, while poll() and peek() return null. When a bounded queue is full, add(e) throws IllegalStateException and offer(e) returns false; on unbounded queues, such as the two classes below, offer always returns true.

An interface has no objects of its own; two common classes implement it:

• ArrayDeque uses a circular array and is usually the fastest; it is a growable version of the circular queue in these notes.
• LinkedList uses a linked list; it also supports list operations but creates a node object per item.

The code below runs the basic operations on an ArrayDeque. Declaring the variable as Queue<Integer> limits the code to queue operations and makes the implementing class easy to swap.

Queue<Integer> q = new ArrayDeque<>();
q.offer(20);
q.offer(10);
q.offer(15);        // [20, 10, 15]
q.peek();           // 20, not removed
q.poll();           // 20 → [10, 15]
q.poll();           // 10 → [15]
q.size();           // 1
q.poll();           // 15 → []
q.poll();           // null (empty)

peek() returns 20 without changing the queue, so the next poll() returns 20 again. The last poll(), on an empty queue, returns null; remove() there would have thrown NoSuchElementException.

Our own classes use the ADT names enqueue/dequeue; the Java library does the same work with offer/poll/peek. The names differ, the behavior does not.

8.1.6Where queues are used

A queue fits wherever work should be done in arrival order. Four common cases:

• Operating system schedulers. Ready processes wait in a ready queue and get the CPU in turn. Round-robin scheduling, the simplest form of this idea, is covered in Section 8.5.1.
• Print queues. A printer prints the documents sent to it in order of arrival; later ones wait.
• Buffers. Keyboard input, network packets, and video streams wait in a buffer, which evens out the speed difference between producer and consumer: data piles up while the producer is ahead and drains while the consumer catches up.
• Breadth-first search (BFS). Nodes discovered in a graph or tree are queued, so nearby nodes are visited before distant ones and the traversal goes level by level. Binary number generation in Section 8.5.4 is a small instance.

What these cases share is fairness and preserved order. A printer must print the first document first; packets handled out of order make a video show scrambled frames; a scheduler must not starve a process. A queue guarantees all this by structure: once an item is in, its turn comes as soon as the items ahead of it have left.

8.2Array-based queues

The obvious way to implement a queue is with an array, whose cells are reached by index in O(1); the queue only has to track its two ends. We try the simplest idea first, see why it wastes space, and fix it with a circular queue.

8.2.1The array representation

The items live in an array, and two indices mark the ends:

• front: the index of the first item, which the next removal takes.
• rear: the index of the last item, the most recently added.

To insert, increment rear and write to data[rear]; to remove, take data[front] and increment front. Items never move, so both operations are O(1). The method is simple and fast, but the capacity is fixed.

Figure 8.4 already shows the weak spot. Removals push the front rightward, and the slots freed behind it are never used again. rear creeps toward the end of the array according to the number of insertions so far, not the number of items held.

8.2.2The trouble with a simple array queue

Take a simple array queue of capacity N = 6 with front = 0 and rear = −1 (nothing added yet; the first insertion raises rear to 0 and writes at index 0). We insert 10, 20, 30, 40, remove three times, then try to insert 50, 60, 70.

Four insertions raise rear to 3. Three removals return 10, 20, 30 and move front to 3, so front and rear both point at 40, the only item left. Inserting 50 and 60 brings rear to 5, the last index (N − 1). For enqueue(70), rear + 1 = 6 = N: there is no room at the end, and the queue reports "full."

Yet it holds only 40, 50, and 60, while indices 0–2 sit empty: half the array is wasted because freed slots cannot be reused. Worse, even if each insertion were followed at once by a removal, rear would hit the end after six insertions. A simple array queue's lifetime is bounded by its total insertions, not by its contents.

There are two ways out.

Solution 1: shifting. After each removal, shift the remaining items one slot left. The front then stays at data[0] and needs no index; size counts the items:

public int dequeue() {              // simple array queue with shifting
    if (size == 0)
        throw new IllegalStateException("empty");
    int result = data[0];           // the front is always data[0]
    for (int i = 1; i < size; i++)
        data[i - 1] = data[i];      // everyone moves one slot left
    size--;
    return result;
}

With n items, a removal makes n − 1 assignments and costs O(n); emptying a queue of 1,000 items takes 999 + 998 + … + 1 + 0 = 499,500. The waste is gone, and so is the speed.

Solution 2: a circular array. Indices wrap from the end of the array to the start. Nothing is shifted, freed slots are reused, and every operation stays O(1). This is the circular queue.

8.2.3The circular queue

In a simple array queue the end of the array is a wall. A circular queue removes it: after the last slot comes the first, so the two ends join logically into a ring. In memory the array is still a flat row; the ring exists only in how indices are computed.

A circular queue is still FIFO; only its "next index" changes, from i + 1 to (i + 1) % N. The two agree while i < N − 1; at i = N − 1, (N − 1 + 1) % N = N % N = 0, and the index wraps. Freed slots are reused and nothing is shifted.

Our circular queue keeps two fields: front, the index of the first item, and size, the item count. The rear is not stored; the free slot for the next item is (front + size) % N.

The ring has no "end": slot 7 neighbors both 6 and 0. Insertion advances the rear clockwise and removal moves the front clockwise, so the queue can start and end anywhere on the ring.

8.2.4Computing indices with mod

Every index is computed from front, size, and N. For non-negative a, the remainder a % N lies between 0 and N − 1, always a valid index. Table 8.5 evaluates the four basic formulas for N = 8, front = 6, size = 4.

All the formulas rest on one idea: item k lies k steps past the front. In a plain array that is front + k; in a circular one the sum may run past the end, and % N wraps it around. C is item 2: 6 + 2 = 8 is outside the array, but 8 % 8 = 0 is C's real place.

The next free slot is simply the case k = size: positions 0 to size − 1 are occupied, so the last item is at size − 1. Mod handles the jump from end to start in one expression, with no if asking whether we have reached the end.

Since front < N and size ≤ N, these sums stay below 2N, so % wraps at most once. Stepping backward needs care: in Java the result of % takes the sign of the dividend, so for front = 0, (front − 1) % N gives −1 % N = −1. The correct expression is (front − 1 + N) % N, which is exactly what inserting at the front of an array-based deque uses.

8.2.5Full or empty?

Two indices look sufficient at first: front for the first item and rear for the next write position. But then empty and full look alike. In an empty queue both point to the same slot; after N insertions rear has circled the ring back to front. Either way, front == rear.

Two common remedies exist.

1. Keep a counter. A size field makes the tests size == 0 (empty) and size == N (full), and all N slots are used. These notes and the slides use this method; with the counter, the rear index need not be stored, since it is (front + size) % N.

2. Leave one slot empty. The queue holds at most N − 1 items. It is empty when front == rear and full when (rear + 1) % N == front, with rear just behind front and one empty slot between. No counter is needed, but a slot is always wasted.

The methods differ little. The counter costs one integer field but uses every slot, and size == 0 and size == N say plainly what is tested. Leaving a slot empty pays off where a shared counter is costly or risky: when a producer and a consumer use one buffer concurrently, the producer changes only rear and the consumer only front, so neither must update a common field.

8.2.6A circular queue step by step

Here is a counter-based circular queue with N = 5, starting at front = 0, size = 0. enqueue writes to slot (front + size) % 5 and increments size; dequeue returns data[front], clears the slot, sets front to (front + 1) % 5, and decrements size.

The first five rows match the simple array queue: three insertions fill slots 0–2, and two removals return 10 and 20 and move front to 2. Only front moves.

The difference appears at enqueue(60): the insertion point (2 + 3) % 5 = 0 has wrapped. Where the simple array queue would say "full," the circular queue reuses slot 0. enqueue(70) goes to slot 1 and size reaches 5; now the queue is truly full, with no slot wasted.

The next write position of the full queue, (2 + 5) % 5 = 2, is front itself; judged by indices alone the queue might look empty, but size == 5 settles it.

Five removals then return 30, 40, 50, 60, 70. On the third, front becomes (4 + 1) % 5 = 0, so the front wraps too. After the last, size = 0. The output order equals the input order: the circular layout keeps FIFO intact.

8.2.7Code: the CircularQueue class

The class below holds the fields, constructor, and status queries of a counter-based circular queue; insertion and removal follow in Section 8.2.8.

public class CircularQueue<E> {
    private E[] data;        // stores the items
    private int front = 0;  // index of the first item
    private int size = 0;   // number of items

    @SuppressWarnings("unchecked")
    public CircularQueue(int capacity) {
        data = (E[]) new Object[capacity];
    }
    public int size()        { return size; }
    public boolean isEmpty() { return size == 0; }
    public boolean isFull()  { return size == data.length; }
    public E first()         { return isEmpty() ? null : data[front]; }
    // enqueue(), dequeue()
}

Line by line:

• data holds the items, front is the index of the first, and size is the count; both start at 0 because a new queue is empty.
• The constructor allocates the array. Java forbids new E[capacity], because E is unknown at run time, so we create an Object array and cast it with (E[]). @SuppressWarnings("unchecked") silences the compiler's unchecked-cast warning for the constructor only; the cast is safe as long as the array never leaves the class.
• size() returns the count; isEmpty() tests size == 0, and isFull() tests size == data.length, the capacity.
• first() returns null for an empty queue and data[front] otherwise, changing nothing. ? : is the conditional operator: the first value if the condition holds, the second if not.

The rear index is computed, (front + size) % data.length, rather than stored. Storing both rear and size would oblige every method to update both correctly, and a method that forgot one would leave them contradicting each other. Keeping each fact in one place removes that risk.

No method loops, so each is O(1). The array has as many slots as the capacity, so space is O(N) however many items are stored.

8.2.8Code: enqueue() and dequeue()

Here are the class's two basic methods:

public void enqueue(E item) {      // add at the rear
    if (isFull())
        throw new IllegalStateException("full");
    int avail = (front + size) % data.length;
    data[avail] = item;
    size++;
}

public E dequeue() {                // remove from the front
    if (isEmpty())
        throw new IllegalStateException("empty");
    E item = data[front];
    data[front] = null;             // drop the reference
    front = (front + 1) % data.length;
    size--;
    return item;
}

enqueue first checks for a full queue and throws IllegalStateException("full"), the code's way of reporting overflow. Otherwise it computes the insertion point into avail, writes the item, and increments size. front is untouched: adding at the rear does not affect the front.

dequeue throws IllegalStateException("empty") on underflow. Otherwise it saves the front item in item, writes null into the slot, advances front, decrements size, and returns the saved item.

data[front] = null; is not needed for correctness: dequeue returns the right item without it, and the slot is overwritten on the next lap anyway. It is about memory. The garbage collector frees only objects no reference points to, so an object that has left the queue but still sits in the array stays alive. With large items (images, file buffers) this becomes a real memory leak.

Line order matters too. item = data[front] must come before the null assignment, or the return value is lost, and front must advance after it, or the wrong slot is cleared.

8.2.9Code trace: enqueue()

We trace enqueue through a wrap. Initially data.length = 5, front = 2, size = 2, with 30 in slot 2 and 40 in slot 3; we add 50, 60, 70, and 80 using this method:

public void enqueue(E item) {
  if (isFull())
    throw new IllegalStateException("full");
  int avail = (front + size) % data.length;
  data[avail] = item;
  size++;
}

For enqueue(50), size (2) is below the capacity (5). The insertion point is (2 + 2) % 5 = 4 — here mod changes nothing — so data[4] = 50 and size becomes 3. front stays at 2.

For enqueue(60) the point is (2 + 3) % 5 = 5 % 5 = 0: the index wraps, and 60, logically last in the queue, sits physically first in the array. enqueue(70) writes to (2 + 4) % 5 = 1 and raises size to 5.

For enqueue(80) the check gives 5 == 5: IllegalStateException("full") is thrown and nothing changes. The capacity ran out at exactly 5 items, none wasted.

8.2.10Code trace: dequeue()

Starting from the full queue left by the previous trace (front = 2; 30, 40, 50, 60, 70 from front to rear), we call dequeue() three times.

public E dequeue() {
  if (isEmpty())
    throw new IllegalStateException("empty");
  E item = data[front];
  data[front] = null;         // drop the reference
  front = (front + 1) % data.length;
  size--;
  return item;
}

Each call takes the same five steps. isEmpty() is false, so item = data[front] takes the oldest item (data[2] = 30 on the first call); data[2] = null clears the slot; front advances to (2 + 1) % 5 = 3; size drops to 4; and 30 is returned.

On the third call the front item is in the last slot, data[4] = 50, and front wraps: (4 + 1) % 5 = 5 % 5 = 0. Left are 60 (slot 0) and 70 (slot 1), now at the front of the queue both physically and logically.

No item moves and no loop runs: each call is O(1).

8.2.11Growing a full circular queue

A fixed-capacity queue fails when full. If the capacity is unknown in advance, an insertion into a full queue can instead allocate an array twice as large and move the items over:

private void resize(int newCap) {
  E[] temp = (E[]) new Object[newCap];
  for (int k = 0; k < size; k++)
    temp[k] = data[(front + k) % data.length];
  data = temp;
  front = 0;
}
public void enqueue(E item) {
  if (size == data.length) resize(2 * data.length);
  data[(front + size) % data.length] = item;
  size++;
}

resize copies the items to the start of the new array in logical order: item k, at old slot (front + k) % data.length, goes to new slot k. Then the old array is dropped and front becomes 0, since the front is now at the start. On a full queue, enqueue doubles the capacity first and then writes as usual.

Take a full queue of capacity 4 with front = 2: logically A, B, C, D, but physically C, D, A, B, since it has wrapped. Now enqueue(E) is called.

At k = 2 the mod kicks in, (2 + 2) % 4 = 0: the copy wraps around the old array and places C and D right behind A and B. The queue now lies in order from slot 0 with front = 0, and E goes to slot (0 + 4) % 8 = 4.

A resize copies every item and so costs O(n), but doubling makes resizes rare, so it is more telling to look at the total cost of a long sequence of operations. This is amortized analysis.

For example, add 17 items to an empty queue of capacity 4 with no removals. Resizes at the 5th, 9th, and 17th insertions copy 4 + 8 + 16 = 28 items; with 17 writes the total is 45, below 3 · 17 = 51. The theorem does not promise that every insertion is cheap: the 17th alone made 16 copies, and a single insertion can take O(n). Real-time systems, where every operation must be quick, need a worst-case bound, not an amortized one.

8.3Linked queues

An array-based queue has a preset capacity and can grow only by copying. A linked list creates a node per arriving item and never copies. This section builds a queue on a singly linked list and compares the two implementations.

8.3.1The linked representation

Each item is a node holding the item's value (data) and a reference to the next node (next). The queue keeps front (first node), rear (last node), and the count size.

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
    }
}
// fields:
Node front, rear;
int size;

Insertion happens at the end of the list and removal at its head. Each insertion allocates a node and each removal releases one, so there is no capacity limit and no "full queue" while memory lasts. The price is an extra reference per node and a new object per insertion.

Why not the other way round? In a singly linked list, deleting the head is a single O(1) assignment, front = front.next, and adding at the end is easy thanks to rear: link the new node to rear.next and move rear to it. Deleting the last node, however, means finding the node before it, the new last node, and with no backward links that takes a walk from the head, O(n). With the ends swapped, dequeue would be O(n).

8.3.2The enqueue and dequeue algorithms

In any implementation the two operations follow the same steps:

enqueue(x)

1. Is the queue full? (Asked only for a fixed-capacity array.)
2. If so, report overflow and stop.
3. Otherwise, write x at the rear position.
4. Advance the rear to the next position.
5. Increment the item count and return successfully.

dequeue()

1. Is the queue empty?
2. If so, report underflow and stop.
3. Otherwise, take the front item.
4. Advance the front to the next item.
5. Decrement the item count and return the item taken.

Table 8.10 shows the corresponding code in the two implementations.

In the circular array, advancing the rear is not a separate step: incrementing size moves the next write position. In the linked list, writing and advancing are two assignments: link the old last node to the new one, then move rear.

8.3.3Code trace: enqueue

The linked queue's enqueue:

public void enqueue(int data) {
    Node temp = new Node(data);
    if (isEmpty()) {
        front = temp;
    } else {
        rear.next = temp;
    }
    rear = temp;
    size++;
}

new Node(data) returns an unlinked node holding the value, with next equal to null. If the queue is empty, the new node is also the first, so front points to it; otherwise the old last node's next is set to it. Either way it is now the last node, which is why rear = temp stands outside the if/else. Finally size grows by one.

Apply enqueue(10), enqueue(15), and enqueue(20) to an empty queue:

On the first call the queue is empty: front = temp and rear = temp make node 10 both front and rear.

On the second call the else branch links the old last node (10) to the new one (15) with rear.next = temp. This must happen before rear changes, since rear is the only way to reach the old last node. Then rear = temp moves the rear to 15; front stays. The third call repeats this for 20.

No call walks the list: each creates one node, assigns at most two references, and increments a counter, O(1).

8.3.4Code trace: dequeue

The linked queue's dequeue:

public int dequeue() {
    if (isEmpty())
        throw new NoSuchElementException();
    int result = front.data;
    front = front.next;
    if (front == null)
        rear = null;
    size--;
    return result;
}

An empty queue throws NoSuchElementException. Otherwise the front value goes into result and front moves to the next node; the old first node is now unreferenced and the garbage collector reclaims it. if (front == null) rear = null; handles the edge case: if the removed node was the only one, the queue is now empty and rear must be cleared too. Finally size drops and result is returned.

Call dequeue() three times on the queue 10 → 15 → 20 from the previous trace:

The first two calls take the front value and move front one node on; since front is not null, rear is untouched. Afterward both point to node 20.

The third call is the edge case. result = 20, and front = front.next makes front null while rear still points to the deleted node 20. front == null holds, so rear = null runs. Without it, an empty queue would keep rear on a deleted node: rear() would return a value not in the queue, and the node could not be freed.

The calls return 10, 15, 20, the insertion order, each in O(1).

8.3.5Circular array or linked list?

Both implementations have O(1) basic operations; memory use and practical speed decide between them.

A circular array stores items contiguously. The processor reads memory in blocks, so contiguous data is faster to access than scattered nodes; it is cache-friendly, and it needs no per-item reference. But the capacity is fixed: when it runs out, the queue reports overflow or copies into a bigger array, a copy that is O(n) alone and O(1) amortized. The array also occupies its full capacity even when nearly empty.

A linked list has no capacity limit, uses memory in proportion to its items, and makes every operation O(1) in the worst case, since nothing is ever copied in bulk. But each node carries an extra reference and each insertion creates an object, and allocation plus later garbage collection cost more than writing an array slot.

In practice the circular array usually wins, which is why Java's ArrayDeque uses it. A linked list pays off when every operation must be guaranteed fast or when the queue's length swings widely.

8.4Kinds of queues and the deque

The basic queue fixes one end for insertion and one for removal. Other kinds of queues relax or change that rule; this section surveys them and studies the most general, the double-ended queue.

8.4.1Kinds of queues

The circular queue defines no new behavior: it is an implementation of the simple queue, and its users see no difference. The other kinds change the ADT.

The double-ended queue, which inserts and removes at both ends, is the most general; input-restricted and output-restricted queues limit it. An input-restricted queue inserts only at the rear but removes at either end, so it can act as a queue (removing at the front) or a stack (removing at the rear). An output-restricted queue accepts items at both ends but removes only at the front: an urgent job can jump to the front, an ordinary one joins at the back.

A priority queue ignores arrival order: removal always yields the item of highest priority, as an emergency room sees patients by urgency rather than arrival. It is usually built on a heap and studied separately; despite its name, it is not FIFO.

8.4.2The double-ended queue (deque)

A deque is not bound to FIFO; its behavior depends on the ends its client uses. Adding and removing at the rear only makes it a stack (LIFO); adding at the rear and removing at the front makes it a queue (FIFO). It subsumes both, which is why Java recommends ArrayDeque for either role.

Figure 8.16 shows the flexibility. If 20 came first, then 21 and 22 may have gone to the front, 23 and 24 to the rear, 26 and 27 to the front, and 25 to the rear. The result is neither arrival order nor its reverse; each item's place depends on the end it entered.

Table 8.15 lists our operation names and their ArrayDeque counterparts.

ArrayDeque also has stack operations: push(e) adds at the front (addFirst) and pop() removes there (removeFirst); its queue operations offer and poll are offerLast and pollFirst. Mixing them on one object confuses: push puts an item at the front, offer at the rear.

A deque can use a circular array — inserting at the front steps back with front = (front − 1 + N) % N and writes there, and removing at the rear just decrements size — as ArrayDeque does. These notes use the other option, a doubly linked list.

boolean isPalindrome(String s) {
    Deque<Character> d = new ArrayDeque<>();
    for (char c : s.toCharArray())
        d.offerLast(c);
    while (d.size() > 1)
        if (!d.pollFirst().equals(d.pollLast()))
            return false;
    return true;
}

8.4.3Deque operations step by step

Our deque is a doubly linked list: each node has prev and next references, and the deque keeps head (first node), tail (last node), and size.

Apply addLast(5), addLast(8), addFirst(3), addLast(9), removeLast(), and removeFirst() to an empty deque:

The first insertion is special: in an empty list the new node is both head and tail. Later a new node is linked to the end node in both directions; adding at the rear sets the new node's prev to the old tail and the old tail's next to the new node, and adding at the front mirrors this.

With both ends referenced, every insertion is O(1). The removals show what prev is worth: removeLast() finds the new tail in one step, tail.prev, where a singly linked list would need an O(n) walk from the head to the next-to-last node. The price is one more reference per node.

8.4.4Code: adding at either end

The node class:

class Node<E> {
    E data;
    Node<E> prev, next;
    Node(E data) { this.data = data; }
}

The insertion methods:

public void addFirst(E data) {
    Node<E> node = new Node<>(data);
    if (isEmpty()) {
        head = tail = node;
    } else {
        node.next = head;
        head.prev = node;
        head = node;
    }
    size++;
}

public void addLast(E data) {
    Node<E> node = new Node<>(data);
    if (isEmpty()) {
        head = tail = node;
    } else {
        node.prev = tail;
        tail.next = node;
        tail = node;
    }
    size++;
}

Both methods create a node with prev and next set to null. In an empty deque it becomes head and tail at once: head = tail = node; runs right to left, assigning tail first and then head. Otherwise three assignments follow.

In addFirst the new node points to the old head (node.next = head), the old head points back (head.prev = node), and the head moves (head = node). The order matters: doing head = node first would lose the old head before it could be linked.

Swapping head with tail and prev with next turns addFirst into addLast. Neither loops; both are O(1).

8.4.5Code trace: addFirst()

Apply addFirst(5) and then addFirst(3) to an empty deque; 3 should end up in front.

The list is now 3 ⇄ 5, read 3, 5 from head to tail and 5, 3 from tail to head. Two-way traversal relies on both node.next = head and head.prev = node. Nothing is traversed: O(1).

8.4.6Code: removing from either end

public E removeFirst() {
    if (isEmpty()) return null;
    E data = head.data;
    head = head.next;
    if (head == null)
        tail = null;       // now empty
    else
        head.prev = null;
    size--;
    return data;
}

public E removeLast() {
    if (isEmpty()) return null;
    E data = tail.data;
    tail = tail.prev;
    if (tail == null)
        head = null;       // now empty
    else
        tail.next = null;
    size--;
    return data;
}

On an empty deque both methods return null, as in Goodrich's interface. Otherwise the end value goes into data and the end reference moves one node inward: head = head.next or tail = tail.prev.

If that reference is now null, the removed node was the only one, so the other end is set to null too. Otherwise the new end's outward link is cut (head.prev = null or tail.next = null), so the list no longer refers to the removed node. Then size drops and the value is returned.

8.4.7Code trace: removeLast()

Call removeLast() twice on the deque 3 ⇄ 5: 5 comes out, then 3, leaving it empty.

On the first call, tail = tail.prev finds the next-to-last node without searching. tail is not null, so the else branch cuts the link to node 5 with tail.next = null, detaching it.

On the second call the single node's prev is null, so tail becomes null while head still points to node 3. tail == null holds and head = null runs; without it head would keep pointing to the deleted node. Both calls are O(1).

8.4.8Sliding window maximum

A classic problem that needs both ends of a deque: slide a window of width k across an array a from left to right and report the largest value at each position. This is a sliding window problem. For a = {1, 3, −1, −3, 5, 3, 6} and k = 3 the five windows {1, 3, −1}, {3, −1, −3}, {−1, −3, 5}, {−3, 5, 3}, {5, 3, 6} have maxima 3, 3, 5, 5, 6.

Brute force scans k items in each of the n − k + 1 windows, O(n·k), which reaches O(n²) for k = n/2. Doing better means reusing earlier work. The key fact: an item with a greater or equal item to its right can never again be a window maximum, since it leaves the window first while the larger item stays. Such items can be discarded at once.

The algorithm keeps candidate indices in a deque whose values decrease from front to rear, so the maximum is always in front. For each new index i:

1. Drop from the front the front index if it has left the window (≤ i − k).
2. Drop from the rear every index whose value is at most a[i]; it is no longer a candidate.
3. Add i at the rear. From the first full window on (i ≥ k − 1), the value at the front index is the window's maximum.

int[] windowMax(int[] a, int k) {
  int[] maxes = new int[a.length - k + 1];
  Deque<Integer> d = new ArrayDeque<>(); // indices
  for (int i = 0; i < a.length; i++) {
    if (!d.isEmpty() && d.peekFirst() <= i - k)
      d.pollFirst();        // outside the window
    while (!d.isEmpty() && a[d.peekLast()] <= a[i])
      d.pollLast();         // no longer a candidate
    d.offerLast(i);
    if (i >= k - 1) maxes[i - k + 1] = a[d.peekFirst()];
  }
  return maxes;
}

d holds indices, and values are read as a[d.peekFirst()] and a[d.peekLast()]. Whether an item has left the window depends on its position; with values alone we could not tell which of several equal values had left. maxes holds the n − k + 1 results, the window ending at i writing to maxes[i − k + 1].

The key step is i = 4. The window covers indices 2–4, so the front index 1 (1 ≤ 4 − 3 = 1) is dropped. The incoming 5 beats −3 and −1 at the rear, which can never be maxima again, so they go too, leaving 4:5. At i = 3, by contrast, −3 was added and nothing dropped: small as it is, −3 could still become the maximum once 3 and −1 left.

This counting trick — each item enters once and leaves at most once — recurs throughout queue and stack algorithms; the amortized analysis of the two-stack queue uses it too.

8.5Applications of queues

In the first three problems below, a queue cycles through work fairly or walks a structure level by level; the last builds a queue from stacks.

8.5.1A round-robin scheduler

Many processes want to run, but a processor core runs one at a time. The scheduler shares the processor among them, and one of the simplest and fairest methods is round robin.

Ready processes wait in a FIFO ready queue. The front process runs for at most q time units, the time slice or quantum. If it finishes, it leaves; if not, it returns to the rear with its remaining time. No process can monopolize the processor, and each runs again within one round.

Performance hinges on q. Too large, and every process finishes in one slice: the method becomes first-come, first-served, with short processes stuck behind long ones. Too small, and the processor switches constantly; each context switch has a cost, so much of its time goes to switching instead of work. In practice q is long enough for most processes to finish an interactive task in one slice.

A process's waiting time is its completion time minus its running time: 10 − 5 = 5 for P1, 9 − 3 = 6 for P2, 6 − 2 = 4 for P3, an average of 15/3 = 5. Run back to back (P1, P2, P3), they would finish at 5, 8, and 10 and wait 0, 5, and 8, an average of 13/3 ≈ 4.33. So round robin does not always lower the average wait; what it buys is that no process waits long for its first turn — all three ran within the first 6 units.

8.5.2Code trace: roundRobin()

The scheduler's code is short. A process is represented by this class:

class Process {
    String name;      // process name (P1, P2, …)
    int remaining;    // remaining running time
    Process(String name, int remaining) { this.name = name; this.remaining = remaining; }
}

void roundRobin(Queue<Process> q, int quantum) {
  int t = 0;
  while (!q.isEmpty()) {
    Process p = q.poll();
    int run = Math.min(quantum, p.remaining);
    t += run;
    p.remaining -= run;
    if (p.remaining > 0) q.offer(p);
    else System.out.println(p.name + " t=" + t);
  }
}

t is the elapsed time, and the loop runs until the queue is empty. Each round takes the front process with poll() and runs it for run = Math.min(quantum, p.remaining), so a process about to finish runs only for what it needs. t grows and p.remaining shrinks by run; a process with time left returns to the rear with offer(p), and a finished one has its completion time printed.

The code repeats the hand computation. In rounds 5 and 6, run is 1 because the remaining time is shorter than the slice. The output is "P3 t=6", "P2 t=9", "P1 t=10".

A round makes one poll and at most one offer, so it is O(1). A process of length s takes ⌈s/q⌉ rounds; here ⌈5/2⌉ + ⌈3/2⌉ + ⌈2/2⌉ = 3 + 2 + 1 = 6.

8.5.3The Josephus problem

The Josephus problem comes from an old puzzle. n people stand in a circle and count off from a given person; every kth person leaves the circle, and counting resumes with the next one. Who is the last one left?

A queue rotates the circle naturally: moving the front person to the rear advances the count by one. Each round moves k − 1 people to the rear and then eliminates the person at the front, the kth.

String josephus(Queue<String> q, int k) {
  while (q.size() > 1) {
    for (int i = 1; i < k; i++)
      q.offer(q.poll());      // front to the rear
    String out = q.poll();
    System.out.println(out + " eliminated");
  }
  return q.poll();
}

The for loop runs q.offer(q.poll()) for i = 1 to k − 1, moving the front person to the rear each time. Then poll() removes the front person for good and prints the name. The outer while runs while more than one person remains, and the survivor is returned.

Here is the trace for n = 5 (A, B, C, D, E) and k = 3.

The elimination order is C, A, E, B; D survives. In round 4 both remaining people move to the rear, the count comes back to B, and B goes. As the circle shrinks the count may lap it several times, and the queue handles this with no special case.

Of n people, n − 1 are eliminated, each round costing k − 1 moves and one removal, k queue operations. The total is (n − 1) · k, or O(n·k); the example used 4 · 3 = 12.

If only the survivor matters, a recurrence suffices. Numbering from 0, J(1) = 0 and J(n) = (J(n − 1) + k) % n; for k = 3, J(2) = 1, J(3) = 1, J(4) = 0, J(5) = 3, and person 3 is the fourth, D. This runs in O(n) but gives no elimination order, which the queue plays out step by step.

8.5.4Binary numbers from 1 to n

The task: list the binary representations of 1 to n in increasing order — {"1", "10", "11"} for n = 3, {"1", "10", "11", "100", "101"} for n = 5.

Converting each number separately works, but a queue is more elegant. Appending "0" to the binary form of x gives 2x, appending "1" gives 2x + 1: "10" (2) yields "100" (4) and "101" (5). This arranges the numbers in a tree rooted at "1," each node's children being the node with "0" and "1" appended.

A queue walks a tree level by level: take a string, write it to the result, add its two children at the rear. First in is first out, so each level is finished before the next begins, left to right. This is breadth-first traversal. Numbers on one level have equal length and grow left to right, and deeper ones are longer and thus larger, so the output is exactly increasing.

String[] generateBinary(int n) {
    String[] result = new String[n];
    Queue<String> q = new LinkedList<>();
    q.offer("1");
    for (int i = 0; i < n; i++) {
        result[i] = q.poll();
        q.offer(result[i] + "0");
        q.offer(result[i] + "1");
    }
    return result;
}

8.5.5Code trace: generateBinary(4)

The method creates a result array of n slots and an empty queue — a LinkedList, used only through Queue operations — and adds the root "1." Each of the n rounds removes the front string, writes it to the result, and adds its two children.

The front string is always the smallest waiting. At i = 4, 4 < 4 fails, and the method returns {"1", "10", "11", "100"}. The five strings left in the queue go unused, a small waste that a counter limiting the insertions could avoid.

In queue operations the cost is n poll and 2n offer calls, O(n). But each operation builds a string of about log₂ n characters, and concatenation is linear in length, so the character-level work is O(n log n). The queue holds at most about n + 1 strings.

8.5.6A queue from two stacks

A design question to finish: can stacks alone make a queue? One stack reverses order, so it cannot; but reversing twice restores the order, and that is the idea behind two stacks.

Insertions go onto inbox; removals come from outbox. enqueue pushes onto inbox. dequeue first checks outbox: if it is empty, every item in inbox is popped and pushed onto outbox, which reverses the order and puts the oldest item on top; then outbox is popped.

Deque<Integer> inbox = new ArrayDeque<>();
Deque<Integer> outbox = new ArrayDeque<>();
void enqueue(int x) {
  inbox.push(x);
}
int dequeue() {
  if (outbox.isEmpty())
    while (!inbox.isEmpty())
      outbox.push(inbox.pop());
  return outbox.pop();
}

ArrayDeque serves as the stack, with push and pop at its head. On an empty queue both stacks are empty, the transfer moves nothing, and outbox.pop() throws NoSuchElementException: underflow is reported by exception.

Apply enqueue(1), enqueue(2), enqueue(3), dequeue(), enqueue(4), and three dequeue() calls; stacks are written bottom to top.

On the first dequeue, outbox is empty. The 3 on top of inbox moves first, landing at the bottom of outbox, then 2, then 1, which ends on top and is popped. FIFO holds: the first item in is the first out.

enqueue(4) puts 4 into inbox and leaves 2 and 3 in outbox. The next two dequeue calls find outbox non-empty, so 2 and 3 come out without a transfer; 4 rightly waits, having arrived after them. The last dequeue finds outbox empty and transfers and removes 4. The output 1, 2, 3, 4 matches the input; 4 items were transferred in all.

One dequeue can be costly: with outbox empty and n items in inbox, the transfer makes n pops and n pushes, O(n) in the worst case. But such calls cannot be frequent.

The 8 operations of Table 8.23 made 4 pushes onto inbox, 4 transfers (a pop and a push each), and 4 pops from outbox: 4 + 8 + 4 = 16 stack operations, exactly the bound 4 · 4 = 16, since each item was transferred once.

Conversely, one queue can make a stack. push(x) adds x and then moves every earlier item from the front to the rear, one at a time, bringing x to the front, so pop removes from the front. Here pop is O(1) and push O(n), and amortizing does not help, because every push rotates the whole queue.

8.6Common mistakes

Most queue bugs fall into a few types. The table collects the mistakes noted throughout the chapter; use it as a checklist when reviewing queue code.

The last row is a design decision: poll() returns null when empty, so a null item would make "empty" and "front item is null" indistinguishable. ArrayDeque forbids null; LinkedList allows it, so its poll results need more care.

The chapter's problems share a pattern. A queue is the right tool when the question is "Which waiting item has waited longest?": the process waiting longest for the processor, the next person in the Josephus count, the smallest number whose children are not yet generated. A stack asks the opposite: "Which unresolved item was seen most recently?" If items must be handled in arrival order, think queue; if both ends matter, as in the sliding window, think deque.

8.7Summary

• A queue inserts at the rear and removes at the front: FIFO. A good implementation makes enqueue, dequeue, first/peek, size, and isEmpty all O(1).
• Removing from an empty queue is underflow; adding to a full fixed-capacity one, overflow. In Java's Queue, add/remove/element throw, while offer/poll/peek return false or null. ArrayDeque is array-based, LinkedList linked.
• A simple array queue cannot reuse slots freed at the front and can report "full" while nearly empty. Shifting fixes this but makes removal O(n).
• A circular queue advances indices with (i + 1) % N and reuses slots. With a counter, the insertion point is (front + size) % N, empty is size == 0, and full is size == N; with one empty slot it holds at most N − 1 items and is full when (rear + 1) % N == front.
• A full circular queue grows by copying into a double-size array in (front + k) % N order: one resize is O(n), but n insertions cost under 3n, amortized O(1) each. Arrays.copyOf scrambles a wrapped queue.
• A linked queue inserts at the end and removes at the head through front and rear, both in worst-case O(1); the first insertion must set front, and removing the last item must clear rear.
• A deque inserts and removes at both ends: one end only makes it a stack, one end in and the other out a queue. In a doubly linked list, prev makes rear removal O(1); removing the last item must clear both ends.
• Sliding window maximum takes O(n) with a deque of indices whose values decrease front to rear; each index enters once and leaves at most once.
• Round robin runs each process for at most q units and requeues unfinished ones at the rear. Josephus takes O(n·k), moving k − 1 people to the rear and eliminating the kth. Binary numbers come out in increasing order by queueing the children "x0" and "x1."
• A queue from two stacks pushes onto one stack and transfers to the other when it is empty. Each item moves at most once, so operations are amortized O(1), though one dequeue can be O(n).

8.8Key terms

Each term links to the course glossary, which gives its Turkish equivalent and its use in other chapters.

• queue
• FIFO (first-in, first-out)
• front
• rear
• enqueue
• dequeue
• abstract data type (ADT)
• interface
• generic
• overflow
• underflow
• array
• capacity
• circular queue
• amortized analysis
• singly linked list
• doubly linked list
• node
• deque (double-ended queue)
• priority queue
• sliding window
• scheduler
• round robin
• time slice (quantum)
• breadth-first search (BFS)
• stack
• time complexity
• space complexity

8.9Test Yourself

1. Starting empty, a queue receives enqueue(5), enqueue(8), dequeue(), enqueue(2), first(), enqueue(6), dequeue(), dequeue(). What do the value-returning calls return, and what remains?

   Answer

   dequeue() returns 5, leaving 8. After enqueue(2) the queue is 8, 2, and first() returns 8 without removing it. After enqueue(6) it is 8, 2, 6; the two dequeue() calls return 8 and 2. Returned: 5, 8, 8, 2; only 6 remains.

2. A counter-based circular queue has N = 8, front = 5, size = 6. Where are the items, where is the last one, and where does the next insertion go?

   Answer

   The items are at (5 + k) % 8 for k = 0, …, 5: 5, 6, 7, 0, 1, 2. The last is at (5 + 6 − 1) % 8 = 2, and the next insertion goes to (5 + 6) % 8 = 3. Two more insertions fit (slots 3 and 4) before size == 8.

3. An empty counter-based circular queue of capacity 4 receives enqueue(1), enqueue(2), enqueue(3), dequeue(), dequeue(), enqueue(4), enqueue(5), enqueue(6). What are the array, front, and size at the end, and what does a further enqueue(7) do?

   Answer

   Slots 0–2 fill; the removals return 1 and 2, giving front = 2, size = 1. Then 4 goes to (2 + 1) % 4 = 3, 5 to (2 + 2) % 4 = 0, 6 to (2 + 3) % 4 = 1. The array is [5, 6, 3, 4], front = 2, size = 4: the queue 3, 4, 5, 6 is full, and enqueue(7) throws IllegalStateException("full").

4. A full circular queue of capacity 3 has data = [R, P, Q] and front = 1. What are the array, front, and size after a growing enqueue(S)?

   Answer

   The logical order is P, Q, R. Since size == 3, resize(6) runs: temp[0] = data[1] = P, temp[1] = data[2] = Q, temp[2] = data[(1 + 2) % 3] = data[0] = R, and front = 0. S goes to (0 + 3) % 6 = 3, giving [P, Q, R, S, _, _], front = 0, size = 4.

5. Suppose if (front == null) rear = null; is deleted from the linked queue's dequeue. Trace enqueue(7), dequeue(), enqueue(9) from an empty queue. When does the bug become visible?

   Answer

   After enqueue(7) both ends point to node 7. dequeue() returns 7 and nulls front, but rear stays on node 7 with size = 0. enqueue(9) finds the queue empty and moves both front and (via rear = temp) rear to 9, so the final state is correct. The bug shows only if rear is read while the queue is empty: rear() would return 7, which is not in the queue, and node 7 cannot be freed.

6. On Deque<Integer> d = new ArrayDeque<>(); we call d.offerLast(1), d.offerFirst(2), d.push(3), d.offer(4), d.pollLast(), d.pop(). What do the last two calls return, and what does printing d show?

   Answer

   offerLast(1) → [1]; offerFirst(2) → [2, 1]; push(3) adds at the front → [3, 2, 1]; offer(4) adds at the rear → [3, 2, 1, 4]. pollLast() returns 4 → [3, 2, 1]; pop() returns 3 from the front → [2, 1]. System.out.println(d) prints [2, 1].

7. What does windowMax({2, 7, 3, 1, 5, 4}, 2) return, and how many times is pollLast() called?

   Answer

   The result is [7, 7, 3, 5, 5]. At i = 1, 7 drops 0:2 from the rear (1st pollLast); at i = 2, 3 is added; at i = 3, 1:7 leaves from the front and 1 is added; at i = 4, 2:3 leaves from the front and 5 drops 3:1 (2nd pollLast); at i = 5, 4 is added. Two pollLast and two pollFirst calls in all, fewer than the 6 insertions.

8. The ready queue holds P1 (3 units), P2 (4 units), and P3 (1 unit), and q = 2. When does each process finish under round robin, and what is the average waiting time?

   Answer

   0–2: P1 (1 left), queue P2, P3, P1. 2–4: P2 (2 left), queue P3, P1, P2. 4–5: P3 finishes. 5–6: P1 finishes. 6–8: P2 finishes. Completion: P3 = 5, P1 = 6, P2 = 8. Waiting times 6 − 3 = 3, 8 − 4 = 4, 5 − 1 = 4; average 11/3 ≈ 3.67 units.

9. For six people numbered 1 to 6, in what order does josephus(q, 3) eliminate them, and whom does it return? Check the result with J(n) = (J(n − 1) + k) % n.

   Answer

   The order is 3, 6, 4, 2, 5, and 1 survives. Numbering from 0: J(1) = 0, J(2) = 1, J(3) = 1, J(4) = 0, J(5) = 3, J(6) = (3 + 3) % 6 = 0; position 0 is person 1, so the methods agree. The queue performs 5 · 3 = 15 operations.

10. A two-stack queue receives enqueue(a), enqueue(b), dequeue(), enqueue(c), enqueue(d), dequeue(), dequeue(), dequeue(). What do the removals return, which ones transfer, and how many items move in total?

    Answer

    1st dequeue: outbox is empty, so b and a move (2 items) and a is returned. c and d go into inbox. 2nd: outbox holds b, no transfer; b is returned. 3rd: outbox is empty, d and c move (2 items), and c is returned. 4th: d. Output a, b, c, d; transfers on the 1st and 3rd calls, 4 items in all.

8.10Further reading

• M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Data Structures and Algorithms in Java (6th ed., 2014), Sections 6.2 and 6.3: the queue ADT, circular-array and linked implementations, and the deque, with a Java interface close to ours.
• R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 1.3: linked and resizing-array queues in short, clear code, with iterators and generics.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed., 2009), Section 10.1: a formal array implementation of the queue; the exercises include the two-stack queue and the deque.
• A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts (10th ed., 2018), Chapter 5: CPU scheduling, including round robin, the choice of quantum, and criteria such as waiting time.

8.11References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009.
2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6th ed., Wiley, 2014.
3. R. Lafore, Data Structures and Algorithms in Java, 2nd ed., Sams, 2002.
4. Oracle, Java SE 17 API Specification: documentation for java.util.Queue, java.util.Deque, java.util.ArrayDeque, and java.util.PriorityQueue.
5. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
6. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10th ed., Wiley, 2018.

Related pages: Chapter 8 slides · Study questions · Glossary · © Sercan Külcü. All rights reserved.