JAVA-201 · Lesson 4 of 12 · 20 min
Stacks, queues and deques
▶ Video coming soon A video version of this lesson is on the way.
Tamsin Rhee runs the Tuesday repair nights, and her problem is a line. Bikes come in, a volunteer writes the owner's name on a tag and hangs the bike on the rack, and whoever is free takes the bike that has waited longest. On a busy night the rack is full and the order is lost. Kofi has a different problem: PartsDesk has no undo, so a mistyped count means retyping it from the clipboard. The plan for Friday, February 5, 2027 covers the two simplest disciplines in computing, which happen to solve both problems: the queue, first in, first out, and the stack, last in, first out.
Two disciplines
A queue works like the line at a counter. New items join at the tail, and items leave from the head, so the first one in is the first one out, abbreviated FIFO. A stack works like a pile of plates. New items go on the top and come off the top, so the last one in is the first one out, abbreviated LIFO. Both are restricted on purpose: by allowing only a few operations, they make it impossible to process items in the wrong order.
Queues in Java
Java's Queue interface has two sets of methods for the same three jobs, which differ in how they report trouble. offer, poll and peek return a special value: offer returns false if a bounded queue is full, and poll and peek return null when the queue is empty. add, remove and element throw an exception instead. With an ordinary unbounded queue, offer and add behave alike; the difference matters for poll versus remove on an empty queue.
| Job | Returns a special value | Throws an exception |
|---|---|---|
| Join the tail | offer(e) returns false if full | add(e) throws IllegalStateException if full |
| Leave from the head | poll() returns null if empty | remove() throws NoSuchElementException if empty |
| Look at the head | peek() returns null if empty | element() throws NoSuchElementException if empty |
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> rack = new ArrayDeque<>();
rack.offer("Ana Ruiz, commuter");
rack.offer("Theo Park, cargo bike");
rack.offer("Mei Lin, road bike");
System.out.println("waiting: " + rack);
System.out.println("next up: " + rack.peek());
while (!rack.isEmpty()) {
System.out.println("working on " + rack.poll());
}
System.out.println("poll on an empty rack: " + rack.poll());
}
}waiting: [Ana Ruiz, commuter, Theo Park, cargo bike, Mei Lin, road bike] next up: Ana Ruiz, commuter working on Ana Ruiz, commuter working on Theo Park, cargo bike working on Mei Lin, road bike poll on an empty rack: null
What this code does
Bikes leave the rack in the order they arrived, because offer joins the tail and poll takes from the head. peek shows the next bike without removing it. Once the rack is empty, poll returns null instead of throwing.
Queue is an interface. The usual implementation for a plain FIFO queue is ArrayDeque, which lesson 2's table recommended; LinkedList also implements Queue. PriorityQueue implements it too, but it hands out the smallest element rather than the oldest, as lesson 11 explains.
Stacks in Java
Java has a class called Stack, but it is a leftover from Java 1.0. It extends the old Vector class, so it synchronizes every call and lets you insert into the middle of the stack, which defeats the point. The Java documentation itself recommends using a Deque instead. The stack methods on a Deque are push, which adds to the top, pop, which removes and returns the top, and peek, which looks at it.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> undo = new ArrayDeque<>();
undo.push("set TUBE-700x25 from 12 to 14");
undo.push("set PAD-ROAD from 6 to 5");
undo.push("set CHAIN-11 from 4 to 40");
System.out.println("last change: " + undo.peek());
System.out.println("undo: " + undo.pop());
System.out.println("undo: " + undo.pop());
System.out.println("still on the stack: " + undo);
}
}last change: set CHAIN-11 from 4 to 40 undo: set CHAIN-11 from 4 to 40 undo: set PAD-ROAD from 6 to 5 still on the stack: [set TUBE-700x25 from 12 to 14]
What this code does
Each change Kofi makes is pushed onto the stack, so the most recent one is on top. The first undo pops the mistyped chain count of 40, which was the last change, and the second undo pops the pad change. The tube change is still on the stack in case he wants to undo further.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> undo = new ArrayDeque<>();
undo.push("set PAD-ROAD from 6 to 5");
System.out.println("undo: " + undo.pop());
System.out.println("undo: " + undo.pop());
}
}What this code does
pop on an empty stack throws NoSuchElementException, so the second undo stops the program. Check isEmpty first, or use poll, which returns null when there is nothing left. An undo button should be disabled when the stack is empty.
$ javac Main.java
$ java Main
undo: set PAD-ROAD from 6 to 5
Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:592)
at Main.main(Main.java:9)Deques: both ends
A Deque, a double-ended queue, can add, remove and look at both ends. Its methods come in pairs named for the end: addFirst and addLast, pollFirst and pollLast, peekFirst and peekLast, plus offerFirst, offerLast, removeFirst and removeLast. A Deque can therefore act as a queue, as a stack or as both. The queue methods offer and poll are offerLast and pollFirst; the stack methods push and pop are addFirst and removeFirst.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> rack = new ArrayDeque<>();
rack.offerLast("Ana");
rack.offerLast("Theo");
rack.offerLast("Mei");
rack.offerFirst("Ravi (warranty, goes first)");
System.out.println(rack);
System.out.println("first: " + rack.peekFirst() + ", last: " + rack.peekLast());
System.out.println("Mei collects her bike unrepaired: " + rack.pollLast());
System.out.println(rack);
}
}[Ravi (warranty, goes first), Ana, Theo, Mei] first: Ravi (warranty, goes first), last: Mei Mei collects her bike unrepaired: Mei [Ravi (warranty, goes first), Ana, Theo]
What this code does
offerLast adds the ordinary bikes at the tail, while offerFirst lets Ravi's warranty job jump to the head. peekFirst and peekLast look at both ends without removing anything. pollLast takes Mei's bike off the tail when she collects it early.
ArrayDeque has one rule that LinkedList does not: it does not accept null elements, and adding one throws NullPointerException. That is deliberate, because poll and peek use null to mean "empty"; if null could be an element, you could not tell the two apart.
How ArrayDeque works: a circular buffer
An ArrayDeque keeps its elements in an array, like ArrayList, but treats the array as a ring. It remembers the index of the head and of the tail. Adding at the tail writes into the next slot and moves the tail on; removing from the head moves the head on. When an index runs off the end of the array it wraps around to 0. Both ends are therefore O(1), with no shifting, and when the ring is full the deque grows by copying into a bigger array, as ArrayList does.
public class Main {
public static void main(String[] args) {
RingQueue q = new RingQueue(5);
for (String s : new String[] {"Ana", "Theo", "Mei"}) q.offer(s);
System.out.println("served " + q.poll() + ", served " + q.poll());
for (String s : new String[] {"Ravi", "Lin", "Omar", "Jo"}) q.offer(s);
System.out.println(q.describe());
System.out.println("full? " + q.isFull() + ", extra offer accepted? " + q.offer("Sam"));
}
}
class RingQueue {
private final String[] slots;
private int head, size;
RingQueue(int capacity) {
slots = new String[capacity];
}
boolean offer(String x) {
if (size == slots.length) return false;
int tail = (head + size) % slots.length;
slots[tail] = x;
size++;
return true;
}
String poll() {
if (size == 0) return null;
String x = slots[head];
slots[head] = null;
head = (head + 1) % slots.length;
size--;
return x;
}
boolean isFull() { return size == slots.length; }
String describe() {
StringBuilder sb = new StringBuilder("head at slot " + head + ": ");
for (int i = 0; i < size; i++) {
sb.append(slots[(head + i) % slots.length]).append(i < size - 1 ? ", " : "");
}
return sb.toString();
}
}served Ana, served Theo head at slot 2: Mei, Ravi, Lin, Omar, Jo full? true, extra offer accepted? false
What this code does
The remainder operator makes the tail index wrap around: after serving two bikes, the head is at slot 2, and Omar and Jo are written into slots 0 and 1. The queue never shifts an element, so offer and poll are constant time. This bounded version refuses a sixth bike, where ArrayDeque would grow its array instead.
A stack at work: checking brackets
Stacks shine whenever something must be matched in reverse order. A classic example is checking that brackets are balanced, as javac must do with your code. Walk through the text: push every opening bracket, and for every closing bracket pop the top and check that it is the matching opener. At the end the stack must be empty. Kofi's spreadsheet formulas, which Hamza must import, are a fair test.
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
String[] formulas = {"SUM(B2:B9)*(1+C1)", "MAX(B2,(C3)", "IF(A1>0,[B1],{C1})", "MIN(B2))("};
for (String f : formulas) {
System.out.println(f + " -> " + (balanced(f) ? "balanced" : "not balanced"));
}
}
static boolean balanced(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) return false;
char open = stack.pop();
if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
}
}
return stack.isEmpty();
}
}SUM(B2:B9)*(1+C1) -> balanced
MAX(B2,(C3) -> not balanced
IF(A1>0,[B1],{C1}) -> balanced
MIN(B2))( -> not balancedWhat this code does
Each opening bracket is pushed, and each closing bracket must match the one on top of the stack. The second formula leaves an unmatched opener on the stack, so it is not balanced. The last formula fails because a closing bracket arrives when the stack is already empty.
Choosing an implementation
| Need | Use | Why |
|---|---|---|
| A FIFO queue | ArrayDeque as Queue | O(1) at both ends, compact, fast |
| A stack | ArrayDeque as Deque, with push and pop | Stack is legacy and synchronized |
| Both ends | ArrayDeque | circular buffer with no shifting |
| A queue that holds null | LinkedList | ArrayDeque refuses null |
| Smallest or most urgent first | PriorityQueue | see lesson 11 |
| Shared between threads | ArrayBlockingQueue, ConcurrentLinkedDeque | covered in a later course |
One more option is worth knowing for later. A bounded queue has a fixed maximum size and refuses or blocks new items when full, which protects a program from being flooded. The rack holds 12 bikes, so a bounded queue of 12 models it exactly. The java.util.concurrent package has ArrayBlockingQueue for this, used with threads in a later course; for a single-threaded program, a check on size before offer is enough.
Try it yourself
Serving the repair rack
Complete serveAll so it removes bikes from the queue in arrival order and prints working on followed by each bike, then returns how many it served.
The program should print the three bikes in the order Ana, Theo, Mei and then served 3.
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> rack = new ArrayDeque<>();
rack.offer("Ana Ruiz");
rack.offer("Theo Park");
rack.offer("Mei Lin");
int n = serveAll(rack);
System.out.println("served " + n);
}
static int serveAll(Queue<String> rack) {
int served = 0;
return served;
}
}Try it yourself
Reversing with a stack
Kofi's change log is in time order, oldest first. Complete newestFirst so it pushes every entry onto an ArrayDeque and then pops them all into a new list, giving the newest first.
The program should print [chain to 40, pads to 5, tube to 14].
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String> log = List.of("tube to 14", "pads to 5", "chain to 40");
System.out.println(newestFirst(log));
}
static List<String> newestFirst(List<String> log) {
Deque<String> stack = new ArrayDeque<>();
List<String> out = new ArrayList<>();
for (String entry : log) out.add(entry);
return out;
}
}Common mistakes
MistakeUsing the legacy Stack class.
InsteadUse a Deque such as ArrayDeque with push, pop and peek.
MistakeCalling remove or pop on a queue or stack that might be empty.
InsteadCheck isEmpty first, or use poll, which returns null when empty.
MistakeAdding null to an ArrayDeque.
InsteadArrayDeque refuses null because poll and peek use null to mean empty; use a placeholder value or Optional.
MistakeMixing up which end push and offer use.
Insteadpush adds at the front, the top of the stack; offer adds at the tail of the queue.
MistakeShifting an array to remove from the front of a queue.
InsteadUse ArrayDeque, whose circular buffer removes from the head in O(1).
Summary and key terms
- A queue serves items first in, first out, and a stack serves them last in, first out.
- Java's Queue interface offers offer, poll and peek, which return false or null, and add, remove and element, which throw exceptions.
- The legacy Stack class should not be used; a Deque provides push, pop and peek.
- A Deque can add, remove and inspect both ends with methods such as offerFirst, pollLast and peekFirst.
- ArrayDeque, the usual implementation, is a circular buffer: the head and tail indexes move round an array and wrap to 0, so both ends are O(1) with no shifting.
- ArrayDeque refuses null elements.
- Stacks suit problems that match things in reverse, such as balanced brackets and undo.
- PriorityQueue serves by priority instead, and bounded or thread-safe queues live in java.util.concurrent.
- Queue
- A collection that serves elements first in, first out.
- Stack
- A collection that serves elements last in, first out.
- FIFO
- First in, first out: the oldest element leaves first.
- LIFO
- Last in, first out: the newest element leaves first.
- Head
- The end of a queue from which elements leave.
- Tail
- The end of a queue at which elements join.
- push and pop
- The stack operations that add to and remove from the top.
- offer and poll
- The queue operations that add at the tail and remove from the head, returning false or null on trouble.
- Deque
- A double-ended queue that works at both ends.
- Circular buffer
- An array used as a ring, with head and tail indexes that wrap around.
- Bounded queue
- A queue with a fixed maximum size.
Practice problems
Work each problem on paper first, then reveal the answer to check.
Which discipline does a repair rack served in arrival order follow?
Show answer
First in, first out: a queue.
What should you use instead of java.util.Stack?
Show answer
A Deque, usually ArrayDeque, with push, pop and peek.
What does poll return on an empty queue?
Show answer
null.
Why does ArrayDeque refuse null?
Show answer
Because poll and peek return null to mean the deque is empty.
How does a circular buffer remove from the front without shifting?
Show answer
It moves the head index forward and wraps it around the array.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.