PHASE 9Intermediate ~29 min· topic 7 of 13

Topic 9.7

Queue, Deque and ArrayDeque

In one line

A Queue hands elements out in arrival order (first in, first out); a Deque works at both ends, so it can also be a stack (last in, first out). ArrayDeque, a circular array, is the fastest general implementation of both and replaces Stack and, for queues, LinkedList.

Think of it like this

The line at a bus stop is a queue: the first person to arrive is the first to board. A stack of plates in a canteen is a stack: you put a clean plate on top and take from the top, so the last plate in is the first out. A deque is like a train carriage with doors at both ends: people can get on and off at either end.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Queue: A collection where elements leave in the order they arrived: first in, first out (FIFO).
Stack: A collection where the last element added is the first one removed: last in, first out (LIFO).
Deque: A double-ended queue, pronounced "deck": add and remove at both the front and the back.
Head and tail: The front of the queue (where elements leave) and the back (where they join).
Circular array: An array used as a ring: after the last slot, the next position is slot 0 again.
Wrap around: Moving an index past the end of the array back to the start, usually with % length or a mask.
FIFO and LIFO: First in, first out (queues) and last in, first out (stacks).

Step by step

01Two flavours of every operation

Why two sets of methods? Some queues have a capacity limit (an ArrayBlockingQueue of 100, say). For them, failing to add is normal, so offer returns false. For an unbounded queue, add and offer behave the same.

On an empty queue, remove() and element() throw NoSuchElementException; poll() and peek() return null. Pick one family and use it consistently.

queue-methods.txtwhole filetext

              throws exception    returns special value
insert        add(e)              offer(e)        -> false if full
remove head   remove()            poll()          -> null if empty
look at head  element()           peek()          -> null if empty

02One Deque, three roles

A Deque is a queue, a stack, or both at once, depending on which ends you use. As a queue: offer adds at the tail, poll takes from the head. As a stack: push and pop both work at the head.

Mixing roles on one object is legal but confusing. Name the variable for the role (queue, stack, window) and use only that role's methods.

One Deque, three rolesdiagram

Rendering diagram…

03Inside ArrayDeque: a ring of slots

Picture an array of 8 slots with head = 6 and tail = 2. The elements live in slots 6, 7, 0 and 1: the queue has wrapped around the end. offerLast(x) writes slot 2 and moves tail to 3. pollFirst() reads slot 6, sets it to null and moves head to 7. offerFirst(y) moves head back to 5 and writes there.

Nothing is ever shifted, which is why ArrayDeque beats ArrayList.remove(0) (O(n)) for queues. When the ring fills, it allocates a bigger array and copies the elements so they're contiguous again.

Inside ArrayDeque: a ring of slotsdiagram

Rendering diagram…

04Why not LinkedList or Stack?

LinkedList allocates a node per element (Topic 9.3): more memory, more garbage, worse cache behaviour. ArrayDeque stores references in one array.

Stack synchronises every call and inherits Vector's indexed methods. stack.get(0) returns the bottom element and stack.add(0, x) inserts under everything: operations no stack should have. ArrayDeque has neither problem.

05Iteration order differs between Stack and ArrayDeque

Stack pushes onto the end of its Vector, so iterating it (or printing it) goes bottom to top. ArrayDeque.push adds at the head, so iterating goes top to bottom, which is the order pop would return. Code that prints or streams a stack changes its output when you migrate, so check tests when replacing Stack.

Main.javawhole filejava

Stack<Integer> old = new Stack<>();
Deque<Integer> modern = new ArrayDeque<>();
for (int i = 1; i <= 3; i++) { old.push(i); modern.push(i); }
System.out.println(old);      // [1, 2, 3]  bottom first
System.out.println(modern);   // [3, 2, 1]  top first

06The monotonic deque

To get the maximum of every window of k elements in an array, keep a deque of indexes whose values are decreasing from head to tail. For each new element: pop indexes from the tail while their values are ≤ the new value (they can never be a maximum again), add the new index at the tail, and pop the head if it has slid out of the window. The head is always the current window's maximum.

Each index is added and removed at most once, so the whole thing is O(n), compared with O(n·k) for scanning every window. It only works because a deque allows O(1) removal at both ends.

