Algorithms and Data Structures · Chapter 5

Lists, stacks and queues

So far, you have stored data in arrays or in ready-made collections. In this chapter, you build the most important data structures yourself: the stack, the queue and the linked list. They differ mainly in where elements come in and go out again, and that decides how fast each operation is.

LIFO and FIFO

A stack works by LIFO, Last In, First Out: what you put on top last, you take off first. The operations are called push (put on top), pop (take off) and peek (just look). Stacks are everywhere something is undone or nested: the back button in the browser, Ctrl+Z, checking brackets, method calls.

A queue works by FIFO, First In, First Out: whoever comes first is served first. The operations are called enqueue (join at the back) and dequeue (take from the front). Examples are print jobs or requests to a server.

ArrayDeque from java.util can do both. In the example, the same three letters come out once reversed and once in insertion order.

1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5    public static void main(String[] args) {6        Deque<String> stack = new ArrayDeque<>();7        stack.push("A");8        stack.push("B");9        stack.push("C");10        System.out.print("Stack: ");11        while (!stack.isEmpty()) {12            System.out.print(stack.pop() + " ");13        }14        System.out.println();15
16        Deque<String> queue = new ArrayDeque<>();17        queue.offer("A");18        queue.offer("B");19        queue.offer("C");20        System.out.print("Queue: ");21        while (!queue.isEmpty()) {22            System.out.print(queue.poll() + " ");23        }24        System.out.println();25    }26}

A stack with an array

For your own stack, an array and a counter size are enough. size is also the index of the next free slot, and the top element is at data[size - 1].

push: write to data[size], then size++.
pop: size--, then return data[size]. Nothing is deleted, the slot simply counts as free.

Neither operation needs a loop, no matter how many elements are on the stack. Their running time is O(1), that is, constant. You have to decide what happens on an empty or full stack: here, an IllegalStateException.

1public class Main {2    static int[] data = new int[10];3    static int size = 0;4
5    static void push(int value) {6        if (size == data.length) {7            throw new IllegalStateException("Stack is full");8        }9        data[size] = value;10        size++;11    }12
13    static int pop() {14        if (size == 0) {15            throw new IllegalStateException("Stack is empty");16        }17        size--;18        return data[size];19    }20
21    public static void main(String[] args) {22        push(1);23        push(2);24        push(3);25        System.out.println(pop());26        System.out.println(pop());27        push(9);28        System.out.println(pop());29        System.out.println("Size: " + size);30    }31}

A queue as a ring

In a queue with an array, elements join at the back and leave at the front. If you moved all elements one slot forward after each dequeue, that would be O(n). Instead, the start moves: head points to the front element, count counts the elements.

When an index reaches the end of the array, it continues at 0. The modulo operator takes care of that:

1int tail = (head + count) % data.length;   // next free slot2head = (head + 1) % data.length;           // after dequeue

That way, the array becomes a ring buffer, and both enqueue and dequeue stay O(1). In the example, 40 and 50 land at index 0 and 1 again, because those slots have become free.

1public class Main {2    static int[] data = new int[3];3    static int head = 0;4    static int count = 0;5
6    static void enqueue(int value) {7        if (count == data.length) {8            throw new IllegalStateException("Queue is full");9        }10        int tail = (head + count) % data.length;11        data[tail] = value;12        count++;13        System.out.println("enqueue " + value + " at index " + tail);14    }15
16    static int dequeue() {17        if (count == 0) {18            throw new IllegalStateException("Queue is empty");19        }20        int value = data[head];21        head = (head + 1) % data.length;22        count--;23        return value;24    }25
26    public static void main(String[] args) {27        enqueue(10);28        enqueue(20);29        enqueue(30);30        System.out.println("dequeue " + dequeue());31        System.out.println("dequeue " + dequeue());32        enqueue(40);33        enqueue(50);34        while (count > 0) {35            System.out.println("dequeue " + dequeue());36        }37    }38}

Linked lists

A singly linked list consists of nodes. Each node knows its value and the next node (next), and the last one points to null. The list itself only remembers head, the first node.

You always walk through it the same way:

1Node current = head;2while (current != null) {3    // use current.value4    current = current.next;5}

Array and linked list compared:

Read the element at index i: array O(1), list O(n), because you have to walk node by node.
Insert at the front: array O(n), because everything is moved, list O(1) with a new head.
Insert at the back: array O(1) as long as there is room, list O(n), O(1) with a tail reference.
Size: an array is fixed, a list grows as needed.

A stack can be built with either. For a queue with nodes, you also remember tail, so that enqueue doesn't have to walk to the end.

1public class Main {2    static class Node {3        int value;4        Node next;5
6        Node(int value) {7            this.value = value;8        }9    }10
11    public static void main(String[] args) {12        Node head = new Node(3);13        head.next = new Node(5);14        head.next.next = new Node(8);15
16        Node node = new Node(1);17        node.next = head;18        head = node;19
20        int sum = 0;21        Node current = head;22        while (current != null) {23            System.out.print(current.value + " -> ");24            sum += current.value;25            current = current.next;26        }27        System.out.println("null");28        System.out.println("Sum: " + sum);29    }30}

Common mistakes

Walking past null
The last node has next == null. If you read current.next.value in the loop or touch head.next on an empty list, you get a NullPointerException. Check whether head == null first, and pick the right condition: current != null to walk through all nodes, current.next != null to stop at the last one.
Losing a reference
A node that nothing points to any more is gone for good. That's why the order matters when relinking:
```
1current.next = previous;      // the rest of the list is lost2Node next = current.next;     // too late
```
Store current.next before you overwrite it. And when a queue with nodes becomes empty, also set tail to null, otherwise the next enqueue attaches to an old node.
Off-by-one when wrapping around
In a ring buffer, the last valid index is data.length - 1. A hand-made wrap-around with if easily goes wrong:
```
1if (tail == data.length - 1) {2    tail = 0;3}4tail++;   // after the wrap-around, tail becomes 1
```
Index 0 is skipped, and the queue overwrites slots that are in use. The modulo form tail = (tail + 1) % data.length is safe.

Lists, stacks and queues

LIFO and FIFO

A stack with an array

A queue as a ring

Linked lists

Common mistakes

Walking past null

Losing a reference

Off-by-one when wrapping around