Queues & Deques

First in, first out — your printer's job queue, and the engine behind BFS, ring buffers and sliding windows.

beginner~60 min6 simulations10 problems

▶ guided lesson ⚡ 1-minute summary ↻ 15 recall cards

before this: Arrays & Strings · Linked Lists · Stacks · Big-O

Section

01 · why it exists

Why this exists, and the weight it carries

since1909–1917

Queue (FIFO)

Agner Krarup Erlang, Copenhagen Telephone Company

Nobody invented "first come, first served" — waiting lines are older than computers, and the FIFO queue in code has no single inventor. What has a clear start is the maths of queues. In 1909 Erlang, an engineer at the Copenhagen Telephone Company, showed that calls made at random follow a Poisson distribution. His 1917 paper gave formulas for lost calls and waiting time, and telephone companies in many countries adopted them. That field, queueing theory, is still how engineers size server pools, call centres and network buffers.

the problem it solvedHow many lines a telephone exchange needs so that calls rarely wait or get lost — sizing any system that serves requests in arrival order.

its jobs today

Operating systems keep ready threads and pending disk or network requests in queues; a print spooler sends jobs to the printer in the order they arrived.
Web servers and message brokers (Kafka, RabbitMQ, Amazon SQS) hold a burst of requests in line, so the backend works through it instead of falling over.
BFS explores a graph or a game map level by level with a queue — the first path that reaches a cell is a shortest one.

the weight it carries

Illustrative: a Tatkal-style burst of 1 lakh (100,000) booking requests reaches a server that handles 5,000 per second. With a FIFO queue the burst drains in 100,000 ÷ 5,000 = 20 seconds, in arrival order. With ArrayList.remove(0) as dequeue, the shifts alone add up to 99,999 + 99,998 + … + 1 ≈ 5·10⁹ element moves.

without it

Bursts of work would be dropped or served in random order — no fairness for print jobs or bookings — and BFS would stop finding shortest paths.

when · why · how

when: Things must be handled in the order they arrived: tasks, requests, messages, a BFS frontier, a sliding time window.
why: Both ends are O(1) — offer at the rear, poll at the front — so n items cost O(n) in total. A list that shifts on every removal turns the same work into O(n²).
how: Queue<Integer> q = new ArrayDeque<>(); then offer, poll, peek, isEmpty. Declare the interface type; pick ArrayDeque unless you need null elements or thread safety.

since?

Circular buffer (ring buffer)

Ring buffers grew out of early I/O and operating-system practice. We couldn't find a reliable first inventor or date, so we don't name one.

its jobs today

Keyboard, audio and network drivers pass data between hardware and software through fixed-size ring buffers — nothing is allocated while they run.
Logs and monitors keep "the last N events" in a ring: the newest entry simply overwrites the oldest.
ArrayDeque is a ring buffer that grows when full; ArrayBlockingQueue is a fixed ring guarded by one lock that producer and consumer threads share.

the weight it carries

Illustrative: audio at 48,000 samples per second, buffered for half a second, needs a ring of 48,000 × 0.5 = 24,000 slots — allocated once. Each sample in or out is one array access and one % 24,000. An array that shifts instead would move up to 23,999 samples for every sample it plays.

without it

Every dequeue would either shift the whole array (O(n)) or waste the freed front slots forever; fixed-memory buffers in drivers and embedded code would not work.

when · why · how

when: A FIFO with a known maximum size, or "keep only the last k items": LC 622, rate limiters, streaming buffers.
why: Indices wrap with % capacity, so nothing ever shifts: every operation is O(1) and memory is fixed at O(capacity). The price: a full ring must reject (or overwrite) new items.
how: An int[] data, an int head and an int size. Next free slot = (head + size) % data.length; rear = (head + size − 1) % data.length; dequeue = head = (head + 1) % data.length.

since2006 (Java 6)

Deque and Java's ArrayDeque

Josh Bloch & Doug Lea (ArrayDeque); the name "deque": E. J. Schweppe, as credited by Knuth

A deque — say "deck" — is a queue that is open at both ends. Knuth's The Art of Computer Programming, Vol. 1, §2.2.1 teaches stacks, queues and deques together; reference works that cite it say Knuth credits the name to E. J. Schweppe. Java added the Deque interface and ArrayDeque in Java 6; the class source lists Josh Bloch and Doug Lea as authors. Its Javadoc says it is likely faster than Stack when used as a stack and faster than LinkedList when used as a queue.

