The Stack and Queue ADTs: Linear Structures

In the previous lesson you built a list that does everything: insert anywhere, delete anywhere, read anywhere.

Now we are going to do the opposite: take powers away. A stack and a queue are lists that we forbid from doing almost anything. You may only touch one end.

And that restriction, which sounds like a limitation, is exactly what makes them valuable, for two reasons:

1. They express intent. If a method takes a Stack, you already know order matters and only the tip is touched. A generic List tells you nothing.
2. They guarantee speed. Since you only operate at the ends, every operation is O(1). Always. No exceptions, no odd cases.

1. The Stack (LIFO): last in, first out

Think of a stack of plates: you add on top and take from the top. To reach the bottom one you must remove everything above it.

There are only four operations:

Implementation over nodes

Here is where the previous lesson pays off: a stack is exactly a linked list where you only use addFirst and removeFirst. The two O(1) operations of a linked list.

public class Stack<T> {
    private Node<T> top;      // it is the "head" from the previous lesson, renamed
    private int size;

    public void push(T data) {
        Node<T> fresh = new Node<>(data);
        fresh.next = top;      // the same reference dance as always
        top = fresh;
        size++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("The stack is empty");
        }
        T data = top.data;
        top = top.next;        // the old node has no references left: the GC takes it
        size--;
        return data;
    }

    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("The stack is empty");
        }
        return top.data;       // looks, does not touch
    }

    public boolean isEmpty() { return top == null; }
    public int size() { return size; }
}

Notice there is not a single loop. No operation walks anything. That is why they are all O(1).

Throwing an exception on pop() over an empty stack is the right call: popping an empty stack is a programmer usage error, not an expected condition. It is a RuntimeException, exactly as we discussed in the Exception Handling and Robustness lesson.

2. The Queue (FIFO): first in, first out

A bank line. You enter at the back, you are served at the front, and nobody cuts.

public class Queue<T> {
    private Node<T> front;   // exit here
    private Node<T> back;    // entry here
    private int size;

    public void enqueue(T data) {
        Node<T> fresh = new Node<>(data);
        if (isEmpty()) {
            front = fresh;
            back = fresh;         // with one element, both point at the same node
        } else {
            back.next = fresh;    // hook it onto the end
            back = fresh;         // and move the back pointer
        }
        size++;
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("The queue is empty");
        }
        T data = front.data;
        front = front.next;
        if (front == null) {
            back = null;          // ← the case almost everyone forgets
        }
        size--;
        return data;
    }

    public T peek() {
        if (isEmpty()) throw new NoSuchElementException("The queue is empty");
        return front.data;
    }

    public boolean isEmpty() { return front == null; }
}

That if (front == null) back = null; is the classic bug of this structure. If you remove the last element and do not clear back, it keeps pointing at a node that no longer belongs to the queue. The next enqueue hooks onto it and the data lands in a phantom place. It compiles, it runs, and it gives wrong answers.

3. The circular queue: why the % operator exists

If you implement the queue over an array instead of nodes, a non-obvious problem shows up.

public class CircularQueue<T> {
    private final Object[] items;
    private int front = 0;
    private int count = 0;
    private final int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.items = new Object[capacity];
    }

    public void enqueue(T item) {
        if (count == capacity) {
            throw new IllegalStateException("The queue is full");
        }
        int back = (front + count) % capacity;   // ← the modulo does the magic
        items[back] = item;
        count++;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (count == 0) {
            throw new NoSuchElementException("The queue is empty");
        }
        T item = (T) items[front];
        items[front] = null;                  // release the reference for the GC
        front = (front + 1) % capacity;       // ← and here too
        count--;
        return item;
    }
}

This pattern — a fixed-size array with two wrapping indices — is called a circular buffer, and it is everywhere: audio drivers, network buffers, logging systems. When you meet it in the wild, you will know exactly what it is.

4. Where they are actually used

Stacks:

• The JVM call stack. Every method call pushes a stack frame; every return pops it. The StackOverflowError from infinite recursion is literally this stack overflowing. And the stack trace from the Exception Handling and Robustness lesson is that stack, printed.
• Undo (Ctrl+Z). Every action is pushed; undoing is a pop.
• The browser back button.
• Expression evaluation and syntax checking, which is this lesson’s exercise.

Queues:

• Print queues, task queues, message queues.
• BFS traversal of graphs and trees, which you will see in the The Tree ADT: Traversals and Binary Search Trees and Graphs: Matrix, Adjacency List, BFS, DFS, and Dijkstra lessons.
• Producer-consumer between threads: one thread enqueues work, another dequeues it. That is the basis of the ExecutorService in the Concurrent Programming: Threads, Synchronization, and Pools lesson.
• Order processing in any system where arrival order is the rule.

