Queues and Deques: FIFO, the Circular Buffer, and the Sliding-Window Trick

You pull a paper ticket at the pharmacy — B-47 — and glance up at the little red board on the wall: NOW SERVING B-41. So you settle in. Six people ahead of you, and you already know, without anyone announcing it, exactly what will happen: 41 gets called, then 42, then 43, in the order everyone arrived. Nobody who walks in after you will be served before you. The line is fair, and the fairness is the whole point.

That fairness has a name. It’s a data structure called a queue, and it runs more of your day than almost anything else you’ll ever build — the print job you fired off, the keystrokes racing ahead of a laggy app, the packets flowing into your phone. By the end of this article you and I will have built one that never wastes a cell and never loses its place, and then we’ll teach it a trick that stumps a lot of candidates: finding the maximum of every sliding window in one clean pass.

Let’s start nowhere near a computer

Go back to that pharmacy counter, because it’s hiding the single idea that makes fast queues possible.

There are two numbers on the wall. One is on your paper ticket — the next number to hand out. The other is the red board — the number being served right now. When the pharmacist finishes with someone, they don’t ask the whole line to physically shuffle one step forward. That would be chaos, and it would be slow. They just tick the red board up by one. When a new person walks in, the dispenser ticks the ticket number up by one.

That’s the entire trick, and it’s worth saying slowly: the line never moves — two numbers do. One number chases the other. Serving someone advances the front number; a new arrival advances the back number. The gap between them is exactly how many people are waiting.

Hold onto those two numbers. We’re going to call the front one head and the back one tail, and almost everything clever later is just a question of how they chase each other around.

The same line, all over your day

Once you see “join at the back, leave from the front,” you spot it everywhere. The print spooler holds your documents in the order you sent them. Your operating system keeps a run queue of threads waiting for a CPU. A keyboard buffer holds the characters you typed while an app was busy, so they replay in order the moment it catches up. A web server drops incoming requests into a work queue that a pool of worker threads drains — that’s the beating heart of the thread pool. And breadth-first search is breadth-first only because it uses a queue: visit a node, drop its neighbours at the back, and because they leave the front in arrival order, you finish an entire ring of the graph before you ever touch the next ring out. Swap that queue for a stack and BFS silently becomes depth-first.

But here’s the example worth slowing down on, because it’s literally the structure we’re about to build. When a packet arrives at your network card faster than the CPU can read it, the hardware doesn’t allocate memory on the fly — there’s no time. It drops the packet into a fixed-size ring buffer: a small, pre-allocated block of slots where the producer (the card) writes at the tail and the consumer (the driver) reads from the head, both wrapping around the end of the block. Your sound card does the same with audio frames. This is the queue with training wheels off — fixed capacity, zero allocation, running millions of times a second — and it lives or dies on exactly the two decisions we’re about to make: how the indices wrap, and how you tell a full ring from an empty one.

What a queue actually looks like

Strip away the pharmacy and here’s the shape. A queue is a row of cells with two markers: head points at the front (the next thing to leave), and tail points at the next free cell (where the next arrival lands).

Only two operations really matter, and both must be cheap:

• enqueue — add a value at the tail, then nudge tail one step to the right.
• dequeue — take the value at the head, then nudge head one step to the right.

That’s it. No searching, no shuffling. A queue deliberately gives up random access — you can’t peek at “the third person in line” cheaply, and you shouldn’t want to. In exchange, the two operations you do care about are each a constant handful of steps. The entire craft of building a good queue is keeping that promise: enqueue and dequeue in O(1), always. Let’s see how the obvious approach breaks that promise, and then fix it for good.

Let’s build one, step by step

Step 1: the obvious array — and the drift

Back the queue with a plain array. Keep a head index and a tail index, both starting at 0. To enqueue, write at tail and increment it. To dequeue, read at head and increment it. Nobody shuffles — just like the pharmacy, the markers move, not the data.

// enqueue just writes at tail and marches it right...
boolean enqueue(int v) {
    if (tail == slots.length) {
        return false;          // "full" — even when the front is all free!
    }
    slots[tail++] = v;
    return true;
}
 
// dequeue just marches head right, abandoning the cell it leaves behind
int dequeue() {
    return slots[head++];
}

Run it for a while and watch what happens. Every enqueue pushes tail right. Every dequeue pushes head right. The little window of live values drifts rightward across the array — and the cells it leaves behind on the left are abandoned. This code can never touch them again.