the problem it solvedOne structure that can be a stack, a queue, or both at once, with O(1) work at either end and no node object per element.

its jobs today

The default stack and queue in Java code: push/pop/peek for a stack, offer/poll/peek for a queue — one class, both ends O(1).
Work-stealing thread pools: ForkJoinPool gives each worker a deque — the owner pushes and pops at one end while idle workers steal from the other.
Bounded history (recent searches, undo with a limit): add new items at one end, drop the oldest from the other.

the weight it carries

Illustrative, on a typical 64-bit JVM with compressed references: 10 lakh (1,000,000) elements in a LinkedList need 10⁶ node objects of about 24 bytes (12-byte header + item, next, prev) ≈ 24 MB of nodes. ArrayDeque keeps 10⁶ references in one array ≈ 4 MB — about 6× less, and laid out side by side for the CPU cache.

without it

You'd choose between the legacy synchronized Stack and a node-per-element LinkedList — slower for both jobs.

when · why · how

when: You need a stack, a queue, or both ends at once: sliding windows, palindrome checks, bounded history, 0-1 BFS.
why: Every end operation is O(1) (amortized when the array grows) on one compact array. It rejects null because null is how poll/peek say "empty".
how: Deque<Integer> dq = new ArrayDeque<>(); — offerFirst/offerLast, pollFirst/pollLast, peekFirst/peekLast; as a stack, push/pop/peek all work at the front.

since?

Monotonic deque

A folklore technique passed on through algorithm courses and contest write-ups. We couldn't verify a first publication or inventor, so we name none.

its jobs today

Sliding-window max or min over a stream — say the peak CPU reading of the last 60 seconds on a monitoring dashboard — at amortized O(1) per new reading.
Speeding up dynamic programming whose step needs "the best of the last k states" (LC 1696 Jump Game VI, LC 1425) from O(n·k) to O(n).
Shortest subarray with sum ≥ k when values can be negative (LC 862), where a two-pointer window gives wrong answers.

the weight it carries

Illustrative: 10⁵ readings, window k = 10⁴. Rescanning every window: (10⁵ − 10⁴ + 1) × 10⁴ = 900,010,000 ≈ 9·10⁸ comparisons. Monotonic deque: each index is pushed once and popped at most once — at most 2 × 10⁵ deque operations.

without it

Window max/min would cost O(n·k) by rescanning, or O(n log n) with a heap and lazy deletion — too slow for long streams with big windows.

when · why · how

when: "Max or min of every window", or a DP / prefix-sum step that needs the best candidate among the last k indices.
why: A newer element that is at least as good makes older, smaller ones useless forever, so drop them. Each index enters and leaves once → O(n) time, O(k) space.
how: A Deque<Integer> of indices: poll the front when it leaves the window, poll the back while its value ≤ the new one, offerLast(i); the front is the answer.

since1980–1985

Queue from two stacks (amortized O(1))

Robert Hood & Robert Melville; Robert E. Tarjan

In a 1980 Cornell report (a journal paper in 1981), Hood and Melville showed several ways to build a queue in pure LISP, where lists can only be read from the front. The key move is reversing a list — and they showed how to spread that reversal over many operations so that each one stays cheap. In 1985 Tarjan's survey "Amortized Computational Complexity" laid out the method of pricing a whole sequence of operations instead of one call — exactly how we cost the two-stack queue.

the problem it solvedA FIFO queue built only from structures that work at one end (stacks, or immutable lists in functional languages), at O(1) average cost per operation.

its jobs today

Immutable queues in functional libraries: Scala's immutable.Queue is documented as a pair of lists — one for elements coming in, one for elements going out.
The textbook example of amortized cost — the same reasoning explains why ArrayList.add and HashMap resizing are O(1) on average.

the weight it carries

Illustrative: 1,000 pushes, then 1,000 pops. The first pop pours all 1,000 elements from in to out — one expensive call. In total: 1,000 pushes + 1,000 × (pop + push) for the pour + 1,000 pops = 4,000 stack operations for 2,000 queue calls, 2 per call. Transferring on every push instead costs about 4 × (0 + 1 + … + 999) ≈ 2·10⁶.

without it

You would pay O(n) on every push, or need a real queue — which stack-only or immutable-list settings don't give you.

when · why · how

