Queues

A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle: the first element added is the first element removed. Think of any orderly line — a queue at a coffee shop, a printer waiting to process jobs, or a list of network packets waiting to be transmitted. The person who joined first is served first. No cutting.

Queues are deceptively simple, yet they underpin some of the most important algorithms in computer science — Breadth-First Search, operating system schedulers, and every request/response cycle on the web starts with a queue somewhere.

The FIFO Principle

Two fundamental operations define a queue:

Enqueue — add an element to the back (rear) of the queue
Dequeue — remove and return the element from the front of the queue
Peek / Front — read the front element without removing it
isEmpty — check whether the queue has no elements

Here is a visual walkthrough. Imagine the queue grows to the right and is consumed from the left:

Text

Initial state (empty):
  front -> [ ] <- rear

Enqueue(10):
  front -> [10] <- rear

Enqueue(20):
  front -> [10, 20] <- rear

Enqueue(30):
  front -> [10, 20, 30] <- rear

Dequeue() -> returns 10:
  front -> [20, 30] <- rear

Dequeue() -> returns 20:
  front -> [30] <- rear

Peek() -> returns 30 (no removal):
  front -> [30] <- rear

Note

Contrast this with a **stack** (LIFO — Last In First Out). A stack is a pile of plates where you add and remove from the same end. A queue is a tunnel where you enter from one end and exit from the other.

Real-World Analogies

Analogy	Enqueue	Dequeue	Who goes first
Checkout line at a store	Customer joins the back	Cashier serves the front	Customer who arrived first
Printer queue	New print job added	Printer processes next job	Job submitted first
CPU scheduling (Round Robin)	Process added to run queue	Scheduler picks next process	Process waiting longest
Web server request queue	Incoming HTTP request	Worker thread picks it up	Earliest request
Keyboard buffer	Key press stored	OS reads next character	Key pressed first

Naive Array Implementation (and Its Problem)

The most natural implementation uses a plain array. Enqueue pushes to the end — that is O(1). But dequeue removes from index 0, which forces the entire array to shift left — that is O(n). For large queues with frequent dequeues this is a serious bottleneck.

class NaiveQueue {
  constructor() {
    this.data = []
  }

  // O(1) — push appends to end
  enqueue(value) {
    this.data.push(value)
  }

  // O(n) — shift removes index 0 and slides every element left
  dequeue() {
    if (this.isEmpty()) throw new Error('Queue is empty')
    return this.data.shift()   // <-- THIS is the problem
  }

  peek() {
    if (this.isEmpty()) throw new Error('Queue is empty')
    return this.data[0]
  }

  isEmpty() {
    return this.data.length === 0
  }

  size() {
    return this.data.length
  }
}

const q = new NaiveQueue()
q.enqueue('A')
q.enqueue('B')
q.enqueue('C')
console.log(q.dequeue())   // 'A'  — but internally shifts B and C left
console.log(q.peek())      // 'B'
console.log(q.size())      // 2

A
B
2

Warning

Array.prototype.shift() is O(n) because JavaScript engines store arrays in contiguous memory. Removing element 0 requires moving every subsequent element one slot to the left. On a queue of 1 million items, each dequeue touches 1 million memory locations. Use a circular buffer or linked list instead.

Circular Array Implementation — O(1) Everything

A circular (ring) buffer avoids shifting entirely. Instead of moving data, we move two integer pointers — front and rear — and let them wrap around using the modulo operator. The array itself never changes position; only the indices advance.

Text

Capacity = 5 slots (indices 0-4)

After enqueue(A), enqueue(B), enqueue(C):
  [ A, B, C, _, _ ]
    ^           ^
  front=0     rear=3  (next write position)

After dequeue() -> A:
  [ _, B, C, _, _ ]
       ^        ^
    front=1   rear=3

After enqueue(D), enqueue(E):
  [ _, B, C, D, E ]
       ^        ^
    front=1  rear=0  (wrapped around!)

After enqueue(F)  — rear wraps to slot 0:
  [ F, B, C, D, E ]
    ^  ^
  rear=1  front=1  -> FULL