Try it yourself

1
Mix the roles
In the stack example, call undo.offer("italic") before the pops. Predict where it goes and what pop returns. (It joins the tail, so pop still returns bold; the deque is now being used as two things at once.)
2
Grow the ring
Change RingQueue.offer so that when it's full it copies the elements into an array twice as big, starting at index 0, and resets head and tail. Predict the state line after offering 50 to the full queue.
3
Window minimum
Change the sliding-window code to compute the minimum of each window. Which single comparison flips? Predict the k=3 output for the same array ([-1, -3, -3, -3, 3, 3]).

Code & diagrams

Queue methods: offer, poll, peek vs add, remove, element New tab

Expected output

queue: [asha, ravi, meera], next up: asha
served asha
served ravi
served meera
poll on empty: null
peek on empty: null
element on empty: NoSuchElementException

ArrayDeque as a stack, and how Stack differs New tab

Expected output

top: bold
undo bold, then type b
left: [type a]
Stack prints bottom-first:     [1, 2, 3]
ArrayDeque prints top-first:   [3, 2, 1]
both pop 3 and 3
Stack after add(0, 99): [99, 1, 2] (stack discipline broken)

Build a circular buffer and watch it wrap New tab

head == tail means either empty or full, which is why the size counter is needed. ArrayDeque avoids the ambiguity by growing before it fills completely.

Expected output

full:      head=0 tail=0 size=4, offer 50? false
poll 10, poll 20 -> head=2 tail=0 size=2
wrapped:   head=2 tail=2 size=4
drain: 30 40 50 60 -> head=2 tail=2 size=0

Sliding window maximum with a monotonic deque New tab

Each index enters and leaves the deque at most once, so this is O(n) however big k is.

Expected output

window max (k=3): [3, 3, 5, 5, 6, 7]
window max (k=1): [1, 3, -1, -3, 5, 3, 6, 7]
window max (k=8): [7]

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Offer null to an ArrayDeque

Run Deque<String> tasks = new ArrayDeque<>(); tasks.offer("email"); tasks.offer(null);.

terminal

$ java Main

── what you'll see ──

Exception in thread "main" java.lang.NullPointerException

at java.base/java.util.ArrayDeque.addLast(ArrayDeque.java:302)

at java.base/java.util.ArrayDeque.offerLast(ArrayDeque.java:351)

at java.base/java.util.ArrayDeque.offer(ArrayDeque.java:507)

at Main.main(Main.java:7)

Break #2

Pop an empty stack

Run Deque<Integer> stack = new ArrayDeque<>(); int top = stack.pop();.

terminal

$ java Main

── what you'll see ──

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:6)

Myth vs fact

Myth

Use Stack for stacks; it's in the name.

Fact

Stack is a synchronised Vector subclass that leaks list methods. The JDK's own Javadoc for Stack recommends Deque instead: Deque<Integer> stack = new ArrayDeque<>();.

Myth

LinkedList is the natural Queue implementation.

Fact

ArrayDeque is faster and smaller. LinkedList is only needed for null elements or when you also need List methods.

Myth

An ArrayDeque has a fixed capacity.

Fact

It grows automatically. The capacity argument to its constructor is only a sizing hint. For a bounded queue, use ArrayBlockingQueue (Topic 13.8) or write a ring buffer.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Since JDK 9, ArrayDeque no longer requires a power-of-two capacity. It grows by oldCapacity + 2 while small (under 64) and by 50% after, and always keeps at least one slot empty so that head == tail can only mean empty.
▸
ArrayDeque.removeFirstOccurrence, contains and remove(Object) are O(n), and removing from the middle shifts the shorter side. If you need frequent removal of arbitrary elements, a queue is the wrong structure.
▸
For multi-threaded queues, ConcurrentLinkedQueue and ConcurrentLinkedDeque are lock-free; ArrayBlockingQueue, LinkedBlockingQueue and LinkedBlockingDeque block producers when full and consumers when empty, which is how thread pools hold their work queues (Topics 13.6 and 13.8).
▸
In 0-1 BFS (edge weights 0 or 1), a deque replaces Dijkstra's priority queue: push 0-weight neighbours to the front and 1-weight neighbours to the back, giving O(V + E) shortest paths (/dsa/shortest-path).

