Queues & Deques Explained: FIFO, Circular Buffers, and Sliding-Window Maximum

In plain words: the checkout-line analogy

Imagine a checkout line at a supermarket. Customers join at the back and are served from the front. Whoever arrives first is served first — that fairness is the defining property of a queue. No matter how many people arrived after you, none jumps the line. This First In, First Out (FIFO) discipline is what makes queues the backbone of scheduling: print jobs, CPU task queues, network packet buffers, and message brokers all work exactly this way.

FRONT                                   BACK (rear)
  │                                        │
  ▼                                        ▼
 [A]──[B]──[C]──[D]

enqueue(E):   [A]──[B]──[C]──[D]──[E]
              │                        │
            FRONT                    BACK

dequeue():  removes A → returns "A"
            [B]──[C]──[D]──[E]
            │                  │
          FRONT              BACK

Where the stack serves the most recent item first, the queue serves the oldest. That fairness property also powers breadth-first search, where 'process things in the order discovered' is the entire algorithm.

The interface

Why the obvious array implementation fails

Enqueue = append to the end of an array: O(1). But dequeue = remove index 0, which shifts every remaining element left: O(n) per dequeue, O(n²) to drain the whole queue. The quick fix — leave dequeued elements in place and advance a front index — fixes the time but leaks space: vacated slots are never reused and the queue crawls rightward through memory forever.

Initial:  [A, B, C, D]  front=0  back=3
enqueue E: [A, B, C, D, E]  front=0  back=4
dequeue:  returns A, front=1  →  [_, B, C, D, E]  (slot 0 wasted forever)
dequeue:  returns B, front=2  →  [_, _, C, D, E]  (slot 1 wasted forever)
...

After n dequeues and n new enqueues:
  [_, _, _, _, _, _, F, G, H ...]  front=n  back=2n
  Slots 0..n-1 are dead weight — memory grows without bound.

The circular buffer (ring buffer) — the real fix

Wrap the indices around using modulo arithmetic. Keep a fixed array of capacity c, a front index, and a count. The back position is always (front + count) mod c — the modulo lets the queue's contents bend around the end of the array back to slot 0, like a clock face rather than a ruler.

Capacity = 4:

Initial (empty):
  [ _ | _ | _ | _ ]   front=0  count=0

enqueue A, B, C, D:
  [ A | B | C | D ]   front=0  count=4   (full)
    0   1   2   3

dequeue (remove A), dequeue (remove B):
  [ _ | _ | C | D ]   front=2  count=2
    0   1   2   3
     ↑ slots 0,1 are now FREE for reuse

enqueue E:
  back = (front + count) % 4 = (2 + 2) % 4 = 0
  [ E | _ | C | D ]   front=2  count=3
    0   1   2   3
  Logical order:  C, D, E  (wraps from slot 2 → 3 → 0)

1. enqueue(x): if count == capacity, resize (allocate ~2× array, copy elements out in queue order with front at index 0). Write x at index (front + count) mod capacity; increment count.
2. dequeue(): read element at front. Advance front = (front + 1) mod capacity. Decrement count. The slot is now free — no shifting, no leak.
3. front(): return the element at index front.

With doubling on resize, the growable version keeps amortized O(1) enqueue exactly like the dynamic array in Lesson 3. Fixed-capacity ring buffers (reject-when-full or overwrite-oldest) are everywhere in systems code: audio pipelines, keyboard input buffers, network card receive rings, log rings.

The deque: both ends open

A deque (double-ended queue, pronounced 'deck') allows O(1) push and pop at *both* ends: pushFront, pushBack, popFront, popBack. It strictly generalizes both the stack (use one end) and the queue (use both, one-directionally). The circular buffer implements it naturally — pushFront just moves front backward: front = (front − 1 + capacity) mod capacity.

pushFront(x):
    front = (front - 1 + capacity) % capacity
    data[front] = x
    count++

pushBack(x):
    data[(front + count) % capacity] = x
    count++

popFront():
    value = data[front]
    front = (front + 1) % capacity
    count--
    return value

popBack():
    idx = (front + count - 1) % capacity
    value = data[idx]
    count--
    return value