The array is treated as a circle. Pointer math: (index + 1) % capacity

class CircularQueue {
  constructor(capacity) {
    this.capacity = capacity
    this.data = new Array(capacity)
    this.front = 0       // index of the element to dequeue next
    this.rear = 0        // index where the next enqueue writes
    this.count = 0       // number of elements currently stored
  }

  // O(1)
  enqueue(value) {
    if (this.isFull()) throw new Error('Queue overflow')
    this.data[this.rear] = value
    this.rear = (this.rear + 1) % this.capacity
    this.count++
  }

  // O(1)
  dequeue() {
    if (this.isEmpty()) throw new Error('Queue underflow')
    const value = this.data[this.front]
    this.data[this.front] = undefined   // help GC
    this.front = (this.front + 1) % this.capacity
    this.count--
    return value
  }

  // O(1)
  peek() {
    if (this.isEmpty()) throw new Error('Queue is empty')
    return this.data[this.front]
  }

  isEmpty() { return this.count === 0 }
  isFull()  { return this.count === this.capacity }
  size()    { return this.count }

  // Utility: print elements in logical order
  toString() {
    if (this.isEmpty()) return '[]'
    const result = []
    for (let i = 0; i < this.count; i++) {
      result.push(this.data[(this.front + i) % this.capacity])
    }
    return '[' + result.join(', ') + ']'
  }
}

const q = new CircularQueue(4)
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
console.log(q.toString())     // [10, 20, 30]
console.log(q.dequeue())      // 10
q.enqueue(40)
q.enqueue(50)                 // rear wraps around
console.log(q.toString())     // [20, 30, 40, 50]
console.log(q.isFull())       // true
console.log(q.size())         // 4

[10, 20, 30]
10
[20, 30, 40, 50]
true
4

Tip

The circular buffer is the queue implementation used in production systems — OS kernel ring buffers, network driver queues, audio processing pipelines. Fixed capacity is usually fine because the system has a defined maximum backlog anyway.

Linked List Implementation — Dynamic O(1)

When you need a queue without a fixed capacity limit, a singly linked list with a tail pointer gives you O(1) enqueue and O(1) dequeue with no wasted pre-allocated space.

The key insight: maintain a head pointer for fast dequeue (remove from front) and a tail pointer for fast enqueue (append to back).

class Node {
  constructor(value) {
    this.value = value
    this.next = null
  }
}

class LinkedQueue {
  constructor() {
    this.head = null   // front — dequeue from here
    this.tail = null   // back  — enqueue here
    this.count = 0
  }

  // O(1) — append new node at tail
  enqueue(value) {
    const node = new Node(value)
    if (this.tail !== null) {
      this.tail.next = node
    }
    this.tail = node
    if (this.head === null) {
      this.head = node   // first element: head and tail point to same node
    }
    this.count++
  }

  // O(1) — remove node at head
  dequeue() {
    if (this.isEmpty()) throw new Error('Queue is empty')
    const value = this.head.value
    this.head = this.head.next
    if (this.head === null) {
      this.tail = null   // queue became empty
    }
    this.count--
    return value
  }

  // O(1)
  peek() {
    if (this.isEmpty()) throw new Error('Queue is empty')
    return this.head.value
  }

  isEmpty() { return this.count === 0 }
  size()    { return this.count }
}

const q = new LinkedQueue()
q.enqueue('first')
q.enqueue('second')
q.enqueue('third')
console.log(q.peek())      // 'first'
console.log(q.dequeue())   // 'first'
console.log(q.dequeue())   // 'second'
console.log(q.size())      // 1
console.log(q.dequeue())   // 'third'
console.log(q.isEmpty())   // true

first
first
second
1
third
true

BFS — The Canonical Queue Application

Breadth-First Search is arguably the most important algorithm that uses a queue. BFS explores a graph level by level — all nodes at distance 1, then all at distance 2, and so on. The queue ensures nodes are processed in the exact order they were discovered.

