Queues and deques

Think of three places where people or things wait.

• A queue at a ticket counter. The person who arrived first is served first. Newcomers join the back. This is called first in, first out, or FIFO.
• A pile of plates in a canteen. You put a clean plate on top and you take one from the top. The plate you added last is the one you use first. This is last in, first out, or LIFO, and the pile is called a stack.
• The emergency room of a hospital. It isn't first come, first served. A patient who walked in an hour ago with a sprained ankle waits while someone who just arrived with chest pain is seen at once. The most urgent goes next.

Java has a collection for each. ArrayDeque (said "array deck", short for double-ended queue) does the first two, because you can add and remove at both of its ends. PriorityQueue is the emergency room.

You will use ArrayDeque more often than you expect. It is Java's recommended stack and its recommended queue, and it is what you reach for in half of all interview problems about brackets, undo, and walking through a maze or a tree.

Remember: a stack gives back the newest thing. A queue gives back the oldest. A priority queue gives back the most urgent.

An ArrayDeque keeps its items in a row, like an ArrayList, and remembers where the front is. Adding or removing at either end is quick, because it only moves that marker, with no need to shift anything. The "How it works" part shows a neat trick it uses, which is to treat the row as a circle.

A PriorityQueue is built on a heap. Picture the tree in the diagram. Every box is smaller than the boxes below it, so the smallest item is always at the top, and poll() takes it from there. After a removal, the tree quietly shuffles a few boxes to put the next smallest on top.

The tree has no wires. It is stored in a plain array, using a neat rule: the children of slot i live in slots 2i + 1 and 2i + 2. That is the row at the bottom of the picture.

One warning. A heap only promises that the top is the best. The rest is in a loose order, not sorted. So if you print a PriorityQueue or loop over it, the items will not come out in order. To get them in order, poll them one at a time.

Every block below can be pasted into jshell. First, the pile of plates, with an ArrayDeque used as a stack.

Deque<String> plates = new ArrayDeque<>();
plates.push("plate 1");
plates.push("plate 2");
plates.push("plate 3");
System.out.println(plates.peek()); // look at the top without taking it
System.out.println(plates.pop());
System.out.println(plates.pop());
System.out.println(plates.size());

plate 3
plate 3
plate 2
1

push puts an item on top. peek looks at the top without taking it. pop takes it off. The last plate pushed was the first one popped. Declare the variable as a Deque, the interface from lesson 1, so the code says what it needs and not which class provides it.

Java also has an old class called Stack. Don't use it. It is slower and has an awkward design, and the Java documentation itself points you to ArrayDeque.

Now the ticket counter, using it as a queue.

Queue<String> line = new ArrayDeque<>();
line.offer("Asha");
line.offer("Ravi");
line.offer("Meera");
System.out.println(line.peek()); // the front of the line, still in it
System.out.println(line.poll());
System.out.println(line.poll());
System.out.println(line.size());

Asha
Asha
Ravi
1

offer joins the back of the line. poll takes the person at the front. peek shows who is at the front without removing them. Asha came first, so Asha is served first.

Because it works at both ends, a deque can do either job and more:

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("B");
deque.addFirst("A");
deque.addLast("C");
deque.addLast("D");
System.out.println(deque);
System.out.println(deque.pollFirst());
System.out.println(deque.pollLast());
System.out.println(deque);

[A, B, C, D]
A
D
[B, C]

addFirst and addLast add at the two ends. pollFirst and pollLast take from them.

Two details to know. When the deque is empty, poll and peek give you null, but pop throws a NoSuchElementException. And ArrayDeque refuses null items, so a null answer can only ever mean "nothing there".

Deque<String> deque = new ArrayDeque<>();
System.out.println(deque.poll()); // an empty queue answers null
try {
    deque.pop(); // the stack-style call complains instead
} catch (NoSuchElementException e) {
    System.out.println("pop on empty: " + e.getClass().getSimpleName());
}
try {
    deque.offer(null); // ArrayDeque refuses null, so null can always mean "empty"
} catch (NullPointerException e) {
    System.out.println("null refused");
}

null
pop on empty: NoSuchElementException
null refused

The emergency room is next. PriorityQueue hands over the smallest item first, by the natural order from lesson 8. To change what "first" means, pass a Comparator.

record Patient(String name, int severity) {}

