Queue, Deque and Stack

Q: What are the most common mistakes with Queue, Deque and Stack?

Using Stack or LinkedList for new code. Mixing the head and tail methods and getting the wrong order. Putting null into an ArrayDeque.

A queue is first-in-first-out (a line at the shop), a stack is last-in-first-out (a pile of plates).

🔎 Unravel this example Prerequisites (1)

Learn these first

Collections: List, Set, Map

At a glance

Mental model

Queue: people waiting at a counter, served in arrival order.

What happens, in order

1Queue: offer(x) adds at the back, poll() removes from the front (null if empty), peek() looks at the frontThe throwing twins are add, remove and element.
2Stack: push(x), pop() and peek() act on the same endDeque<Integer> stack = new ArrayDeque<>(); replaces Stack.
3A Deque (double-ended queue) can add and remove at both ends: addFirst, addLast, pollFirst, pollLast
4Classic uses: stack for matching brackets, undo history, depth-first search and expression evaluation; queue for breadth-first search, task buffers and rate windows

Remember

java.util.Stack extends Vector, so every call is synchronized and it exposes list methods such as get(i) and insertElementAt
poll() and peek() return null on an empty queue, while remove() and pop() throw NoSuchElementException
ArrayDeque is a circular array with head and tail indices that doubles its size when full, so add and remove at both ends are O(1) amortised without allocating a node per element

Watch out

Using Stack or LinkedList for new codeMixing the head and tail methods and getting the wrong orderPutting null into an ArrayDeque

Example (highlighted lines explain it)

import java.util.*;public class Brackets {  static boolean balanced(String s) {    Deque<Character> stack = new ArrayDeque<>();    for (char c : s.toCharArray()) {      if (c == '(' || c == '[') stack.push(c);      else if (c == ')' || c == ']') {        if (stack.isEmpty()) return false;        char open = stack.pop();        if ((c == ')' && open != '(') || (c == ']' && open != '[')) return false;      }    }    return stack.isEmpty();  }}

line 4 uses Deque, the core of Queue, Deque and Stack
line 6 uses push, the core of Queue, Deque and Stack
line 9 uses pop, the core of Queue, Deque and Stack

Read the full explanation (about 1 min)

A queue is first-in-first-out (a line at the shop), a stack is last-in-first-out (a pile of plates). In Java use ArrayDeque for both; the old Stack class is legacy.

A mental model

Queue: people waiting at a counter, served in arrival order. Stack: a pile of plates, where you only take the one on top, the last one placed.

How it works

Queue: offer(x) adds at the back, poll() removes from the front (null if empty), peek() looks at the front. The throwing twins are add, remove and element.

Stack: push(x), pop() and peek() act on the same end. Deque<Integer> stack = new ArrayDeque<>(); replaces Stack.

A Deque (double-ended queue) can add and remove at both ends: addFirst, addLast, pollFirst, pollLast.

Classic uses: stack for matching brackets, undo history, depth-first search and expression evaluation; queue for breadth-first search, task buffers and rate windows.

Going deeper

java.util.Stack extends Vector, so every call is synchronized and it exposes list methods such as get(i) and insertElementAt. ArrayDeque is faster and has a cleaner API. It does not allow null elements.

poll() and peek() return null on an empty queue, while remove() and pop() throw NoSuchElementException. Pick the style on purpose.

For thread hand-off use a BlockingQueue; ArrayDeque is not thread safe.

Under the hood

ArrayDeque is a circular array with head and tail indices that doubles its size when full, so add and remove at both ends are O(1) amortised without allocating a node per element.

Common mistakes

Using Stack or LinkedList for new code.
Mixing the head and tail methods and getting the wrong order.
Putting null into an ArrayDeque.

How Unravel recognises it

When you paste code, Unravel looks for these signs of queue, deque and stack. Spotting them yourself is a good habit when you read unfamiliar code:

Types: Deque ArrayDeque Stack
Method calls: push() pop() offerFirst() offerLast() pollFirst() pollLast() peekFirst() peekLast() removeLast() addLast()
Created with new: ArrayDeque

Part of a learning path

Collections in depth · previous: TreeMap, TreeSet and sorted collections · next: PriorityQueue and heaps

Related concepts

PriorityQueue and heapsJava language Concurrent collectionsConcurrency Building your own stack or queueJava language

Builds on this

Graphs: BFS and DFSJava language

Frequently asked questions

What is Queue, Deque and Stack?

A queue is first-in-first-out (a line at the shop), a stack is last-in-first-out (a pile of plates). In Java use ArrayDeque for both; the old Stack class is legacy.

What are the most common mistakes with Queue, Deque and Stack?

Using Stack or LinkedList for new code. Mixing the head and tail methods and getting the wrong order. Putting null into an ArrayDeque.

How can I see Queue, Deque and Stack in real code?

Paste your own Java into Unravel and it will point out where queue, deque and stack appears, explain how it works at the detail level you choose, and draw the flow of the code around it.