when: Only stacks (or immutable lists) are available, or an interviewer asks for "queue using stacks" to test amortized analysis.
why: Each element is pushed, moved and popped at most once, so n operations cost O(n): amortized O(1) each, even though one pop can be O(n).
how: Two Deque<Integer> stacks: push → in.push(x); pop/peek → if out is empty, pour all of in into out, then use out.

02 · plain english

The idea in 30 seconds

A queue lets you add at the rear and remove from the front: whoever arrived first leaves first (FIFO).

Both ends must be O(1). An array does that by letting head and tail walk forward and wrap around; a linked list does it with head and tail pointers.

A deque ("deck") opens both ends. Keep it sorted as you go and it becomes a monotonic deque — the trick behind sliding-window maximum.

picture this

Your printer's queue: jobs wait in the order you pressed Ctrl+P. The printer always takes the oldest job; a new job joins at the back. No job jumps the line — that is FIFO.

03 · remember

What you must know

FIFO: the element removed is always the one that has waited longest. A stack is LIFO; a queue is its opposite.
Circular array: tail = (tail + 1) % capacity and head = (head + 1) % capacity. Nothing ever shifts, so enqueue and dequeue are O(1).
Track size (or keep one slot empty) — otherwise head == tail can't tell an empty queue from a full one.
`ArrayDeque` is Java's default Queue and Stack: fast, cache-friendly, amortized O(1) at both ends. No null elements allowed.
`offer` / `poll` / `peek` return false/null on failure; `add` / `remove` / `element` throw. Pick one family and stay consistent.
Monotonic deque: pop from the back every element that can never be the answer again. Each index enters and leaves once → O(n) total.
Two stacks make a queue with amortized O(1) per operation: pour in into out only when out is empty.
Queues power BFS: processing nodes in arrival order visits them in order of distance — you'll use this in every graph chapter.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Linked queue: enqueue & dequeue

Top: the queue as the user sees it. Bottom: the linked nodes in memory, with head and tail markers.

loading simulation…

javajava.util.*

