Queue

Queues turn the simple concept of “waiting in line” into a powerful programming tool. They enable us to process elements in the order they arrive, making them essential for breadth-first search, task scheduling, and real-time data streams.

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The first element added to the queue is the first one to be removed. Think of it like a single-lane checkout line at a store: the first person in line gets served first, and new people join at the back.

The two primary operations are:

• Enqueue: Add an element to the rear of the queue
• Dequeue: Remove an element from the front of the queue

Real-World Analogy

Imagine a ticket counter at a movie theater. When people arrive for tickets, they form a line. The person at the front of the line buys their ticket and leaves first. New arrivals join at the back of the line. This is exactly how a queue works: elements are processed in the exact order they arrived.

How a Queue Works

Let’s visualize the queue operations step by step. We start with an empty queue and add elements one by one.

  graph TD
    subgraph Initial State
        A[Empty Queue]
    end

    subgraph Enqueue 5
        B1[Enqueue 5] --> B2[Queue: 5]
    end

    subgraph Enqueue 10
        C1[Enqueue 10] --> C2[Queue: 5, 10]
    end

    subgraph Enqueue 15
        D1[Enqueue 15] --> D2[Queue: 5, 10, 15]
    end

    subgraph Dequeue
        E1[Dequeue] --> E2[Returns 5]
        E2 --> E3[Queue: 10, 15]
    end

    A --> B1
    B2 --> C1
    C2 --> D1
    D2 --> E1

Notice how elements enter from the rear and leave from the front. The front pointer always points to the next element to be removed, while the rear pointer points to where new elements will be added.

Queue Variations

Circular Queue

In a standard array-based queue, removing elements from the front creates empty spaces that go unused. A circular queue solves this by wrapping around to the beginning of the array when reaching the end. This efficient reuse of space is ideal for bounded queues.

  graph LR
    subgraph Array[Array of size 5]
        direction LR
        A0[0] --- A1[1] --- A2[2] --- A3[3] --- A4[4]
    end

    subgraph State1[After enqueuing 3 elements]
        F[Front: 0] --> |points to| A1
        R[Rear: 2] --> |points to| A3
        A1[10] --- A2[20] --- A3[30]
    end

    subgraph State2[After 2 dequeues, rear wraps]
        F[Front: 2] --> |points to| A3
        R[Rear: 4] --> |points to| A0
        A3[30] --- A4[40] --- A0[50]
    end

Priority Queue

A priority queue doesn’t strictly follow FIFO. Instead, elements are dequeued based on their priority. The highest (or lowest) priority element is removed first, regardless of when it was enqueued. Priority queues are typically implemented using heaps.

Deque (Double-Ended Queue)

A deque extends the queue by allowing insertions and deletions at both ends. This flexibility makes it perfect for sliding window problems where you need efficient access to both the newest and oldest elements in a window.

When to Use This Pattern

Use a queue when:

• You need to process elements in the exact order they arrive (FIFO)

• You’re implementing a breadth-first search (BFS) on a graph or tree

• You need level-order traversal of a tree structure

• You’re managing a bounded buffer with circular queue behavior

• You need to find the shortest path in an unweighted graph

• You’re implementing sliding window algorithms with deques

• You need topological sorting (Kahn’s algorithm)

• Task scheduling requires processing in arrival order

• You’re building systems like print queues, message queues, or job schedulers

Complexity Analysis

Time Complexity Derivation:

• Array Queue: Enqueue is O(1) amortized because we only add to the end. Dequeue is O(n) due to shifting all remaining elements.
• Circular Queue: Both operations are O(1) because we use modular arithmetic and maintain front/rear pointers.
• Priority Queue: Operations are O(log n) because we must maintain heap property after each modification.
• Space Complexity: O(n) for unbounded queues, O(k) for circular queues with fixed capacity k.

Common Mistakes

1. Using array shift for dequeue: The shift() operation in JavaScript removes the first element and shifts all others, making dequeue O(n). Use a circular queue or deque library instead.

2. Forgetting to mark visited in BFS: When implementing BFS, you must mark a node as visited before enqueuing it, not after dequeuing. This prevents the same node from being added multiple times and causing infinite loops.

3. Confusing queue with stack: Remember, queues use FIFO (like a line), while stacks use LIFO (like a stack of plates). Using the wrong one leads to incorrect traversal order.

4. Not handling empty queue edge cases: Always check if the queue is empty before attempting to dequeue or peek. Returning null or throwing an appropriate exception is essential.

5. Priority queue misunderstanding: A priority queue is not the same as a regular queue with priorities. Elements are removed based on priority, not arrival time.

6. Circular queue overflow/underflow: Forgetting to check isFull() before enqueue or isEmpty() before dequeue in circular queues leads to undefined behavior.

Next Steps

Ready to put queues into action? Head over to our Code Templates to see reusable implementations across multiple programming languages, then practice with our curated Practice Problems.