// BFS on an undirected graph represented as an adjacency list
function bfs(graph, startNode) {
  const visited = new Set()
  const queue = new LinkedQueue()   // or any queue implementation
  const order = []

  visited.add(startNode)
  queue.enqueue(startNode)

  while (!queue.isEmpty()) {
    const node = queue.dequeue()
    order.push(node)

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor)
        queue.enqueue(neighbor)
      }
    }
  }

  return order
}

// Example: social network — who is 2 hops from Alice?
const graph = {
  Alice:   ['Bob', 'Carol'],
  Bob:     ['Alice', 'Dave', 'Eve'],
  Carol:   ['Alice', 'Frank'],
  Dave:    ['Bob'],
  Eve:     ['Bob'],
  Frank:   ['Carol'],
}

console.log(bfs(graph, 'Alice'))
// Explores level by level:
//   Level 0: Alice
//   Level 1: Bob, Carol
//   Level 2: Dave, Eve, Frank

[ 'Alice', 'Bob', 'Carol', 'Dave', 'Eve', 'Frank' ]

Note

BFS with a queue finds the **shortest path** (in terms of number of edges) between two nodes in an unweighted graph. The first time BFS reaches a destination node, that path is guaranteed to be the shortest. This is used in social networks ("degrees of separation"), word ladders, and maze solving.

Level-Order Tree Traversal

A special case of BFS, level-order traversal visits every node in a binary tree row by row. This is used to serialize trees, calculate tree width, and find cousins of a node.

function levelOrder(root) {
  if (!root) return []
  const result = []
  const queue = [root]

  while (queue.length > 0) {
    const levelSize = queue.length    // snapshot: how many nodes on this level
    const level = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()      // dequeue
      level.push(node.val)
      if (node.left)  queue.push(node.left)   // enqueue children
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

// Tree:
//        1
//       / \
//      2   3
//     / \   \
//    4   5   6

// levelOrder(root) -> [[1], [2, 3], [4, 5, 6]]

Job Scheduling and Rate Limiting

Queues are the backbone of any system that must buffer and process tasks asynchronously. Web servers, message brokers (Kafka, RabbitMQ, SQS), and background job frameworks all model work as queues.

// Simple token-bucket rate limiter using a queue of timestamps
class RateLimiter {
  constructor(maxRequests, windowMs) {
    this.maxRequests = maxRequests
    this.windowMs = windowMs
    this.timestamps = []   // acts as a sliding-window queue
  }

  // Returns true if request is allowed, false if throttled
  allow() {
    const now = Date.now()
    const windowStart = now - this.windowMs

    // Dequeue all timestamps outside the current window
    while (this.timestamps.length > 0 && this.timestamps[0] < windowStart) {
      this.timestamps.shift()
    }

    if (this.timestamps.length < this.maxRequests) {
      this.timestamps.push(now)
      return true    // request allowed
    }
    return false     // rate limit exceeded
  }
}

// Allow 5 requests per second
const limiter = new RateLimiter(5, 1000)
for (let i = 0; i < 8; i++) {
  console.log(`Request ${i + 1}: ${limiter.allow() ? 'ALLOWED' : 'THROTTLED'}`)
}

Request 1: ALLOWED
Request 2: ALLOWED
Request 3: ALLOWED
Request 4: ALLOWED
Request 5: ALLOWED
Request 6: THROTTLED
Request 7: THROTTLED
Request 8: THROTTLED

Priority Queue — A Smarter Queue

A priority queue extends the basic queue concept: instead of FIFO, elements are dequeued in order of their priority (highest or lowest first). Under the hood, priority queues are typically implemented with a binary heap, giving O(log n) enqueue and O(log n) dequeue.

// Min-heap priority queue (smallest priority dequeues first)
class PriorityQueue {
  constructor() {
    this.heap = []
  }

  enqueue(value, priority) {
    this.heap.push({ value, priority })
    this._bubbleUp(this.heap.length - 1)
  }

  dequeue() {
    if (this.isEmpty()) throw new Error('Empty')
    const top = this.heap[0]
    const last = this.heap.pop()
    if (this.heap.length > 0) {
      this.heap[0] = last
      this._sinkDown(0)
    }
    return top.value
  }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2)
      if (this.heap[parent].priority <= this.heap[i].priority) break
      ;[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]]
      i = parent
    }
  }

  _sinkDown(i) {
    const n = this.heap.length
    while (true) {
      let smallest = i
      const left = 2 * i + 1
      const right = 2 * i + 2
      if (left < n && this.heap[left].priority < this.heap[smallest].priority) smallest = left
      if (right < n && this.heap[right].priority < this.heap[smallest].priority) smallest = right
      if (smallest === i) break
      ;[this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]]
      i = smallest
    }
  }

  isEmpty() { return this.heap.length === 0 }
}