1class LinkedQueue {2    private static class Node {3        final int val;4        Node next;5 6        Node(int val) {7            this.val = val;8        }9    }10 11    private Node head; // front: we remove here12    private Node tail; // rear: we add here13    private int size;14 15    void enqueue(int x) {16        Node node = new Node(x);17        if (tail == null) head = node; // empty queue: the new node is also the front18        else tail.next = node; // link it after the old rear19        tail = node;20        size++;21    }22 23    int dequeue() {24        if (head == null) throw new NoSuchElementException("queue is empty");25        int x = head.val;26        head = head.next;27        if (head == null) tail = null; // queue became empty: forget the rear too28        size--;29        return x;30    }31 32    int peek() {33        if (head == null) throw new NoSuchElementException("queue is empty");34        return head.val;35    }36 37    boolean isEmpty() {38        return size == 0;39    }40}

sim

Circular buffer: watch head and tail wrap around

The array never shifts. Grey slots are free (or stale); the live part can wrap past the end back to index 0.

loading simulation…

javajava.util.*

1class CircularQueue {2    private final int[] data;3    private int head = 0; // index of the front element4    private int tail = 0; // index where the next element will go5    private int size = 0; // how many elements are stored right now6 7    CircularQueue(int capacity) {8        data = new int[capacity];9    }10 11    /** Adds x at the rear. Returns false when the queue is full (like Queue.offer). */12    boolean enqueue(int x) {13        if (size == data.length) return false;14        data[tail] = x;15        tail = (tail + 1) % data.length; // step right, wrap to 0 at the end16        size++;17        return true;18    }19 20    /** Removes and returns the front. Throws when empty (like Queue.remove). */21    int dequeue() {22        if (size == 0) throw new NoSuchElementException("queue is empty");23        int x = data[head];24        head = (head + 1) % data.length; // step right, wrap to 0 at the end25        size--;26        return x;27    }28 29    int peek() {30        if (size == 0) throw new NoSuchElementException("queue is empty");31        return data[head];32    }33 34    boolean isEmpty() {35        return size == 0;36    }37 38    int size() {39        return size;40    }41}

sim

Queue using two stacks

Pushes go to `in`. When `out` runs dry, pour `in` into it — the reversal puts the oldest element on top.

loading simulation…

javajava.util.*

1class MyQueue {2    private final Deque<Integer> in = new ArrayDeque<>(); // receives every push3    private final Deque<Integer> out = new ArrayDeque<>(); // serves pops, oldest on top4 5    public void push(int x) {6        in.push(x);7    }8 9    public int pop() {10        peek(); // makes sure the front is on top of out11        return out.pop();12    }13 14    public int peek() {15        if (out.isEmpty()) { // only refill when out has nothing left16            while (!in.isEmpty()) out.push(in.pop()); // reversing puts the oldest on top17        }18        return out.peek();19    }20 21    public boolean empty() {22        return in.isEmpty() && out.isEmpty();23    }24}

sim

Sliding window maximum with a monotonic deque

Values in the deque only decrease, so the front is the max. Smaller, older values are popped for good.

loading simulation…

javajava.util.*

1class Solution {2    public int[] maxSlidingWindow(int[] nums, int k) {3        int n = nums.length;4        int[] result = new int[n - k + 1];5        Deque<Integer> dq = new ArrayDeque<>(); // indices; values strictly decrease front → back6        for (int i = 0; i < n; i++) {7            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {8                dq.pollFirst(); // the front index slid out of the window9            }10            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {11                dq.pollLast(); // smaller and older: can never be a max again12            }13            dq.offerLast(i);14            if (i >= k - 1) {15                result[i - k + 1] = nums[dq.peekFirst()]; // the front is the window max16            }17        }18        return result;19    }20}

sim

A time-window queue (Number of Recent Calls)

Times only grow, so old pings leave from the front and never come back.

loading simulation…

javajava.util.*

1class RecentCounter {2    private final Queue<Integer> window = new ArrayDeque<>(); // pings inside [t - 3000, t]3 4    public int ping(int t) {5        window.offer(t); // newest joins at the rear6        while (window.peek() < t - 3000) {7            window.poll(); // too old for this and every later call8        }9        return window.size();10    }11}

sim

Reveal Cards: simulate on positions, not cards

A queue of positions replays the reveal process; the next smallest card drops into each revealed position.

loading simulation…

javajava.util.*

1class Solution {2    public int[] deckRevealedIncreasing(int[] deck) {3        int n = deck.length;4        int[] sorted = deck.clone();5        Arrays.sort(sorted); // cards will be revealed smallest first6        Queue<Integer> positions = new ArrayDeque<>();7        for (int i = 0; i < n; i++) positions.offer(i); // replay the process on positions8        int[] result = new int[n];9        for (int card : sorted) {10            int pos = positions.poll(); // the next position that gets revealed11            result[pos] = card; // so the next smallest card goes there12            if (!positions.isEmpty()) {13                positions.offer(positions.poll()); // the following top card moves to the bottom14            }15        }16        return result;17    }18}

05 · cost

Time & space, explained

Queue operations by implementation
	Circular array (raw)	Linked queue (raw)	ArrayDeque	ArrayList + remove(0)	why
enqueue (offer)	O(1)	O(1)	O(1) amortized	O(1) amortized	Write at `tail` / link after `tail`. ArrayDeque and ArrayList occasionally grow their array, which averages out to O(1).
dequeue (poll)	O(1)	O(1)	O(1)	O(n)	Moving `head` is one step. `ArrayList.remove(0)` shifts every remaining element left.
peek front	O(1)	O(1)	O(1)	O(1)	The front is at a known index or node.
contains / search	O(n)	O(n)	O(n)	O(n)	A queue keeps arrival order, not sorted order — you must scan.
Memory	O(capacity)	O(n) + a node per item	O(n)	O(n)	Linked nodes pay for an object header and a `next` reference per element; arrays are compact.

Building one structure from the other
	push / enqueue	pop / dequeue	Extra space	why
Queue from two stacks (lazy transfer)	O(1)	O(1) amortized, O(n) worst	O(n)	Each element is moved from `in` to `out` at most once in its life, so n operations cost O(n) in total.
Queue from two stacks (transfer on every push)	O(n)	O(1)	O(n)	Every push empties and refills the main stack.
Stack from one queue (rotate on push)	O(n)	O(1)	O(n)	After offering x, the other n−1 elements are rotated behind it.
Stack from two queues (move on pop)	O(1)	O(n)	O(n)	Pop moves all but the newest element to the helper queue.

Sliding window maximum (n elements, window k)
	Time	Extra space	why
Rescan every window	O(n·k)	O(1)	n − k + 1 windows, k elements each.
Max-heap with lazy deletion	O(n log n)	O(n)	n heap inserts; stale tops are removed later, so the heap can hold up to n entries.
Monotonic deque	O(n)	O(k)	Each index is pushed once and popped at most once; the deque never holds more than k indices.

06 · java

Raw vs Collections Framework

A queue on a circular array: write it by hand vs use ArrayDeque

javaraw circular array (head, tail, size)java.util.*

1class CircularQueue {2    private final int[] data;3    private int head = 0; // index of the front element4    private int tail = 0; // index where the next element will go5    private int size = 0; // how many elements are stored right now6 7    CircularQueue(int capacity) {8        data = new int[capacity];9    }10 11    /** Adds x at the rear. Returns false when the queue is full (like Queue.offer). */12    boolean enqueue(int x) {13        if (size == data.length) return false;14        data[tail] = x;15        tail = (tail + 1) % data.length; // step right, wrap to 0 at the end16        size++;17        return true;18    }19 20    /** Removes and returns the front. Throws when empty (like Queue.remove). */21    int dequeue() {22        if (size == 0) throw new NoSuchElementException("queue is empty");23        int x = data[head];24        head = (head + 1) % data.length; // step right, wrap to 0 at the end25        size--;26        return x;27    }28 29    int peek() {30        if (size == 0) throw new NoSuchElementException("queue is empty");31        return data[head];32    }33 34    boolean isEmpty() {35        return size == 0;36    }37 38    int size() {39        return size;40    }41}

javaQueue<Integer> q = new ArrayDeque<>()java.util.*

1class LibraryQueue {2    static List<Integer> demo() {3        Queue<Integer> q = new ArrayDeque<>(); // the go-to Queue implementation4        q.offer(1); // [1]5        q.offer(2); // [1, 2]6        q.offer(3); // [1, 2, 3]7        List<Integer> seen = new ArrayList<>();8        seen.add(q.peek()); // 1 — look at the front, don't remove9        seen.add(q.poll()); // 1 — remove the front → [2, 3]10        seen.add(q.poll()); // 2 → [3]11        seen.add(q.size()); // 112        return seen; // [1, 1, 2, 1]13    }14 15    static Integer pollWhenEmpty() {16        Queue<Integer> q = new ArrayDeque<>();17        return q.poll(); // null — poll/peek/offer report failure with a special value18    }19 20    static boolean removeWhenEmptyThrows() {21        Queue<Integer> q = new ArrayDeque<>();22        try {23            q.remove(); // remove/element/add throw instead24            return false;25        } catch (NoSuchElementException e) {26            return true;27        }28    }29}

% data.length is the whole trick: index capacity − 1 steps to index 0 instead of falling off the array.
size removes the classic ambiguity: when head == tail the queue is either empty (size == 0) or full (size == capacity).
ArrayDeque is exactly this circular buffer, plus automatic growth when it fills up — that's why its offer is amortized O(1).
Declare the variable as the interface (Queue<Integer> / Deque<Integer>) so you can swap implementations without touching the rest of the code.

A linked queue (and why LinkedList is rarely the best Queue)

javaraw linked queuejava.util.*

1class LinkedQueue {2    private static class Node {3        final int val;4        Node next;5 6        Node(int val) {7            this.val = val;8        }9    }10 11    private Node head; // front: we remove here12    private Node tail; // rear: we add here13    private int size;14 15    void enqueue(int x) {16        Node node = new Node(x);17        if (tail == null) head = node; // empty queue: the new node is also the front18        else tail.next = node; // link it after the old rear19        tail = node;20        size++;21    }22 23    int dequeue() {24        if (head == null) throw new NoSuchElementException("queue is empty");25        int x = head.val;26        head = head.next;27        if (head == null) tail = null; // queue became empty: forget the rear too28        size--;29        return x;30    }31 32    int peek() {33        if (head == null) throw new NoSuchElementException("queue is empty");34        return head.val;35    }36 37    boolean isEmpty() {38        return size == 0;39    }40}

Remove at head, add at tail — both O(1) with no array to grow.
When the last node is dequeued, set tail = null too. Forgetting this is the #1 linked-queue bug.
java.util.LinkedList implements Queue and Deque, but each element costs a node object. The ArrayDeque Javadoc itself says it is likely faster than LinkedList when used as a queue.
Use LinkedList only if you need null elements or you also need it as a List (index access).

Deque: both ends (and Java's real Stack)

javaDeque<Integer> dq = new ArrayDeque<>()java.util.*

1class BothEnds {2    static String demo() {3        Deque<Integer> dq = new ArrayDeque<>();4        dq.offerLast(2); // [2]5        dq.offerFirst(1); // [1, 2]6        dq.offerLast(3); // [1, 2, 3]7        int front = dq.pollFirst(); // 1 → [2, 3]8        int back = dq.pollLast(); // 3 → [2]9        dq.push(9); // stack-style push = offerFirst → [9, 2]10        int top = dq.peek(); // 9 — peek() = peekFirst()11        return front + " " + back + " " + top + " " + dq; // "1 3 9 [9, 2]"12    }13}

offerFirst/offerLast, pollFirst/pollLast, peekFirst/peekLast — every end operation is O(1).
push/pop/peek on a Deque work on the front — so an ArrayDeque is also the recommended stack (prefer it over the legacy Stack class).
Iterating an ArrayDeque (or printing it) goes front → back.

BFS teaser: the queue's most famous job

javabreadth-first search distancesjava.util.*

1class Bfs {2    /** Fewest edges from start to every node of an unweighted graph (-1 = unreachable). */3    static int[] distances(List<List<Integer>> graph, int start) {4        int[] dist = new int[graph.size()];5        Arrays.fill(dist, -1);6        Deque<Integer> queue = new ArrayDeque<>();7        dist[start] = 0;8        queue.offer(start);9        while (!queue.isEmpty()) {10            int node = queue.poll(); // oldest discovered = closest to start11            for (int next : graph.get(node)) {12                if (dist[next] == -1) { // first visit is the shortest13                    dist[next] = dist[node] + 1;14                    queue.offer(next);15                }16            }17        }18        return dist;19    }20}

Nodes leave the queue in the order they were discovered, which is the order of their distance from the start.
So the first time BFS reaches a node is along a shortest path (in an unweighted graph). The graphs chapter builds on this.

Java API you will actually use
call	does	cost
`Queue<Integer> q = new ArrayDeque<>()`	Default FIFO queue (resizable circular array, no nulls)	—
`q.offer(x) / q.add(x)`	Add at the rear; offer returns false if a bounded queue is full, add throws IllegalStateException	O(1) amortized
`q.poll() / q.remove()`	Remove the front; poll returns null when empty, remove throws NoSuchElementException	O(1)
`q.peek() / q.element()`	Read the front without removing; peek returns null, element throws	O(1)
`dq.offerFirst(x) / dq.offerLast(x)`	Add at the front / back of a Deque	O(1) amortized
`dq.pollFirst() / dq.pollLast()`	Remove from the front / back (null if empty)	O(1)
`dq.peekFirst() / dq.peekLast()`	Read either end (null if empty)	O(1)
`dq.push(x) / dq.pop()`	Stack-style: addFirst / removeFirst	O(1) amortized / O(1)
`q.size() / q.isEmpty()`	Element count / emptiness	O(1)
`q.contains(x) / q.remove(x)`	Search or remove one element by value	O(n)
`new ArrayBlockingQueue<>(cap)`	Thread-safe bounded queue (producer/consumer)	O(1)

A plain FIFO queue (BFS, scheduling, buffering)

→ ArrayDeque via the Queue interface

Fastest general-purpose queue; O(1) at both ends, compact memory.

A stack

→ ArrayDeque via the Deque interface (push/pop/peek)

Stack is a synchronized legacy class built on Vector; the Javadoc recommends Deque.

Sliding-window max/min, or "next useful candidate" problems

→ ArrayDeque<Integer> of indices as a monotonic deque

Both-end O(1) access; storing indices lets you tell when the front has left the window.

Fixed capacity, no allocation after start-up

→ Raw circular array (int[] + head/size)

No boxing, no resizing — what ring buffers in drivers and audio code do.

Process by priority, not arrival

→ PriorityQueue

It implements Queue, but poll() returns the smallest element, not the oldest (see the heaps chapter).

Several threads share the queue

→ ArrayBlockingQueue / LinkedBlockingQueue / ConcurrentLinkedQueue

ArrayDeque and LinkedList are not thread-safe.

null elements or List-style index access

→ LinkedList

ArrayDeque rejects null; LinkedList allows it and is also a List.

07 · recognise

Spot the pattern

"Process in the order they arrive", "first come first served", task scheduling

Plain FIFO queue (ArrayDeque)

Shortest path / fewest steps in an unweighted graph or grid, level-by-level

BFS with a queue

"Within the last X seconds / last k items", stream of timestamps

Queue as a time window: offer new, poll expired from the front

Max or min of every window of size k

Monotonic deque of indices

Shortest/longest subarray with a sum condition and negative numbers

Prefix sums + monotonic deque (LC 862)

"Design a circular queue / ring buffer / fixed-size buffer"

Array + head + size, indices wrap with %

Rotation games: "move the top card to the bottom", "pass the ball k times", Josephus

Simulate with a queue: poll then offer

Need both ends (add/remove front and back)

Deque (ArrayDeque)

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Using head == tail alone to test empty/full in a circular array — they look identical. Keep a size counter.
Computing (head - 1) % n in Java: % keeps the sign, so -1 % 5 == -1. Use (head - 1 + n) % n.
Using ArrayList.remove(0) as dequeue — it's O(n), turning an O(n) algorithm into O(n²).
Calling remove() / element() on a possibly empty queue — they throw. poll() / peek() return null instead (and unboxing that null into an int throws a NullPointerException).
Adding null to an ArrayDeque — it throws NullPointerException, because null is its "empty" signal.
Storing values instead of indices in a sliding-window deque — you then can't tell when the front left the window.
Comparing Integer objects from a deque with == (e.g. dq.peekFirst() == dq.peekLast()): outside the cached range −128…127, equal values are usually different objects, so == says false. Unbox or use .equals.
Forgetting tail = null when a linked queue becomes empty.

tricks

Default to Deque<Integer> q = new ArrayDeque<>(); and use offer/poll/peek — it works for queues, stacks and deques.
For monotonic deques say the invariant aloud: "values in the deque decrease from front to back, and all indices are inside the window."
When an operation is sometimes O(n) (two-stack queue), say amortized O(1) and give the reason: each element is moved at most once.
Simulation problems (tickets, cards, Josephus) are allowed to start as a queue simulation — then look for a counting shortcut.
Edge cases to test: empty queue, capacity 1, wrap-around exactly at the last index, k = 1, k = n, all-equal values.

09 · why & how

Questions you might be too shy to ask

Why not just use an array and shift everything left on dequeue?

Shifting moves every remaining element, so dequeue becomes O(n). With n operations that's O(n²). A circular array moves head instead of the data — O(1).

How does % capacity make the array "circular"?

(i + 1) % capacity is i + 1 for every index except the last one, where it becomes 0. So walking right from the last slot lands on the first slot — the array behaves like a ring.

Why is the rear (head + size − 1) % k and the next free slot (head + size) % k?

Start at head and count size items forward, wrapping with % k. The last item is size − 1 steps after head; the free slot is one step after that. Example: k = 4, head = 3, size = 2 → items sit in slots 3 and 0. Rear = (3 + 2 − 1) % 4 = 0, next free = (3 + 2) % 4 = 1. Simple hai — just count on a ring.

ArrayDeque or LinkedList for a queue?

ArrayDeque. Both give O(1) offer/poll, but ArrayDeque stores elements in one contiguous array (cache-friendly, no per-node object). Pick LinkedList only if you need nulls or List methods.

When should I use offer/poll vs add/remove?

They do the same job; only failure differs. offer/poll/peek return false/null; add/remove/element throw. In interviews offer/poll/peek is the common style. Just remember that poll() on an empty queue returns null, and assigning that to an int throws.

Queue or deque — when do I actually need a deque?

A queue adds at the back and removes from the front. That's all. A deque can add and remove at both ends. You need it when one problem uses both ends: in Sliding Window Maximum, old indices leave from the front and smaller values are popped from the back. In Java, ArrayDeque is both — declare it as Queue<Integer> or Deque<Integer> depending on what you need.

Is PriorityQueue a queue?

It implements Queue, but it is not FIFO — poll() returns the smallest element (by its comparator), not the oldest. It's a heap; see the heaps chapter.

What does "amortized O(1)" really mean for the two-stack queue?

A single pop can cost O(n) (when it pours in into out). But every element is poured at most once, so any sequence of n operations does at most about 4n stack operations in total — O(1) on average per operation, guaranteed, not just "usually".

Why does the monotonic deque store indices, not values?

You need two facts: the value (to compare) and the position (to know if it left the window). An index gives you both: nums[i] and i.

Sliding Window Maximum: why evict the front when it is <= i − k?

The window ending at i holds indices i − k + 1 to i. So index i − k is the first one outside it. Example: k = 3, i = 5 → the window is 3, 4, 5, and index 2 = 5 − 3 must go. With < i − k, index 2 would stay one step too long and could report a stale max. Only one index leaves per step, so an if (not a while) is enough for the front.

Popping smaller values from the back — can't that throw away a future answer?

No. Say 3 is in the deque and 6 arrives later. Every future window that still holds 3 also holds 6, because 6 is newer and leaves the window later. So 3 can never beat 6 again — dropping it loses nothing. Equal values work the same way: the newer copy stays longer, so popping with <= is safe.

Isn't a while loop inside a for loop O(n²)?

Not here. Count pops instead of loop iterations: each index is pushed once and can be popped at most once. Total pops ≤ n, so the whole run is O(n).

Time Needed to Buy Tickets: is the plain queue simulation good enough?

Check the constraints first. Here n ≤ 100 and tickets ≤ 100, so the line sells at most 100 × 100 = 10⁴ tickets — the simulation passes easily. If tickets could be 10⁹, it would time out and you'd need the counting formula. In an interview, give the simulation first (correct, easy), then the formula if they ask for better.

In an interview, can I just use ArrayDeque, or must I build the queue myself?

Depends on what is being tested. If the queue is a tool (BFS, sliding window, recent calls), use ArrayDeque — nobody wants you to rebuild it. If the problem is the queue (Design Circular Queue, Design Circular Deque), write the raw array with head and size. Not sure? Just ask: "Can I use ArrayDeque, or should I implement the buffer myself?"

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#232
Implement Queue using Stacksmust-do
EasyAppleMicrosoftBloombergAmazonMeta
#225
Implement Stack using Queues
EasyBloombergMicrosoftAmazon
#622
Design Circular Queuemust-do
MediumAppleAmazonMicrosoftMeta
#933
Number of Recent Calls
EasyGoogleAmazon
#362
Design Hit CounterLeetCode Premium
MediumAppleUberWalmartGoogleAmazon
#239
Sliding Window Maximummust-do
HardOracleAmazonNVIDIAMicrosoftGoogle+1
#950
Reveal Cards In Increasing Order
MediumGoogle
#2073
Time Needed to Buy Tickets
EasyGoogleAmazon
#641
Design Circular Deque
MediumAmazon
#862
Shortest Subarray with Sum at Least K
HardGoldman SachsAmazonGoogle

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#994
Rotting Oranges
Mediumin Graphs
Multi-source BFS: every rotten orange starts in the queue, and each minute is one level of polls.
#1091
Shortest Path in Binary Matrix
Mediumin Graphs
BFS on a grid: the first time the queue reaches the corner is along a shortest path.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
A queue is FIFO: offer at the rear, poll from the front — whoever waited longest leaves first. A deque opens both ends.
use it when
"In arrival order", BFS / fewest steps, "in the last X seconds", rotation games, and the max or min of every window.
template
Deque<Integer> q = new ArrayDeque<>(); → offer, poll, peek, isEmpty. The same object is a stack with push/pop/peek.
cost
offer / poll / peek: O(1) (amortized when ArrayDeque grows). ArrayList.remove(0) is O(n), so n dequeues become O(n²).
template
Ring buffer: head + size. Next free = (head + size) % k, rear = (head + size − 1) % k, dequeue = head = (head + 1) % k.
trap
head == tail means both empty and full — keep a size. Stepping left? (head − 1 + k) % k, because Java's % can be negative.
trap
Monotonic deque: store indices, not values — otherwise you can't tell when the front has left the window.
cost
Monotonic deque and two-stack queue: each element goes in once and comes out at most once → O(n) total, amortized O(1) each.
pro tip
Time window with growing timestamps? Offer the new one, poll expired ones from the front; the answer is the size.
trap
poll() on an empty queue returns null — int x = q.poll(); then throws. And ArrayDeque refuses null elements.

12 · recall

Flip, remember, repeat

card 1 / 15

recall

Queue vs stack: which element comes out next?

tap or Space to flip ↻

Question 1: Queue vs stack: which element comes out next?

13 · check yourself

Quick quiz

Circular queue with capacity 5, tail = 4. You enqueue one element. What is tail now?
Why keep a `size` field in a circular array queue?
What does `poll()` return on an empty `ArrayDeque`?
Queue from two stacks: what's the cost of n operations in total?
Sliding window max deque (front → back) holds values [8, 5, 3]. Next value is 6. What does the deque hold after pushing it?
Which is the best default Queue implementation in Java?
Why does a monotonic deque run in O(n) despite a while loop inside a for loop?
HitCounter (window = last 300 s): hit(100), then getHits(400). What does it return?

0/0 correct · 8 left

14 · learn more