Now the punchline: after a handful of operations, tail hits the end of the array and enqueue reports full — even though there are free cells sitting right there at the front. You’ve got a queue that swears it’s out of room while a third of it is empty. That’s the drift, and it’s the bug that sinks every naïve array queue.

You could “fix” it by shifting every element back to index 0 on each dequeue. Don’t — that turns your O(1) dequeue into an O(n) stampede, moving the whole line every single time one person leaves. We threw away shuffling for a reason. The real fix keeps the markers moving and just changes where they go when they hit the wall.

Step 2: bend the array into a ring

Here’s the move. When tail reaches the last cell, don’t give up — wrap it back to index 0 and start reusing the cells the front has already vacated. Do the same for head. The array stops being a line with two dead ends and becomes a ring: a circular track the two markers chase each other around forever.

The wrap is one line of arithmetic — the modulo operator:

tail = (tail + 1) % slots.length;   // 7 → 0 when length is 8

When tail is 7 and the capacity is 8, (7 + 1) % 8 is 0. The marker teleports from the last cell straight back to the first, landing exactly on the cells the dequeues freed up. No shifting, no waste, still one step.

Here are enqueue and dequeue with the wrap baked in. Notice they’re barely longer than the naïve version — the whole fix is that % slots.length:

/** Adds v at the back. Returns false if the ring is full. O(1). */
public boolean enqueue(E v) {
    if (isFull()) {
        return false;
    }
    slots[tail] = v;
    tail = (tail + 1) % slots.length;   // step forward, wrapping past the end
    size++;
    return true;
}
 
/** Removes and returns the front. Throws if empty. O(1). */
@SuppressWarnings("unchecked")
public E dequeue() {
    if (isEmpty()) {
        throw new NoSuchElementException("dequeue from an empty queue");
    }
    E v = (E) slots[head];
    slots[head] = null;                 // release the reference so it can be GC'd
    head = (head + 1) % slots.length;   // step forward, wrapping past the end
    size--;
    return v;
}
 

Step 3: full or empty? The question that trips everyone

You may have noticed I quietly added a size field to enqueue and dequeue. That wasn’t bookkeeping for its own sake — it’s the fix to the single subtlest problem in the whole structure, and interviewers love it precisely because it looks like a non-issue until it bites.

Think about head and tail on the ring. When you drain the queue completely, head finally catches up to tail — so head == tail means empty. But now fill the queue completely: tail wraps all the way around the ring and lands right back on head — so head == tail means full. The exact same condition means two opposite things, and from the indices alone you cannot tell which.

This is the real depth of the circular buffer, and there are two classic ways out:

1. Keep a size count. Increment on enqueue, decrement on dequeue. Now size == 0 is unambiguously empty and size == capacity is unambiguously full, no matter where head and tail happen to sit. It costs one integer, and it hands you an O(1) size() for free — which is why it’s the approach in the code here.

public boolean isEmpty() {
    return size == 0;
}
 
public boolean isFull() {
    return size == slots.length;
}

2. Sacrifice one slot. Refuse to ever fill the last cell, so a full ring always keeps exactly one gap between tail and head. Then full ⇔ (tail + 1) % capacity == head and empty ⇔ head == tail, with no counter at all. You “waste” one cell of capacity to buy back the ambiguity.

Why would anyone give up a cell instead of just counting? Because of the thing that isn’t in our code: threads. In a lock-free, single-producer-single-consumer ring — the kind that shuttles packets and audio frames — the producer only ever writes tail and the consumer only ever writes head. A shared size counter would be written by both, and that shared write is exactly the read-modify-write race that breaks under concurrency: two threads read the same size, both add one, and one update vanishes. The one-slot trick avoids that landmine entirely, because each thread touches only its own index. Same ring, a different fear, a different answer — that’s the tell of someone who’s actually built one.

Step 4: peek, and the promise kept

The last piece is peek — look at the front without removing it, the way you glance at the red board without being served:

@SuppressWarnings("unchecked")
public E peek() {
    if (isEmpty()) {
        throw new NoSuchElementException("peek at an empty queue");
    }
    return (E) slots[head];
}

And that’s the whole promise kept. Enqueue: check size, write, wrap, count — a fixed handful of steps regardless of how full the ring is. Dequeue and peek: the same. No shifting, no scanning, no growing. Every operation is O(1), five items or five million.

From one door to two: the deque

A queue lets you join at the back and leave from the front — one door in, one door out. A deque (pronounced “deck”, short for double-ended queue) throws the doors open at both ends. You can add or remove at the front and at the back, all in O(1):