5. How it is actually done in Java

Do not implement this in production. Java already ships it, and ships it well:

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

// STACK
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
System.out.println(stack.pop());    // B
System.out.println(stack.peek());   // A (without removing it)

// QUEUE
Deque<String> queue = new ArrayDeque<>();
queue.offer("A");                   // enqueue
queue.offer("B");
System.out.println(queue.poll());   // A — dequeue

A Deque (“double ended queue”) lets you operate on both ends, so it serves as both stack and queue. ArrayDeque is the recommended implementation for both: internally it uses exactly the circular buffer you just saw.

Do not use Java’s Stack class. It dates from 1996, extends Vector, is needlessly synchronized on every operation — which makes it slow — and, worst of all, iterates bottom to top, the opposite of how a stack works. Java’s own documentation recommends ArrayDeque instead.

There are also offer/poll as alternatives to add/remove: the former return null or false when the operation cannot be done, the latter throw. Pick based on whether the case is expected or an error.

6. The classic: is the expression balanced?

This problem is the “hello world” of stacks, and it turns up in job interviews with suspicious frequency. The idea is to verify that every (, [, and { has its matching closer, in the right order.

The conceptual key: the last symbol you opened is the first one you must close. That sentence is, word for word, the definition of LIFO. Which is why the problem and the structure fit so perfectly.

7. Common mistakes

8. Guided hands-on exercise

Challenge: isBalanced(String expression)

Write a method returning true when every opening symbol (, [, { has its matching closer in the correct order.

Cases it must get right:

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

public class BalanceChecker {

    // Each closer maps to its matching opener
    private static final Map<Character, Character> PAIRS = Map.of(
        ')', '(',
        ']', '[',
        '}', '{'
    );

    public static boolean isBalanced(String expression) {
        if (expression == null) {
            return false;
        }

        Deque<Character> stack = new ArrayDeque<>();

        for (char c : expression.toCharArray()) {

            if (PAIRS.containsValue(c)) {
                // An opener: note it down and move on
                stack.push(c);

            } else if (PAIRS.containsKey(c)) {
                // A closer. Two ways to fail here:

                // 1) Nothing is open: closing something never opened
                if (stack.isEmpty()) {
                    return false;
                }

                // 2) The most recent opener is not of the same kind
                if (stack.pop() != PAIRS.get(c)) {
                    return false;
                }
            }
            // Any other character takes no part: ignored
        }

        // Third way to fail: openers left dangling.
        // If the stack is empty, everything closed correctly.
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String[] cases = {
            "{ a + [ b * ( c ) ] }",   // true
            "( ( a )",                 // false: missing a closer
            "( a ] )",                 // false: crossed closing
            ") a (",                   // false: closes without opening
            "",                        // true: nothing to unbalance
            "no symbols here"          // true
        };

        for (String c : cases) {
            System.out.printf("%-24s → %s%n", "\"" + c + "\"", isBalanced(c));
        }
    }
}

9. Discrete-event simulation with two queues

A discrete-event simulation does not wait for real time to pass. It maintains a simulated clock and jumps directly to the next event’s timestamp. It therefore does not use Thread.sleep: sleeping would make tests slow and dependent on the machine’s wall clock without improving the model.

This problem needs two queues with different responsibilities:

A timestamp alone is not enough for ordering: an arrival and a completion may coincide. An increasing sequence is a deterministic tie-breaker. The same inputs always produce exactly the same processing order.

Bounded runnable example

The following model represents one server, known arrivals, and a constant service duration. Every Event and Customer is an immutable record.

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;

public final class QueueSimulator {
    private static final int MAX_EVENTS = 20_000;

    private enum Type { ARRIVAL, COMPLETION }

    private record Event(long time, long sequence, Type type, int customerId) {
        Event {
            if (time < 0 || sequence < 0) {
                throw new IllegalArgumentException("time and sequence must be nonnegative");
            }
            Objects.requireNonNull(type, "type is required");
        }
    }

    private record Customer(int id, long arrivalTime) {}

    public record Metrics(int served, double averageWait, int maximumQueueLength) {}

    private final PriorityQueue<Event> futureEvents = new PriorityQueue<>(
        Comparator.comparingLong(Event::time)
            .thenComparingLong(Event::sequence)
    );
    private final ArrayDeque<Customer> serviceQueue = new ArrayDeque<>();
    private final long serviceDuration;
    private long clock = 0;
    private long nextSequence = 0;
    private long totalWaitingTime = 0;
    private int served = 0;
    private int maximumQueueLength = 0;
    private boolean serverBusy = false;

    private QueueSimulator(long serviceDuration) {
        if (serviceDuration <= 0) {
            throw new IllegalArgumentException("serviceDuration must be positive");
        }
        this.serviceDuration = serviceDuration;
    }

    public static Metrics simulate(long[] arrivalTimes, long serviceDuration) {
        if (arrivalTimes == null || arrivalTimes.length == 0) {
            throw new IllegalArgumentException("arrivalTimes must contain at least one timestamp");
        }
        if (arrivalTimes.length * 2L > MAX_EVENTS) {
            throw new IllegalArgumentException("simulation exceeds MAX_EVENTS");
        }

        QueueSimulator simulator = new QueueSimulator(serviceDuration);
        long previous = -1;
        for (int id = 0; id < arrivalTimes.length; id++) {
            long arrival = arrivalTimes[id];
            if (arrival < 0 || arrival < previous) {
                throw new IllegalArgumentException(
                    "arrival times must be nonnegative and monotonic"
                );
            }
            simulator.schedule(arrival, Type.ARRIVAL, id);
            previous = arrival;
        }
        return simulator.run();
    }

    private void schedule(long time, Type type, int customerId) {
        if (time < clock) {
            throw new IllegalArgumentException("cannot schedule an event in the past");
        }
        futureEvents.add(new Event(time, nextSequence++, type, customerId));
    }

    private Metrics run() {
        int processed = 0;
        while (!futureEvents.isEmpty()) {
            if (++processed > MAX_EVENTS) {
                throw new IllegalStateException("simulation did not converge within the limit");
            }

            Event event = futureEvents.remove();
            if (event.time() < clock) {
                throw new IllegalStateException("simulated clock cannot move backward");
            }
            clock = event.time();

            if (event.type() == Type.ARRIVAL) {
                serviceQueue.addLast(new Customer(event.customerId(), clock));
                if (!serverBusy) {
                    startNext();
                }
                maximumQueueLength = Math.max(maximumQueueLength, serviceQueue.size());
            } else {
                served++;
                serverBusy = false;
                startNext();
            }
        }

        if (serverBusy || !serviceQueue.isEmpty()) {
            throw new IllegalStateException("calendar ended with pending work");
        }
        return new Metrics(served, (double) totalWaitingTime / served, maximumQueueLength);
    }

    private void startNext() {
        Customer customer = serviceQueue.pollFirst();
        if (customer == null) {
            return;
        }
        totalWaitingTime += clock - customer.arrivalTime();
        serverBusy = true;
        long completion = Math.addExact(clock, serviceDuration);
        schedule(completion, Type.COMPLETION, customer.id());
    }

    public static void main(String[] args) {
        Metrics metrics = simulate(new long[] {0, 1, 1, 5}, 3);
        System.out.println(metrics);
    }
}

How the model advances

1. Every valid ARRIVAL is scheduled in the future-event priority queue.
2. The loop removes the minimum event and moves clock to its timestamp; it does not increment time step by step.
3. An arrival enters the FIFO service queue. If the server is idle, service starts and a COMPLETION is scheduled.
4. A completion releases the server and starts the next pending service.
5. Simulation terminates when the calendar is empty and no work remains.

Each arrival creates at most one completion. Together with MAX_EVENTS, this property gives a bounded termination rule. Math.addExact makes clock overflow explicit.

Metrics and meaning

• Waiting time: clock - arrivalTime when service begins. The average uses served customers only.
• Queue length: number of customers waiting, excluding the one in service. Maximum queue length helps estimate capacity.
• Final clock: can be exposed to calculate throughput per time unit, but it is not wall-clock time.

Common failure modes

• Comparing only time: ties have no reproducible policy.
• Using a FIFO queue for future events: it processes insertion order rather than timestamp order.
• Using a PriorityQueue for customers who require arrival order: it changes the service discipline.
• Calling Thread.sleep: it mixes simulation with wall-clock time and slows tests.
• Scheduling an event before the current clock or accepting negative timestamps.
• Generating events without a bound or termination condition.
• Calculating waiting time at arrival rather than when service starts.
• Skipping validation and ending with customers outside the event calendar.

The FIFO queue models who is next; the priority queue models what happens next. Confusing those questions creates code that is syntactically valid but behaviorally incorrect.

Key takeaways

• Stack and queue are lists with restricted powers, and that restriction is the feature, not the shortcoming.
• Because only one end is touched, every operation is O(1). No loops, no traversals.
• The stack needs one pointer (top); the queue needs two (front and back).
• When dequeuing the last element you must clear back as well. It is the queue’s most common bug.
• The % operator turns an array into a ring: that is a circular queue, found in drivers, network buffers, and logging systems.
• pop/dequeue on an empty structure is a usage error: throw NoSuchElementException.
• In real Java use ArrayDeque as a Deque, never the old Stack class.
• “The last thing I opened is the first thing I must close” is LIFO stated in words. Which is why a stack solves balance checking.