Module F-7·14 min read

FIFO structure, circular queues, and the queueing patterns behind message brokers and job schedulers.

JJS

Written by Jatin Jain Saraf · Senior Software Engineer

Module F-7 — Queues: FIFO, Circular Queues, and Job Scheduling

Q: Why is `array.shift()` an O(n) operation when used to dequeue from a plain array-backed queue, and how does the `Queue` class with `head`/`tail` pointers avoid that cost?

`shift()` is O(n) because it must move every remaining element one position to the left to keep the array contiguous; the pointer-based `Queue` avoids this by never physically moving elements — it just advances a `head` index to mark removed slots. — `shift()` removes the first element and then must move every subsequent element one position left to keep the array's contents contiguous — this is the same cost analysis from Module F-2 applied to a queue's dequeue operation. The pointer-based `Queue` class sidesteps this entirely: instead of moving remaining elements, it advances a `head` index to logically mark earlier slots as removed, without touching any other element's position — turning dequeue into genuine O(1). Option B fabricates a browser-vs-Node.js distinction that isn't the actual reason and isn't mentioned in the module. Option C directly contradicts the module, which explicitly states the pointer-based approach achieves O(1), a different complexity class from O(n), not merely a constant-factor improvement. Option D invents an irrelevant sorting step that has nothing to do with queue operations.

Q: In the `CircularQueue` implementation, what specific role does the expression `(this.tail + 1) % this.capacity` play?

It wraps the `tail` index back to 0 once it reaches the end of the fixed-size buffer, allowing previously-dequeued slots near the beginning of the array to be reused instead of requiring the buffer to keep growing. — The modulo operation is what makes the queue "circular" — once `tail` would go past the last valid index, the modulo wraps it back to 0, letting the queue reuse buffer slots that have already been freed by earlier dequeues, rather than requiring unbounded new memory. This is explicitly contrasted in the module with the unbounded, ever-growing `head`/`tail` version that precedes it. Option A invents an unrelated hashing concept that has nothing to do with circular queues. Option C is incorrect — a circular queue's whole purpose is to stay at a fixed capacity; it explicitly returns `false` from `enqueue` when full rather than growing, unlike the dynamic array resizing from Module F-2. Option D dismisses a mechanism the module presents as functionally central to how the structure works, not merely defensive.

Q: In the `MovingAverage` class, why does maintaining a running `sum` (adjusted incrementally on each call) matter for performance, compared to recomputing the sum of the current window from scratch on every call to `next()`?

Recomputing the sum from scratch on every call would cost O(windowSize) per call, whereas incrementally adding the new value and subtracting the dropped value keeps each call to O(1), regardless of how large the window is. — If `next()` recomputed the sum of every value currently in the window from scratch each time, that would cost O(windowSize) per call — expensive if called repeatedly on a large window. By instead adding only the newly arrived value and subtracting only the value that just aged out, the running `sum` stays accurate with a fixed, small amount of work per call — O(1), independent of window size. This mirrors the module's broader point about queues: avoid re-deriving a result from scratch when you can incrementally maintain it as items enter and leave. Option A dismisses a real, stated performance distinction as mere style. Option C fabricates a nonexistent JavaScript restriction — arrays can be summed as many times as desired. Option D invents an irrelevant claim about `reduce`'s deprecation status, which is both false and unrelated to why the running sum is used here.

What this module covers: Where a stack processes the most recent item first, a queue processes the oldest item first — first in, first out. This module covers the queue as an abstract data type, why the obvious array-based implementation is quietly O(n) per operation, the circular buffer that fixes it, and why message brokers and job schedulers are built on queues rather than stacks.

The Queue: First-In, First-Out

A queue supports enqueue (add to the back) and dequeue (remove from the front) — the exact opposite access pattern from a stack. Whatever was added first is the first thing that comes back out.

typescript

interface QueueLike<T> {
  enqueue(item: T): void;
  dequeue(): T | undefined;
  peek(): T | undefined;
  isEmpty(): boolean;
}

Analogy: A queue is a line at a counter. New arrivals join at the back; whoever has been waiting longest is served next, from the front. Nobody gets served out of order just because they're standing closer to the front of the physical line by accident — position in the queue is exactly the order of arrival.

The Naive Implementation's Hidden Cost

The obvious approach — a plain array, push() to enqueue, shift() to dequeue — looks correct and is correct. It's also quietly expensive:

typescript

class NaiveQueue<T> {
  private items: T[] = [];

  enqueue(item: T): void {
    this.items.push(item); // O(1) — Module F-2: appending at the end
  }

  dequeue(): T | undefined {
    return this.items.shift(); // O(n) — Module F-2: removing from the front shifts everything left
  }
}

This is the exact insertion/deletion cost distinction from Module F-2: push() is O(1) because it only touches the end, but shift() is O(n) because every remaining element has to move one position to the left to stay contiguous. A queue implemented this way is O(n) per dequeue — fine for a handful of items, a measurable bottleneck once a queue is processing thousands of jobs.

Fixing It: Two Pointers Instead of Physical Shifting

The fix doesn't require a different memory layout — it requires not physically moving elements at all. Instead of shifting everything left after a dequeue, just move a pointer forward to mark "everything before here has already been removed":

typescript

class Queue<T> {
  private items: Record<number, T> = {};
  private head = 0;
  private tail = 0;

  enqueue(item: T): void {
    this.items[this.tail] = item;
    this.tail++; // O(1) — just advance the back pointer
  }

  dequeue(): T | undefined {
    if (this.head === this.tail) return undefined; // empty
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++; // O(1) — just advance the front pointer, nothing shifts
    return item;
  }

  peek(): T | undefined {
    return this.items[this.head];
  }

