BrewlearnStacks & queues in practice in Java
Balanced brackets, BFS, undo — using ArrayDeque.
Plates and lines
A stack is LIFO: last in, first out, like a pile of plates. A queue is FIFO: first in, first out, like the line at a coffee shop. In Java, **ArrayDeque** is the go-to implementation for both.
Deque<Character> st = new ArrayDeque<>();
st.push('(');
st.push('[');
st.pop(); // '[' (last in, first out)One deque, two ends
push, pop and peek work at the head. offer adds at the tail and poll removes from the head. So push/pop gives a stack and offer/poll gives a queue, both O(1). One more rule: ArrayDeque doesn't allow null elements.
Deque<Integer> d = new ArrayDeque<>();
d.push(1); // head: [1]
d.push(2); // head: [2, 1]
d.offer(9); // tail: [2, 1, 9]
d.poll(); // removes 2 from the headBoth ends at once
What does this print?
Deque<String> d = new ArrayDeque<>();
d.offer("a"); d.offer("b"); d.push("c");
System.out.println(d);
System.out.println(d.poll() + d.pop());
System.out.println(d);[c, a, b] ca [b][a, b, c] ab [c][c, a, b] cb [a]
Show the answer
offer adds a, then b at the tail: [a, b]. push puts c at the head: [c, a, b]. poll takes the head (c), then pop takes the new head (a). Only b is left.
Matching brackets
For each opener, push the closer you expect. For each closer, pop and compare. In "([)]" the top of the stack is ']' when ')' arrives, so the brackets are crossed: the most recent unclosed bracket must close first. At the end the stack must be empty.
for (char c : s.toCharArray()) {
if (c == '(') st.push(')');
else if (c == '[') st.push(']');
else if (st.isEmpty() || st.pop() != c)
ok = false;
}
boolean valid = ok && st.isEmpty();Nothing wrong... yet
What does this print?
String s = "(()";
var st = new ArrayDeque<Character>();
boolean ok = true;
for (char c : s.toCharArray()) {
if (c == '(') st.push(')');
else if (st.isEmpty() || st.pop() != c)
ok = false;
}
System.out.println(ok + " " + st.size());true 1false 0true 0
Show the answer
No closer ever mismatched, so ok stays true. But one '(' was never closed, so 1 item is left on the stack. That's why a full check needs ok && st.isEmpty().
Legacy and slow choices
java.util.Stack extends Vector, so every call is synchronized and it exposes index-based methods; the docs recommend ArrayDeque instead. And don't fake a queue with ArrayList.add(0, x) or remove(0): shifting the array makes those O(n).
Picking the structure
Undo history: stack (LIFO). BFS frontier and print jobs in arrival order: queue with offer/poll (FIFO). Always serve the most urgent job: PriorityQueue. Add and remove at both ends: Deque. These choices show up daily in schedulers, parsers and editors.
Key takeaways
- Deque<Integer> st = new ArrayDeque<>() for a stack
- push/pop work at the head; offer adds at the tail
- ArrayDeque doesn't allow null elements
- Brackets and undo → stack; BFS and job lines → queue
💡 A stack is a pile of plates; a queue is the line at a coffee shop.
The JVM itself is a stack machine: bytecode like iadd pops two values off an operand stack and pushes the result back.
Practice questions
What does this print?
Deque<Integer> d = new ArrayDeque<>();
d.push(1); d.push(2); d.push(3);
System.out.println(d.pop() + " " + d.peek());
d.offer(9);
System.out.println(d);- 1 2 [2, 3, 9]
- 3 2 [9, 2, 1]
- 3 3 [2, 1, 9]
- 3 2 [2, 1, 9]
Check your answer
3 2 [2, 1, 9]. push adds at the head, so the deque is [3, 2, 1]. pop removes 3, and peek shows 2. offer adds at the tail, giving [2, 1, 9].
What does this print?
String s = "([)]";
var st = new ArrayDeque<Character>();
boolean ok = true;
for (char c : s.toCharArray()) {
if (c == '(') st.push(')');
else if (c == '[') st.push(']');
else if (st.isEmpty() || st.pop() != c)
ok = false;
}
System.out.println(ok && st.isEmpty());- true
- false
- Throws NoSuchElementException
Check your answer
false. Each opener pushes the closer it expects. When ')' arrives, the top of the stack is ']', so the brackets are crossed and ok becomes false.