PriorityQueue<Integer> smallestFirst = new PriorityQueue<>();
smallestFirst.offer(5);
smallestFirst.offer(1);
smallestFirst.offer(3);
System.out.println(smallestFirst.poll());
System.out.println(smallestFirst.poll());
System.out.println(smallestFirst.poll());

// The emergency room: the most serious patient is seen first.
PriorityQueue<Patient> er = new PriorityQueue<>(Comparator.comparingInt(Patient::severity).reversed());
er.offer(new Patient("Asha", 2));
er.offer(new Patient("Ravi", 9));
er.offer(new Patient("Meera", 5));
while (!er.isEmpty()) {
    System.out.println(er.poll().name());
}

1
3
5
Ravi
Meera
Asha

The numbers came out smallest first, whatever order they went in. For the patients, the comparator says "sort by severity, highest first", so Ravi (9) is seen before Meera (5) and Asha (2). Two patients with the same severity would be seen in no promised order, so give your comparator a tie-breaker if that matters.

Remember: push and pop for a stack, offer and poll for a queue, and poll a PriorityQueue to get items in order. Never loop over one and expect sorted output.

An ArrayDeque has a trick. If the front of a queue moved along an ordinary array, the empty slots at the start would be wasted. So it treats the array as a ring: after the last slot, it wraps round to slot 0. Here is a queue built that way.

static class RingQueue<T> {
    private Object[] items = new Object[4];
    private int head = 0; // the slot holding the front item
    private int size = 0;

    int size() {
        return size;
    }

    void offer(T value) {
        if (size == items.length) {
            grow();
        }
        // % wraps the position round to slot 0 after the last slot
        items[(head + size) % items.length] = value;
        size++;
    }

    @SuppressWarnings("unchecked")
    T poll() {
        if (size == 0) {
            return null;
        }
        T value = (T) items[head];
        items[head] = null;
        head = (head + 1) % items.length;
        size--;
        return value;
    }

    private void grow() {
        Object[] bigger = new Object[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[(head + i) % items.length]; // unwrap into a straight row
        }
        items = bigger;
        head = 0;
    }
}

Go through it in order.

• head is the slot holding the front item, and size counts the items.
• The back of the queue is at slot (head + size) % items.length. The % (remainder) is what wraps the position back to 0 after the last slot.
• poll reads the front, clears the slot, and moves head along by one, wrapping round too.
• When the ring is full, grow makes an array twice as big and copies the items across in queue order, starting at slot 0, which straightens the ring out again.

RingQueue<Integer> queue = new RingQueue<>();
for (int i = 1; i <= 4; i++) {
    queue.offer(i);
}
System.out.println(queue.poll());
System.out.println(queue.poll());
queue.offer(5); // lands in a slot freed at the front, by wrapping round
queue.offer(6);
queue.offer(7); // now the row is full, so it grows
StringBuilder order = new StringBuilder();
while (queue.size() > 0) {
    order.append(queue.poll()).append(' ');
}
System.out.println(order.toString().trim());

1
2
3 4 5 6 7

After two polls the first two slots were free, so 5 and 6 wrapped round into them. Number 7 found the ring full and made it grow. Nothing was ever shifted, which is why both ends are quick.

Now the heap behind PriorityQueue, using the array rule from the picture. This one holds plain numbers to keep it short.

static class TinyMinHeap {
    // A tree stored in an array: the children of slot i are slots 2i+1 and 2i+2.
    private int[] items = new int[4];
    private int size = 0;

    int size() {
        return size;
    }

    void add(int value) {
        if (size == items.length) {
            items = Arrays.copyOf(items, size * 2);
        }
        items[size] = value;
        int i = size++;
        // Swim up while the new value is smaller than its parent.
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (items[parent] <= items[i]) {
                break;
            }
            swap(parent, i);
            i = parent;
        }
    }

    int poll() {
        if (size == 0) {
            throw new NoSuchElementException("the heap is empty");
        }
        int smallest = items[0];
        items[0] = items[--size]; // the last item takes the top seat...
        int i = 0;
        while (true) { // ...and sinks until both children are bigger
            int left = 2 * i + 1;
            int right = left + 1;
            int least = i;
            if (left < size && items[left] < items[least]) {
                least = left;
            }
            if (right < size && items[right] < items[least]) {
                least = right;
            }
            if (least == i) {
                break;
            }
            swap(i, least);
            i = least;
        }
        return smallest;
    }

    private void swap(int a, int b) {
        int saved = items[a];
        items[a] = items[b];
        items[b] = saved;
    }
}

