Stacks and queues: LIFO, FIFO, circular queue and ArrayDeque

← Back to the section

Arrays and lists hold data you can reach in any order you like. Stacks and queues are a different kind of structure: they are tools, and access to their elements is deliberately restricted. The restriction looks like a downside, yet it is exactly what makes them simple and fast. The shared vocabulary is in the section intro.

Stack: last in, first out

A stack works like a pile of paper on a desk: a new sheet goes on top, and you take from the top too. Only the top element is reachable — the one put there last. That is the LIFO principle (Last In, First Out).

There are only three operations:

• push — put an element on top;
• pop — take the top element off (and get it);
• peek — look at the top element without removing it.

The simplest way to implement a stack is on an array: keep the index of the top in top, increment it and write into the cell on push, read and decrement on pop.

live example

public class Stack {
    private final long[] a;
    private int top = -1;
    Stack(int size) { a = new long[size]; }
    void push(long v) { a[++top] = v; }
    long pop()        { return a[top--]; }
    long peek()       { return a[top]; }
    boolean isEmpty() { return top == -1; }

    public static void main(String[] args) {
        Stack s = new Stack(4);
        s.push(17);
        s.push(42);
        s.push(8);
        System.out.println("on top: " + s.peek());
        StringBuilder order = new StringBuilder();
        while (!s.isEmpty()) order.append(s.pop()).append(' ');
        System.out.println("they come out: " + order);
    }
}

In went 17, 42, 8 — out came 8, 42, 17. Every operation is O(1): it always touches the same position, the top.

Where a stack is used:

• reversing order. Exactly what the example above printed: that is how a string gets reversed.
• matching brackets. An opening bracket goes onto the stack, a closing one pops it and checks the pair. That is how compilers catch unbalanced (, {, [.
• undo. Every action goes onto the stack; undo pops the last one.
• the call stack. The language itself uses a stack: on a method call the return address and the arguments are pushed, on exit they are popped. That is why recursion works at all.
• parsing expressions. The infix form 3 × (4 + 5) becomes the postfix 3 4 5 + ×, where brackets are not needed, and is then evaluated — a stack does both steps. Old calculators worked that way, and so does the Java virtual machine.

Queue: first in, first out

A queue is like a queue in a shop: people join the tail and are served from the head. That is the FIFO principle (First In, First Out). The operations:

• enqueue — add an element to the tail;
• dequeue — take an element from the head.

A queue is irreplaceable when tasks must be handled in arrival order: messages, print jobs, requests to a service, events. It is also the workhorse of breadth-first graph traversal.

Circular queue

A naive queue on an array soon hits a problem: the head and the tail creep to the right, and the left part of the array sits empty. The fix is a circular queue (ring buffer): when the tail reaches the end of the array, it jumps back to the beginning if room has been freed there. Indices are counted modulo the array length. That keeps enqueue and dequeue at O(1) with no shifting.

Deque

A deque (double-ended queue) lets you add and take from both ends. It is a generalisation: allow operations at one end only and the deque becomes a stack; add at one end and take from the other and it becomes a queue.

Priority queue

In an ordinary queue the exit order is set by arrival time; in a priority queue, by the element's priority — the first one out is not the earliest but the one that ranks highest. The analogy is a hospital emergency room: a severe case is seen first even if it arrived later.

A simple priority queue can be built on a sorted array (insert keeping the order — then taking the maximum is instant, but insertion is O(N)). When efficiency matters it is built on a special structure, the heap, where both insertion and extraction of the top element cost O(log N). This is the heart of many algorithms, Dijkstra's shortest path among them.

How Java does it

A stack and a queue are easy to write yourself — ten lines of code each — but the standard library already has them. The choice is between two classes, and one of them is better left alone.

The right one is ArrayDeque. It is the deque from the previous section, and inside it is exactly a circular queue: a plain array, two indices — head and tail — and a wrap from the far end back to the start. There is no modulo arithmetic for that wrap: the index is incremented by one and, if it hits the array length, reset to zero — one check instead of a division. When space runs out, the contents move into a bigger array: while the deque is small its length doubles, and past a few dozen elements it grows by half.

All operations are O(1) (amortised, because of that rare move into a bigger array):

• as a stack: push puts to the head, pop takes from the same place, peek looks;
• as a queue: offer adds to the tail, poll takes from the head.

One class covers both structures — a deque generalises them. The difference shows on identical input:

live example

import java.util.ArrayDeque;
import java.util.Deque;

public class StackVsQueue {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        Deque<String> queue = new ArrayDeque<>();
        for (String task : new String[]{"first", "second", "third"}) {
            stack.push(task);
            queue.offer(task);
        }
        System.out.println("stack: " + stack.pop() + ", " + stack.pop());
        System.out.println("queue: " + queue.poll() + ", " + queue.poll());
    }
}

Three identical tasks, one class — but the stack starts with the last and the queue with the first. And the Deque and Queue interfaces it implements are an ADT in its purest form: code is written against behaviour, and any implementation can be plugged in.

The class to leave alone is Stack. It appeared in the very first version of Java and inherits from Vector, so every one of its methods is synchronised: you pay for locks even in a single thread that does not need them. Worse, Stack is also a list, and it iterates bottom-up, from the oldest element towards the top — the opposite of the order in which the stack hands elements back through pop. New code does not use Stack; it takes ArrayDeque.

The priority queue lives separately: that is PriorityQueue, built on a heap.

ArrayDeque has one trap, and people hit it regularly: null cannot be stored in it — you get a NullPointerException. poll and peek return null when the deque is empty, and if null were allowed inside, that answer would become ambiguous. LinkedList in the role of a deque does accept null, and there an empty deque and a deque ending in null can no longer be told apart.

In short

• A stack is LIFO, only the top element is reachable; push/pop/peek, all O(1). Used for reversing order, matching brackets, undo, and the call stack.
• A queue is FIFO: add to the tail, take from the head; tasks are handled in arrival order. A circular queue uses the array as a ring so no space is wasted.
• A deque is a queue with access at both ends; it generalises the stack and the queue.
• A priority queue hands out the highest-priority element first; it is implemented efficiently on a heap.
• In Java one ArrayDeque covers both structures; Stack is not used — it is synchronised and iterates bottom-up, against LIFO.

What to read next

• Linked lists — another filling for a stack or a queue: insertion and deletion with no shifting.
• Heaps — how a priority queue fits into O(log N) instead of O(N).
• Monotonic stack — a technique where a stack finds the nearest greater element in one pass.
• Recursion — the call stack from the inside: what exactly overflows when recursion goes too deep.