Stack & Deque
IntermediateUse ArrayDeque as your go-to Stack and Queue — faster than the legacy Stack class and more memory-efficient than LinkedList.
Overview
Java has a legacy Stack class (extends Vector — synchronized, slow) and the modern Deque interface with ArrayDeque as the preferred implementation. A Deque (double-ended queue) supports O(1) insertion and removal at both ends, making it perfect for stacks (LIFO) and queues (FIFO). ArrayDeque is backed by a resizable circular array — no node allocation overhead like LinkedList, better cache locality, and typically 2–3× faster in benchmarks. Always prefer Deque<T> stack = new ArrayDeque<>() over new Stack<>().
ArrayDeque as Stack & Queue
Deque interface provides two naming conventions:
Stack (LIFO): push/pop/peek — these are on the head (front) Queue (FIFO): offer/poll/peek — offer adds at tail, poll removes from head
Both sets of methods are O(1). ArrayDeque does not allow null elements (unlike LinkedList). It grows by doubling when full.
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
public class ArrayDequeDemo {
public static void main(String[] args) {
// ── As a STACK (LIFO) ─────────────────────────────────────────
Deque<String> stack = new ArrayDeque<>();
stack.push("first"); // addFirst()
stack.push("second");
stack.push("third");
System.out.println(stack.peek()); // third — view top, no remove
System.out.println(stack.pop()); // third — remove top
System.out.println(stack.pop()); // second
System.out.println(stack); // [first]
// ── As a QUEUE (FIFO) ─────────────────────────────────────────
Queue<String> queue = new ArrayDeque<>();
queue.offer("first"); // addLast()
queue.offer("second");
queue.offer("third");
System.out.println(queue.peek()); // first — view head, no remove
System.out.println(queue.poll()); // first — remove head
System.out.println(queue.poll()); // second
System.out.println(queue); // [third]
// ── As a DEQUE (both ends) ────────────────────────────────────
Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(2); // [2]
deque.offerFirst(1); // [1, 2]
deque.offerLast(3); // [1, 2, 3]
deque.offerLast(4); // [1, 2, 3, 4]
System.out.println(deque.peekFirst()); // 1
System.out.println(deque.peekLast()); // 4
System.out.println(deque.pollFirst()); // 1
System.out.println(deque.pollLast()); // 4
System.out.println(deque); // [2, 3]
// Null not allowed in ArrayDeque
try {
deque.offer(null); // throws NullPointerException
} catch (NullPointerException e) {
System.out.println("No nulls in ArrayDeque");
}
}
}Classic Stack Problems
Stacks are the canonical data structure for: • Balanced parentheses checking • Expression evaluation / operator precedence • Undo/redo functionality • DFS traversal (iterative) • Monotonic stack problems (next greater element)
All of these use ArrayDeque as the stack implementation in modern Java.
import java.util.ArrayDeque;
import java.util.Deque;
public class StackProblems {
// 1. Balanced parentheses — O(n)
static boolean isBalanced(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 top = stack.pop();
if (c == ')' && top != '(') return false;
if (c == ']' && top != '[') return false;
if (c == '}' && top != '{') return false;
}
}
return stack.isEmpty();
}
// 2. Next greater element — O(n) using monotonic stack
static int[] nextGreater(int[] nums) {
int n = nums.length;
int[] result = new int[n];
java.util.Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // stores indices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}
// 3. Evaluate Reverse Polish Notation — O(n)
static int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String t : tokens) {
switch (t) {
case "+" -> stack.push(stack.pop() + stack.pop());
case "*" -> stack.push(stack.pop() * stack.pop());
case "-" -> { int b = stack.pop(), a = stack.pop(); stack.push(a - b); }
case "/" -> { int b = stack.pop(), a = stack.pop(); stack.push(a / b); }
default -> stack.push(Integer.parseInt(t));
}
}
return stack.pop();
}
public static void main(String[] args) {
System.out.println(isBalanced("({[]})")); // true
System.out.println(isBalanced("([)]")); // false
System.out.println(java.util.Arrays.toString(
nextGreater(new int[]{2, 1, 2, 4, 3})));
// [4, 2, 4, -1, -1]
System.out.println(evalRPN(new String[]{"2","1","+","3","*"})); // 9
}
}Deque Method Reference Card & Legacy Stack
The Deque interface has two sets of methods for each operation — one throws exceptions on failure, one returns a special value:
Throws exception Returns null/false Insert head: addFirst(e) offerFirst(e) Remove head: removeFirst() pollFirst() Examine head: getFirst() peekFirst() Insert tail: addLast(e) offerLast(e) Remove tail: removeLast() pollLast() Examine tail: getLast() peekLast()
For queues: offer/poll/peek are preferred (no exceptions). For stacks: push/pop/peek.
The legacy Stack class extends Vector (synchronized array list) — never use it in new code.
import java.util.*;
public class DequeReference {
public static void main(String[] args) {
Deque<String> dq = new ArrayDeque<>();
dq.offerLast("a");
dq.offerLast("b");
dq.offerLast("c");
// Exception-throwing variants
dq.addFirst("start"); // throws if capacity restricted
System.out.println(dq.getFirst()); // start — throws NoSuchElementException if empty
System.out.println(dq.getLast()); // c
// Value-returning variants (prefer these)
System.out.println(dq.peekFirst()); // start — null if empty
System.out.println(dq.pollFirst()); // start — null if empty
System.out.println(dq.pollLast()); // c — null if empty
System.out.println(dq); // [a, b]
// Legacy Stack — avoid in new code
Stack<String> legacyStack = new Stack<>();
legacyStack.push("x");
legacyStack.push("y");
System.out.println(legacyStack.peek()); // y
System.out.println(legacyStack.pop()); // y
// Stack is synchronized (extends Vector) — slow; use ArrayDeque instead
// Iterating Deque — iterates from head to tail
Deque<Integer> nums = new ArrayDeque<>(List.of(1, 2, 3, 4, 5));
for (int n : nums) System.out.print(n + " "); // 1 2 3 4 5
System.out.println();
// descendingIterator — tail to head
Iterator<Integer> desc = nums.descendingIterator();
while (desc.hasNext()) System.out.print(desc.next() + " "); // 5 4 3 2 1
}
}Interactive Visualization
Key Points to Remember
- Always use ArrayDeque instead of the legacy Stack class — faster, not synchronized
- ArrayDeque is a circular resizable array — O(1) amortised at both ends, better cache locality than LinkedList
- ArrayDeque does not permit null elements; LinkedList does
- Stack API: push/pop/peek (head); Queue API: offer/poll/peek (tail in, head out)
- offerXxx/pollXxx/peekXxx return null on empty; addXxx/removeXxx/getXxx throw NoSuchElementException
- Monotonic stack (ArrayDeque) solves Next Greater Element, Largest Rectangle, and similar in O(n)
Practice Stack & Deque in the Playground
Run and modify code directly in your browser - no setup needed.
Interview Questions
Sign in to ask AriaWhy should you use ArrayDeque instead of Stack in Java?
What is the difference between offer() and add() in a Queue?
Implement a stack that supports push, pop, and getMin in O(1)
How would you check balanced parentheses using a stack?
What is a monotonic stack? Give a problem where it applies.
Ask Aria about Stack & Deque
Your personal AI tutor — ask anything about this concept