Look at what that gives you. Use only addLast and removeFirst and it’s a plain FIFO queue. Use only addFirst and removeFirst and it’s a stack — last in, first out. A deque is a queue and a stack in one object, which is why the standard ArrayDeque is the recommended tool for both jobs — reach for it over the legacy Stack class and over a LinkedList.

And here’s the satisfying part: it’s the same ring we just built. To add at the front, you don’t shift anything — you step head backwards, wrapping the other way with head = (head - 1 + capacity) % capacity, and write there. ArrayDeque is exactly a growable circular buffer that lets both markers move in both directions. Everything you learned about the wrap and the full-versus-empty question carries straight over.

The party trick: sliding-window maximum

Now the problem that makes the deque earn its keep, and a genuine interview favourite. You’re given an array and a window width k. Slide a window of size k across the array and report the maximum in every window. For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, the answer is [3, 3, 5, 5, 6, 7].

The brute force re-scans all k elements for every window: O(n · k). We can do it in a single O(n) pass with one idea — a monotonic deque that holds indices, kept so their values always decrease from front to back. The front is therefore always the current window’s maximum.

The magic is in one insight: when a new value arrives, every smaller value still waiting in the deque is now useless forever. If nums[i] is bigger than the guy at the back of the deque, that back guy can never be a maximum again — any future window containing him also contains the bigger, later i. So we pop him. That keeps the deque decreasing, which keeps the answer sitting right at the front.

/** Max of every length-k window of nums. O(n): each index is pushed and popped once. */
public static int[] maxOfEachWindow(int[] nums, int k) {
    if (k < 1 || k > nums.length) {
        throw new IllegalArgumentException("need 1 <= k <= nums.length");
    }
    int[] result = new int[nums.length - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();   // holds indices; their values decrease front→back
    for (int i = 0; i < nums.length; i++) {
        // 1. the front slid out of the window on the left — drop it
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
            dq.pollFirst();
        }
        // 2. pop from the back every value <= nums[i] — they can never be the max again
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
            dq.pollLast();
        }
        // 3. push the new index; the front is always this window's max
        dq.offerLast(i);
        if (i >= k - 1) {
            result[i - k + 1] = nums[dq.peekFirst()];
        }
    }
    return result;
}

Three moves per step: drop the front if it just slid out of the window on the left; pop the back while it’s no bigger than the incoming value; push the new index. Read the front once the first full window forms, and it’s your answer.

Why is this O(n) and not O(n · k), given that inner while loop? Because of a classic amortized argument: each index is offered to the deque exactly once and polled off exactly once, ever. The while can’t pop more times in total than the number of things that were ever pushed. Across the whole array that’s at most n pushes and n pops — so the total work is linear, no matter how wild the loop looks in any single step. That “each element enters and leaves once” counting move is worth having in your pocket; it’s the same reasoning behind an array-list’s amortized-O(1) append.

How fast is this, really?

Three ways to back a queue, and what each operation truly costs. Let n be the number of items:

The ring and the linked list both hit O(1) on the two operations that matter — so why prefer the ring? Memory and cache. The linked list pays for a separate node object and two pointers on every element, scattered across the heap, so walking it thrashes the cache. The ring is one contiguous block the CPU loves, with zero per-element overhead. Its only cost is the one the linked list doesn’t have: a fixed capacity you must choose up front (or pay an occasional O(n) copy to grow, which still amortizes to O(1) — that’s what ArrayDeque does). The naïve shifting array is in the table only as a cautionary tale: it looks simplest and is quietly the worst.

The complete implementation

The whole ring, assembled — fixed capacity, wrap-around, and the size counter that keeps full and empty honest:

package dev.fiveyear.queue;
 
import java.util.NoSuchElementException;
 
public final class RingBuffer<E> {
 
    private final Object[] slots;
    private int head;   // index of the front element
    private int tail;   // index where the next element will be written
    private int size;   // how many elements are live right now
 
    public RingBuffer(int capacity) {
        if (capacity < 1) {
            throw new IllegalArgumentException("capacity must be >= 1");
        }
        this.slots = new Object[capacity];
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
 
    public boolean isFull() {
        return size == slots.length;
    }
 
    public int size() {
        return size;
    }
 
    /** Adds v at the back. Returns false if the ring is full. O(1). */
    public boolean enqueue(E v) {
        if (isFull()) {
            return false;
        }
        slots[tail] = v;
        tail = (tail + 1) % slots.length;   // step forward, wrapping past the end
        size++;
        return true;
    }
 
    /** Removes and returns the front. Throws if empty. O(1). */
    @SuppressWarnings("unchecked")
    public E dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("dequeue from an empty queue");
        }
        E v = (E) slots[head];
        slots[head] = null;                 // release the reference so it can be GC'd
        head = (head + 1) % slots.length;   // step forward, wrapping past the end
        size--;
        return v;
    }
 
    /** Returns the front without removing it. Throws if empty. O(1). */
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("peek at an empty queue");
        }
        return (E) slots[head];
    }
}

