Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Queues

Medium4 min readdsaqueues

Introduction to Queues

A queue is the stack's mirror image. Where a stack serves the most recent arrival first (LIFO), a queue serves the oldest arrival first - first in, first out (FIFO). That single rule, "handle things in the order they arrived," turns out to be exactly what you need for fairness, scheduling, buffering, and - most importantly for interviews - breadth-first traversal of trees and graphs. This introduction lays out the queue's operations and guarantees, the mental model of "a line at a ticket counter," and the two problem families this module is built around: standard queue problems and the monotonic queue.

If you internalize one idea here, make it this: a queue is what you reach for whenever the thing you need to process next is the thing that has been waiting the longest.

What a Queue Is

A queue stores elements in a line. You add to the back (enqueue / offer) and remove from the front (dequeue / poll), and you can look at the front without removing it (peek). Every operation is O(1). The element you enqueued first is the first one you'll dequeue; the element you enqueued most recently waits at the back until everything ahead of it has been served.

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(1);            // [1]      (1 at front and back)
queue.offer(2);            // [1, 2]
queue.offer(3);            // [1, 2, 3]
int front = queue.peek();  // 1, not removed
queue.poll();              // removes 1 -> [2, 3]
queue.poll();              // removes 2 -> [3]

graph LR
    A["front → 1"] --> B["2"]
    B --> C["3 ← back"]
    D["poll removes 1 first (FIFO)"]

    style A fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9

This diagram shows a queue holding one, two, three, with one at the front and three at the back. Enqueue adds to the back and dequeue removes from the front, so the earliest element, one, comes out first. This is the first-in-first-out discipline.

Why FIFO Is the Whole Point

The FIFO rule matches any problem where order of arrival governs the logic. A printer serves jobs in the order received. A web server handles requests fairly. A breadth-first search visits nodes in order of distance from the start - closest first - which is exactly FIFO over a frontier of nodes. Whenever you process a sequence and must respect "first come, first served," or you need to explore outward in layers, a queue is the natural and usually optimal fit.

Implementation Choices

In Java, prefer ArrayDeque as a queue (offer, poll, peek) over LinkedList. Both implement the Queue interface, but ArrayDeque is backed by a resizable circular array with better cache behavior and no per-node object overhead. A few conventions used throughout this module:

• offer(x) adds to the back; poll() removes and returns the front; peek() returns the front without removing.
• Always check isEmpty() before poll/peek to avoid reading from an empty queue.
• A Deque (double-ended queue) allows adding and removing at both ends - this is the structure behind the monotonic queue in the second half of the module.

The Two Problem Families

This module is organized around the two ways queues show up in interviews.

Standard queue problems (17.2–17.8). The queue is used in its most direct role: process elements in arrival order, expire old entries from the front, or simulate a fair line. Recent-call counting within a time window, ticket-buying simulations, moving averages over a stream, card-reveal simulations, first-unique tracking, and the circular elimination game (Josephus). The unifying move is "add at the back; serve, expire, or rotate from the front."

Monotonic queue (17.9–17.17). A specialized deque kept in sorted order by discarding elements that can never again be the answer. This single idea answers an entire genre of sliding-window questions - "maximum in every window," "longest window where the spread stays bounded," constrained subsequence sums - in O(n) time, where a naive scan would be O(n·k) or worse. It's the queue-side counterpart to the monotonic stack you met in the previous section, and it's one of the highest-leverage patterns in array and stream interviewing, which is why it gets its own introduction (17.9) and the back half of this module.

graph TD
    A["Queue (FIFO)"] --> B["Standard problems (17.2-17.8)<br/>process / expire / rotate in arrival order"]
    A --> C["Monotonic queue (17.9-17.17)<br/>maintain sorted deque for O(n) window extremes"]

    style A fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This diagram shows the two families. Standard queue problems use the first-in-first-out rule to process, expire, or rotate elements in arrival order. The monotonic queue maintains a sorted deque to answer sliding-window extremes in linear time.

When to Reach for a Queue

In an interview, a few signals should make you think "queue":

• Order of arrival matters: first come, first served; fairness; buffering a stream.
• Expiring old entries: a time or count window where the oldest entries fall off the front (recent calls, moving average).
• Level-by-level exploration: breadth-first search over trees and graphs visits a frontier in FIFO order (you'll see this dominate the tree and graph sections later).
• Simulation of a line or rotation: people in a queue, cards dealt in order, elimination games where you rotate the front to the back.
• Sliding-window extremes: the monotonic-queue signature - maintain the max or min of a moving window in O(1) amortized.

A Note on Reading the Code

Throughout this module, queues hold either values or indices depending on what the problem needs. Watch that distinction: storing indices lets you detect when an element has slid out of a window (essential for Sliding Window Maximum and its relatives), while storing values suffices for pure order-of-arrival processing. Each topic states which it uses and why, and every algorithm comes with a frame-by-frame trace so you can watch the FIFO discipline play out.

Let's begin with the most direct possible queue application - Number of Recent Calls counts how many requests arrived in the last 3000 milliseconds by enqueuing each new timestamp and expiring stale ones from the front. It's FIFO in its purest form: new arrivals at the back, old ones leaving from the front.

Back to DSA Mastery - Interview Prep, End to End