  isEmpty(): boolean {
    return this.head === this.tail;
  }
}

Both enqueue and dequeue are now genuinely O(1) — no element is ever physically moved. The cost of this approach is that head and tail grow forever in an unbounded queue; in practice, this is fine for most application code (the numbers are just array/object indices, and modern runtimes handle large integers without issue), but a fixed-capacity version needs one more idea: wrapping around.

The Circular Queue

A circular queue uses a fixed-size backing array and wraps head/tail back to the start using the modulo operator once they reach the end — reusing freed-up slots instead of growing forever.

typescript

class CircularQueue<T> {
  private buffer: (T | undefined)[];
  private head = 0;
  private tail = 0;
  private size = 0;

  constructor(private capacity: number) {
    this.buffer = new Array(capacity);
  }

  enqueue(item: T): boolean {
    if (this.size === this.capacity) return false; // full
    this.buffer[this.tail] = item;
    this.tail = (this.tail + 1) % this.capacity; // wrap around at the boundary
    this.size++;
    return true;
  }

  dequeue(): T | undefined {
    if (this.size === 0) return undefined; // empty
    const item = this.buffer[this.head];
    this.head = (this.head + 1) % this.capacity; // wrap around at the boundary
    this.size--;
    return item;
  }
}

(this.tail + 1) % this.capacity is the whole trick: once tail reaches the end of the buffer, the modulo wraps it back to index 0, reusing a slot that's already been dequeued rather than allocating more memory. This is exactly the "fixed-size ring, reuse behind the moving front" structure behind bounded in-memory buffers — audio/video streaming buffers, rate limiters tracking "requests in the last N seconds" (Module F-9 covers the sliding-window version of this problem), and fixed-size log/event ring buffers that overwrite their oldest entry once full.

A Practical Pattern: Moving Average from a Stream

A queue is the natural structure for "the average of the last N values I've seen," because it needs exactly what a queue provides: cheap removal of the oldest value the moment a new one arrives.

typescript

class MovingAverage {
  private queue: number[] = [];
  private sum = 0;

  constructor(private windowSize: number) {}

  next(value: number): number {
    this.queue.push(value);
    this.sum += value;

    if (this.queue.length > this.windowSize) {
      this.sum -= this.queue.shift()!; // drop the oldest value out of the window
    }

    return this.sum / this.queue.length;
  }
}

const ma = new MovingAverage(3);
ma.next(1); // 1
ma.next(10); // 5.5
ma.next(3); // 4.67
ma.next(5); // (10 + 3 + 5) / 3 = 6 — the 1 has aged out of the window

This runs the queue's oldest-value-first-out property directly: as each new value arrives, the running sum absorbs it and sheds whatever fell outside the window — no re-summing the whole window from scratch on every call. Module F-9 (Sliding Window) generalizes this exact "expand on one side, contract on the other, maintain a running total" shape well beyond averages.

Where This Shows Up in Your Stack

Message brokers — SQS, RabbitMQ, Redis Streams, Kafka — are, at the conceptual level, exactly this structure at scale: producers enqueue messages, consumers dequeue and process them in (roughly) arrival order, with the broker handling the durability and distribution a simple in-memory queue doesn't need to.
BullMQ and job queues: jobs are enqueued and processed FIFO by default (oldest job first) — the opposite of the LIFO mode covered in Module F-6, which BullMQ also supports for the cases where "most recent" should jump the line.
The Node.js event loop's callback queues: the macrotask queue (timers, I/O callbacks) and the microtask queue (resolved Promises) are both processed FIFO — callbacks registered earlier generally run before ones registered later, within the same queue. Module F-12's capstone covers this in full.
Pagination: "give me the next 20 rows after this cursor" is conceptually dequeuing a batch from the front of an ordered stream, without needing to have the entire result set loaded into memory at once.
Level-order tree traversal (Module P-4) and breadth-first graph search (Module A-5) are both built directly on a queue — visit a node, enqueue its children, and the FIFO order guarantees you finish an entire "layer" before moving to the next one.

Summary

A queue is enqueue at the back, dequeue from the front — FIFO, the mirror image of a stack's LIFO.
The naive array + shift() implementation is O(n) per dequeue, because removing from the front shifts every remaining element — the same cost identified for unshift/shift back in Module F-2.
The fix is two pointers (head/tail) instead of physically shifting elements — both enqueue and dequeue become genuinely O(1).
A circular queue bounds memory with a fixed-size buffer, wrapping indices with modulo ((index + 1) % capacity) to reuse freed slots instead of growing forever.
Moving averages and rate limiting both lean on "drop the oldest as a new one arrives" — the queue's core property, generalized further by the sliding window pattern next.
This structure underlies message brokers, job queues, the event loop's callback queues, pagination, and breadth-first traversal — all covered directly or built on in later modules.

The next module, Two-Pointer Technique, formalizes a pattern that's already appeared twice — array reversal (Module F-2) and the head/tail pointers in this module's efficient queue — into a general-purpose tool for collapsing O(n²) problems into O(n).

Knowledge Check

Why is array.shift() an O(n) operation when used to dequeue from a plain array-backed queue, and how does the Queue class with head/tail pointers avoid that cost?

In the CircularQueue implementation, what specific role does the expression (this.tail + 1) % this.capacity play?

In the MovingAverage class, why does maintaining a running sum (adjusted incrementally on each call) matter for performance, compared to recomputing the sum of the current window from scratch on every call to next()?

Test your knowledge with more question sets

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

PreviousModule F-6: Stacks: LIFO, the Call Stack, and Expression Parsing Next Module F-8: Two-Pointer Technique

Discussion

Join the discussion

Loading comments...