Remember this

1
Queue<E> (Java 5) extends Collection with a waiting-line API. Each operation comes in two flavours: throwing methods add, remove and element throw an exception when they can't succeed (full or empty queue), and special-value methods offer, poll and peek return false or null instead. For ordinary unbounded queues, offer/poll/peek are the idiomatic choice.
2
Deque<E> ("deck", Java 6) extends Queue with both-end versions: offerFirst/offerLast, pollFirst/pollLast, peekFirst/peekLast, and throwing addFirst, removeLast, getFirst and so on. Used as a queue, you add at the tail and remove at the head (offer = offerLast, poll = pollFirst). Used as a stack, push = addFirst, pop = removeFirst and peek = peekFirst: everything happens at the head.
3
**ArrayDeque stores elements in a circular array** with two indexes: head (the first element) and tail (the slot where the next element goes at the end). Adding at the tail writes elements[tail] and advances tail; adding at the head moves head back one slot. Both indexes wrap around the end of the array, so nothing is ever shifted. All end operations are O(1) (amortised, because the array grows when full).
4
ArrayDeque **rejects null** (a NullPointerException on insert), which keeps poll() returning null unambiguous: it always means "empty". It's not thread-safe, has no capacity limit, and grows by roughly doubling while small and by 50% once larger. Its Javadoc says it's "likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue".
5
**Stack** is a legacy class from Java 1.0 that extends Vector: every method is synchronized, and because it is a Vector it exposes get(i), add(i, e) and remove(i), letting anyone break the stack discipline. It also iterates from the bottom up, while an ArrayDeque used as a stack iterates top-first. Declare stacks as Deque<T> stack = new ArrayDeque<>();.
6
Queues and deques power classic algorithms: breadth-first search uses a queue (/dsa/bfs), bracket matching and undo use a stack (/dsa/stack), and the monotonic deque gives the maximum of every sliding window in O(n) (/dsa/queue-deque). For priority order instead of arrival order, use PriorityQueue (Topic 9.8). For producer-consumer handoff between threads, use a BlockingQueue (Topic 13.8).

Explain it without notes

What is the difference between offer/poll/peek and add/remove/element?

How does ArrayDeque achieve O(1) operations at both ends?

Why should you use ArrayDeque instead of Stack and LinkedList?

Explain the monotonic deque technique for sliding window maximum and its complexity.

Practice

Simulate a printer queue: jobs "report", "photo", "invoice" arrive; print them in arrival order using an ArrayDeque as a queue, printing "printing <job>" for each.

Reverse the words of "java is fun" using an ArrayDeque as a stack.

Implement BFS on this graph and print the visiting order from node 0: edges 0-1, 0-2, 1-3, 2-3, 3-4 (an adjacency list of List<List<Integer>>).

Trade-offs

↔
ArrayDeque is the fastest single-threaded queue and stack, but it rejects null, isn't thread-safe and has no capacity bound. Each of those needs a different class.
↔
The throwing methods make a bug (popping an empty stack) loud; the special-value methods make normal emptiness cheap to handle. Choosing the wrong family either hides bugs or litters code with try/catch.
↔
A queue gives arrival order; when urgency matters more than arrival, a PriorityQueue (Topic 9.8) costs O(log n) per operation instead of O(1).

Done when you can

Done when you can list the throwing and special-value queue methods and when each fails.
Done when you can use one Deque as a queue and as a stack with the right methods.
Done when you can explain ArrayDeque's circular array and wrap-around.
Done when you replace Stack with ArrayDeque and know the iteration-order difference.
Done when you can write the monotonic-deque sliding window maximum.

Command Palette

Words you'll meet

Step by step

01Two flavours of every operation

02One Deque, three roles

03Inside ArrayDeque: a ring of slots

04Why not LinkedList or Stack?

05Iteration order differs between Stack and ArrayDeque

06The monotonic deque

Try it yourself

Mix the roles

Grow the ring

Window minimum

Code & diagrams

Break it on purpose

Offer null to an ArrayDeque

Pop an empty stack

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can