Previous Topic

What Is a Queue?

A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle: the earliest inserted element is the first one removed. Think of a line at a ticket counter—people are served in the order they arrive.

Core Operations

• enqueue(x): Insert element x at the back (tail) of the queue.
• dequeue(): Remove and return the element at the front (head). Often raises underflow if empty.
• front() / peek(): Return the element at the front without removing it.
• isEmpty(): Return whether the queue has no elements.
• size(): Return the number of elements.

How Queues Work

Queues maintain two conceptual ends: a front from which elements are removed, and a rear to which new elements are added. This ordering naturally supports workflows where tasks arrive over time and must be processed in arrival order.

Implementations

• Array-based: Fixed-size or dynamic arrays with head and tail indices. Circular buffering avoids shifting elements.
• Linked list: Nodes linked in sequence with pointers to head and tail; grows until memory limits.
• Circular queue: Array where head/tail wrap around using modular arithmetic.
• Two-stack queue: Implements FIFO using two LIFO stacks, achieving amortized O(1) enqueue/dequeue.

Algorithmic Complexity

• enqueue: O(1) average; O(n) worst if resizing (dynamic array).
• dequeue: O(1) average; O(n) worst if shifting (avoid by circular buffer or linked list).
• peek/front: O(1).
• space: O(n) for n stored elements.

Variants and Related Structures

• Deque (double-ended queue): Insert/remove at both ends.
• Priority queue: Removes highest-priority element first (not strictly FIFO; often implemented with a heap).
• Blocking queue: Thread-safe queue where enqueue/dequeue can block until space/data is available.
• Lock-free/Wait-free queues: Concurrency-friendly queues using atomic operations for high throughput.

Common Use Cases

• Scheduling: CPU round-robin scheduling, print spoolers, task dispatchers.
• Traversal: Breadth-first search (BFS) in graphs and level-order traversal in trees.
• Buffering: I/O buffers, network packet queues, streaming data pipelines.
• Producer-consumer: Decoupling data producers from consumers in concurrent systems.
• Messaging: Message queues in distributed, event-driven architectures.

Concurrency and Systems Considerations

• Thread safety: Use synchronized or lock-free queues to avoid race conditions.
• Backpressure: Bounded queues help signal when producers outpace consumers.
• Fairness: FIFO ordering provides predictable service; priority or weighted queues can tune fairness vs. latency.
• Throughput vs. latency: Batch dequeueing can improve throughput at the cost of per-item latency.

Example Pseudocode

// Interface
Queue:
  enqueue(x)
  y = dequeue()
  y = front()
  b = isEmpty()
  n = size()

// Breadth-First Search using a queue
function BFS(graph, start):
  q ← new Queue()
  visited ← empty set
  enqueue(q, start)
  add start to visited
  while not isEmpty(q):
    v ← dequeue(q)
    for each u in graph.neighbors(v):
      if u not in visited:
        add u to visited
        enqueue(q, u)

Gotchas and Best Practices

• Underflow/overflow: Check for empty on dequeue/peek; for bounded queues, check for full on enqueue.
• Circular buffer bugs: Watch off-by-one errors and correct modulo arithmetic.
• Amortized vs. worst-case: Understand resizing costs for dynamic arrays.
• Memory management: In linked implementations, ensure nodes are properly freed or garbage-collected.

Comparison to Stacks

Stacks are LIFO (last-in, first-out) and support backtracking and function call management; queues are FIFO and support fair scheduling and level-wise processing. Many systems use both, each where its ordering semantics best fit the problem.

Next Topic