* Amortized when growable. Space is O(n) throughout. Deque practical uses: work-stealing schedulers (push/pop own tasks at one end, steal from other end), undo histories with a size cap (evict oldest), palindrome checking, and 0-1 BFS in graphs.

The monotonic deque: sliding-window maximum in O(n)

The deque's most celebrated application. Problem: given an array and window size k, report the maximum of every sliding window of k consecutive elements. Brute force scans each window: O(n·k). The monotonic deque does it in O(n) — the same evict-what-can-never-win idea as the monotonic stack, but with expiry at the front.

function slidingWindowMax(arr, k):
    dq = empty Deque of indices    # values in dq are decreasing front→back
    result = []

    for i in 0 .. len(arr)-1:

        # 1. Expire: front index is outside the current window
        while not dq.isEmpty() and dq.front() <= i - k:
            dq.popFront()

        # 2. Evict: back values ≤ arr[i] can never be a future window max
        while not dq.isEmpty() and arr[dq.back()] <= arr[i]:
            dq.popBack()

        dq.pushBack(i)

        # 3. Record: window is full starting at i = k-1
        if i >= k - 1:
            result.append(arr[dq.front()])

    return result

i=0  arr[0]=3   expire:none  evict:none  push 0   dq:[0]         (values [3])
               i<k-1=1, no output

i=1  arr[1]=1   expire:0>1-2=no  evict:arr[0]=3>1,keep  push 1  dq:[0,1]  (values [3,1])
               i=k-1=1 → output arr[dq.front()]=arr[0]=3   result:[3]

i=2  arr[2]=4   expire:dq.front()=0 ≤ 2-2=0 → popFront  dq:[1]
               evict:arr[1]=1≤4 → popBack  dq:[]
               push 2   dq:[2]  (values [4])
               i≥1 → output arr[2]=4   result:[3,4]

i=3  arr[3]=2   expire:dq.front()=2>3-2=1, keep
               evict:arr[2]=4>2, keep
               push 3   dq:[2,3]  (values [4,2])
               output arr[dq.front()]=arr[2]=4   result:[3,4,4]

Final: [3, 4, 4]
Windows: max(3,1)=3  max(1,4)=4  max(4,2)=4  ✓

Common pitfalls

• Dequeuing from index 0 of a plain array. The silent O(n²) drain. Use your language's built-in deque/queue type, or a ring buffer.
• Forgetting the modulo on wrap. `back = front + count` without `mod capacity` walks off the array on the very next operation after the first wrap. Every index update in a ring buffer must wrap.
• Confusing full and empty in a two-pointer ring buffer. When tracked by front and back pointers alone (without a count), full and empty are visually identical (front == back). Solution: track an explicit count, or deliberately sacrifice one slot.
• Storing values instead of indices in the monotonic deque. You need indices to check whether the front has expired from the window — values alone can't tell you their position in the original array.
• Using a queue when order doesn't matter. If you only need 'give me any pending item', a stack is equally correct and faster; if you need 'most urgent first', use a priority queue, not FIFO.

When to use each: choosing your service order

Practice problems

1. Implement a queue using two stacks: support enqueue and dequeue, each amortized O(1). Hint: an 'inbox' stack and an 'outbox' stack.
2. Sliding window maximum: given an integer array and window size k, return the array of window maximums. Solve in O(n) using a monotonic deque.
3. First unique character in a stream: process characters one at a time and after each insertion report the first character seen exactly once. Hint: a queue plus a frequency map.

Key takeaways

• Queues are FIFO — fairness by arrival order — and power scheduling, buffering, and breadth-first search.
• The circular buffer's modulo-wrapped indices deliver O(1) at both ends with zero shifting; it's the workhorse behind library queues and systems ring buffers.
• A deque opens both ends in O(1) and generalizes both stack and queue.
• The monotonic deque solves sliding-window max/min in amortized O(n) — evict from the back what can never win, expire from the front what has aged out.
• Choosing among stack/queue/deque/priority queue is choosing a service order: newest, oldest, either end, or most important.

Next lesson turns to the stack no one writes but everyone uses: recursion and the call stack — how function calls actually work and how to reason about recursive complexity. Practice queue and deque questions in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play