• add puts the new value in the first free slot at the bottom, then lets it swim up: while it is smaller than its parent (at slot (i - 1) / 2), swap them.
• poll takes the top. The last item then jumps into the empty top seat and sinks down: it swaps with its smaller child until both children are bigger.
• Each swim or sink goes down or up one level of the tree at a time, so the work is about the height of the tree, which is small.

TinyMinHeap heap = new TinyMinHeap();
for (int n : new int[] {5, 1, 8, 3, 2, 9}) {
    heap.add(n);
}
List<Integer> out = new ArrayList<>();
while (heap.size() > 0) {
    out.add(heap.poll());
}
System.out.println(out); // always smallest first, so sorted

[1, 2, 3, 5, 8, 9]

Numbers went in jumbled and came out smallest first. That is called heap sort when you do it on purpose.

The ring buffer is why ArrayDeque tends to beat LinkedList as a queue: no node objects, and the items sit together in memory. The Java documentation says as much.

static boolean isBalanced(String text) {
    throw new UnsupportedOperationException("does every bracket close, in the right order?");
}

static boolean isBalanced(String text) {
    Deque<Character> open = new ArrayDeque<>();
    for (char c : text.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            open.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (open.isEmpty()) {
                return false; // a closer with nothing to close
            }
            char last = open.pop();
            boolean matches = (last == '(' && c == ')')
                    || (last == '[' && c == ']')
                    || (last == '{' && c == '}');
            if (!matches) {
                return false;
            }
        }
    }
    return open.isEmpty(); // anything still open was never closed
}

static String lastStanding(List<String> names, int k) {
    throw new UnsupportedOperationException("every k-th player leaves; who is left?");
}

static String lastStanding(List<String> names, int k) {
    Queue<String> circle = new ArrayDeque<>(names);
    while (circle.size() > 1) {
        for (int i = 1; i < k; i++) {
            circle.offer(circle.poll()); // pass the parcel: front goes to the back
        }
        circle.poll(); // the k-th player leaves
    }
    return circle.peek();
}

static List<Integer> topK(int[] numbers, int k) {
    throw new UnsupportedOperationException("the k biggest numbers, biggest first");
}

static List<Integer> topK(int[] numbers, int k) {
    // A min-heap of size k: the smallest of the best k sits on top,
    // ready to be thrown out when something better comes along.
    PriorityQueue<Integer> best = new PriorityQueue<>();
    for (int n : numbers) {
        best.offer(n);
        if (best.size() > k) {
            best.poll();
        }
    }
    List<Integer> result = new ArrayList<>();
    while (!best.isEmpty()) {
        result.add(best.poll());
    }
    Collections.reverse(result); // it came out smallest first
    return result;
}

• "How would you implement a stack in Java?" ArrayDeque with push, pop and peek, declared as a Deque. Add that you avoid Stack because it is an old class and ArrayDeque is faster.
• "Stack versus queue?" A stack is last in, first out. A queue is first in, first out. Give an example of each: undo history or matching brackets for a stack, a print line or a breadth-first walk for a queue.
• "ArrayDeque or LinkedList as a queue?" ArrayDeque, almost always. No node objects, items close together in memory, and the docs say it is faster. The one exception is that LinkedList allows null.
• "poll versus remove, peek versus element?" The first of each pair returns null on an empty queue. The second throws an exception. Pick based on whether empty is normal or a bug.
• "What is a PriorityQueue, and how does it work?" A heap, stored in an array. The smallest item is on top, and offer and poll are O(log n).
• "Is a PriorityQueue sorted?" No. Only the top is promised. Iterating it shows an unspecified order. Poll to get sorted output.
• "How do you get a max-heap?" Pass a reversed comparator, for example new PriorityQueue<>(Comparator.reverseOrder()).
• "Find the k largest." Problem 3: a min-heap of size k, O(n log k).
• Say the cost. "Both ends of an ArrayDeque are O(1). A PriorityQueue is O(log n) to add and remove, and O(1) to peek."

Made by VeraStack Labs