// CPU scheduler example — lower number = higher priority
const scheduler = new PriorityQueue()
scheduler.enqueue('Background sync', 10)
scheduler.enqueue('User input handler', 1)    // highest priority
scheduler.enqueue('Network fetch', 5)
scheduler.enqueue('Animation frame', 2)

console.log(scheduler.dequeue())   // User input handler  (priority 1)
console.log(scheduler.dequeue())   // Animation frame     (priority 2)
console.log(scheduler.dequeue())   // Network fetch       (priority 5)
console.log(scheduler.dequeue())   // Background sync     (priority 10)

User input handler
Animation frame
Network fetch
Background sync

Complexity Summary

Implementation	Enqueue	Dequeue	Peek	Space
Naive array (shift)	O(1)	O(n)	O(1)	O(n)
Circular array	O(1)	O(1)	O(1)	O(capacity)
Linked list (with tail pointer)	O(1)	O(1)	O(1)	O(n)
Priority queue (binary heap)	O(log n)	O(log n)	O(1)	O(n)

Common Queue Applications

Use Case	Why a Queue	Variant
Breadth-First Search	Process nodes level by level in discovery order	Standard FIFO queue
CPU task scheduling	Round-robin: each process gets a time slice in order	Circular queue
Print spooler	Documents print in submission order	Standard FIFO queue
Web server requests	Handle requests in arrival order	Bounded circular buffer
Message broker (Kafka/SQS)	Decouple producer and consumer, buffer bursts	Persistent distributed queue
Rate limiter	Sliding window of request timestamps	Deque (double-ended)
Dijkstra's shortest path	Process nodes by current known distance	Min-heap priority queue
OS I/O scheduler	Schedule disk reads/writes by priority	Priority queue

JavaScript Built-In

JavaScript arrays can act as a simple queue using push (enqueue) and shift (dequeue). For small queues this is fine. For performance-critical code, use a circular buffer or linked list as shown above.

// Quick-and-dirty queue with a plain array
const queue = []

queue.push('first')    // enqueue
queue.push('second')
queue.push('third')

console.log(queue.shift())   // dequeue -> 'first'
console.log(queue[0])        // peek    -> 'second'
console.log(queue.length)    // size    -> 2

// Fine for small N, but shift() is O(n).
// For large queues, prefer CircularQueue or LinkedQueue.

When to Use a Queue

You need to process items in the exact order they arrived
You are implementing BFS or level-order traversal
You are building a scheduler, print spooler, or job processor
You need to decouple a producer from a consumer (buffering)
You are implementing a sliding window over a stream of data
You need a rate limiter based on a time window

Summary

A queue is a FIFO structure: first in, first out
Core operations: enqueue (back), dequeue (front), peek, isEmpty
Naive array dequeue is O(n) due to shifting — avoid for large queues
Circular array gives O(1) for all operations at the cost of fixed capacity
Linked list gives O(1) for all operations with dynamic capacity
Priority queues use a heap to dequeue by priority in O(log n)
BFS, job scheduling, rate limiting, and buffering all rely on queues

Note

Up next: **Deque (Double-Ended Queue)** — a generalization of the queue that allows O(1) insertions and deletions from both ends, enabling algorithms like the Sliding Window Maximum.