Java 45: ArrayDeque — Stack, Queue & the Deque API
easy⏱ 5 mincoursejava
Two method families: throw vs return
Deque exposes paired operations: throwing (addFirst/addLast/removeFirst/removeLast/getFirst) that raise on empty/full, and value-returning (offerFirst/offerLast/pollFirst/pollLast/peekFirst) that return false/null instead. Pick throwing when emptiness is a bug; pick the offer/poll/peek family when emptiness is a normal control-flow case.
Deque<Integer> d = new ArrayDeque<>();
d.offerLast(1); d.offerLast(2); // queue: enqueue at tail
d.pollFirst(); // -> 1 (FIFO)
d.push(9); // stack: push == addFirst
d.pop(); // -> 9 (LIFO)
Stack via push/pop, Queue via offer/poll
As a stack: push = addFirst, pop = removeFirst, peek = peekFirst — LIFO at the head. As a queue: offer (= offerLast) enqueues at the tail, poll (= pollFirst) dequeues at the head — FIFO. Same object, chosen by which methods you call.
Why not Stack/Vector?
java.util.Stack extends Vector — every method is synchronized (pointless single-thread overhead) and it iterates in the wrong order for a stack (bottom-to-top). ArrayDeque is unsynchronized, contiguous (cache-friendly), grows amortized O(1), and forbids null elements (so null from poll unambiguously means empty). It's the default for both stacks and non-blocking queues.
One deque, three roles
Implement ArrayDeque<T> with addFirst/addLast/pollFirst/pollLast/peekFirst/peekLast/size. (1) Use it as a stack to reverse [1,2,3,4,5]. (2) Use it as a FIFO queue to process the same list in order. (3) Use it as a sliding window: maintain the max of each window of size 3 over [4,1,7,2,9,3] using a monotonic deque. Print all three results.
Monotonic deque = sliding window max
Sliding-window-maximum in O(n) keeps indices in a deque whose values are decreasing front-to-back: before pushing, pop smaller values off the tail; pop the front when it leaves the window. The front always holds the current window's max. This deque trick is a frequent interview question.
Quiz: ArrayDeque vs LinkedList as a queue
Which is the better Queue? ArrayDeque in almost every case — contiguous memory means fewer cache misses and no per-node object overhead. LinkedList only wins when you need to remove from the middle by iterator, which queues never do. For BFS, work queues, and stacks, reach for ArrayDeque.