And the sliding-window maximum, standing on the standard ArrayDeque:

package dev.fiveyear.queue;
 
import java.util.ArrayDeque;
import java.util.Deque;
 
public final class SlidingWindowMax {
 
    private SlidingWindowMax() {}
 
    /** Max of every length-k window of nums. O(n): each index is pushed and popped once. */
    public static int[] maxOfEachWindow(int[] nums, int k) {
        if (k < 1 || k > nums.length) {
            throw new IllegalArgumentException("need 1 <= k <= nums.length");
        }
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();   // holds indices; their values decrease front→back
        for (int i = 0; i < nums.length; i++) {
            // 1. the front slid out of the window on the left — drop it
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            // 2. pop from the back every value <= nums[i] — they can never be the max again
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            // 3. push the new index; the front is always this window's max
            dq.offerLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
}

And here they are doing the things we drew — the comments are the exact outputs:

RingBuffer<String> q = new RingBuffer<>(3);
q.enqueue("A");
q.enqueue("B");
q.enqueue("C");
q.isFull();        // true
q.enqueue("D");    // false — no room
q.dequeue();       // "A"  — the front leaves first
q.enqueue("D");    // true — tail wraps into A's old cell
q.peek();          // "B"  — the new front
 
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
SlidingWindowMax.maxOfEachWindow(nums, 3);   // [3, 3, 5, 5, 6, 7]

The interview corner

Queues look too simple to be an interview topic — which is exactly why the good questions live in the corners: capacity, concurrency, and the deque trick.

Clarifying questions to ask first

• Fixed capacity or unbounded? This decides everything. A bounded ring needs a full-versus-empty answer and a policy for “what happens when it’s full”; an unbounded one needs a growth strategy.
• When it’s full, do we block, drop, or grow? Back-pressure, load-shedding, and resizing are three different systems. Name the one the problem wants.
• Single-threaded or concurrent? One thread lets you use a plain size counter. Multiple producers or consumers change the whole design — locks, or a lock-free ring with the one-slot trick.

The follow-up ladder

1. “Make enqueue/dequeue O(1) on an array.” — A circular buffer: wrap both indices with % capacity so freed front cells get reused; no shifting.
2. “How do you tell full from empty when head == tail?” — Keep a size count (empty is 0, full is capacity), or leave one slot always empty so full is (tail + 1) % capacity == head.
3. “Now make it thread-safe for one producer and one consumer.” — Drop the shared size counter — it’s a read-modify-write race — and use the one-slot trick so each thread writes only its own index; that’s a lock-free SPSC ring.
4. “Implement a stack and a queue with the same class.” — A deque (ArrayDeque): addLast/removeFirst is a queue, addLast/removeLast is a stack, all O(1).
5. “Maximum of every sliding window of size k, in O(n).” — A monotonic deque of indices kept decreasing; the front is each window’s max, and the amortized O(n) falls out because every index is pushed and popped once.

Mistakes that fail the round

• Shifting the array on dequeue. It looks like it works and it’s secretly O(n) per removal — the drift bug’s evil twin. Wrap the index instead.
• Assuming head == tail means empty. On a full ring it means the opposite. If you can’t explain how you disambiguate, you haven’t built a real circular buffer.
• Reaching for Stack or synchronized collections by reflex. The legacy Stack and Vector are synchronized and slow; ArrayDeque is the modern default for both stack and queue. Know why.

Where to go from here

You own the core now: two markers chasing each other around a ring, with a count to keep full and empty honest. Three natural next stops:

• BlockingQueue and the producer/consumer pattern — the bounded ring with back-pressure built in, the backbone of every thread pool and work-stealing scheduler.
• The priority queue (heap) — when “first in, first out” becomes “most important out first,” the ring gives way to a binary heap; it’s what powers Dijkstra’s shortest path.
• Lock-free ring buffers — the LMAX Disruptor and kernel io_uring push the single-producer-single-consumer ring to millions of messages a second with no locks at all, on exactly the one-slot idea from Step 3.

Next time you pull a ticket and watch the red board tick up, you’ll know there’s no line really moving at all — just two numbers, chasing each other around a ring.