Day 11: Queue Data Structure Explained Simply

Why does fairness in computer systems—from your printer jobs to Uber ride matching—rely on the exact same line discipline as a coffee shop counter?


In 30 Seconds

A Queue is a linear data structure built on fairness: FIFO (**First-In, First-Out** [the oldest item waiting in line is always the very first item served]). New elements enter exclusively at the back (enqueue), and existing elements leave exclusively from the front (dequeue). Unlike a stack where newcomers cut to the top, a queue guarantees every task is processed in the exact order it arrived.


The Real-World Analogy: The Coffee Shop Drive-Thru Lane

Imagine cars pulling into a single-lane coffee shop drive-thru.

  • The first car to enter rolls up to the pickup window at the Front.
  • New cars line up neatly at the Rear—nobody can cut to the window.
  • Once the barista hands coffee to the front car, that car drives away (dequeue), and the second car becomes the new front of the line.

Picture This

Here is a visual diagram illustrating the two-ended FIFO flow of a Queue with FRONT and REAR pointers:

DEQUEUE 101 FRONT 102 103 104 REAR ENQUEUE First-In, First-Out (FIFO): Items enter at REAR and exit from FRONT
                  DEQUEUE (Leave)                 ENQUEUE (Enter)
                      ^                                |
                      |                                v
               +------+------+------+------+------+------+
   FRONT  ---> | 101  | 102  | 103  | 104  | 105  | 106  | <---  REAR
               +------+------+------+------+------+------+
               (Oldest)                           (Newest)

And here is why using a plain array without a circular wrap-around or linked nodes wastes space:

  Naive Array Queue after 2 dequeues:
  Index:    [  0  ]   [  1  ]   [  2  ]   [  3  ]
  Values:   | None|   | None|   | 103 |   | 104 |
                                   ^         ^
                                 FRONT      REAR

How It Actually Works

  1. Avoid the Naive Array Trap: Calling list.pop(0) shifts every remaining item left, turning $O(1)$ into slow $O(N)$ work.
  2. Use Linked Nodes or deque: Maintain dedicated front and rear pointers for true $O(1)$ speed at both ends.
  3. Enqueue at the Rear ($O(1)$): Attach the new item right behind rear, then slide rear onto the new item.
  4. Dequeue from the Front ($O(1)$): Grab the value at front, advance front forward, and return the served value.

Show Me The Code

# Day 11: O(1) Queue Implemented from Scratch in Python

class QNode:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = None   # Oldest item (next to leave)
        self.rear = None    # Newest item (last to arrive)
        self._size = 0

    def enqueue(self, item):
        """Adds a new item to the rear of the queue in O(1) constant time."""
        new_node = QNode(item)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
        self._size += 1

    def dequeue(self):
        """Removes and returns the front item in O(1) constant time."""
        if self.is_empty():
            raise IndexError("Queue Underflow: Cannot dequeue from an empty queue.")

        served_value = self.front.data
        self.front = self.front.next

        if self.front is None:
            self.rear = None

        self._size -= 1
        return served_value

    def peek(self):
        return None if self.is_empty() else self.front.data

    def is_empty(self):
        return self.front is None


if __name__ == "__main__":
    print_jobs = Queue()
    print_jobs.enqueue("Resume.pdf")
    print_jobs.enqueue("BoardingPass.pdf")
    print("Next to print:", print_jobs.peek())      # Output: Resume.pdf
    print("Printing now:", print_jobs.dequeue())    # Output: Resume.pdf

Dry Run

StepAction TakenQueue State (FRONT -> REAR)Output / Return
1enqueue("A")FRONT -> ["A"] <- REARNone
2enqueue("B")FRONT -> ["A"] -> ["B"] <- REARNone
3dequeue()FRONT -> ["B"] <- REARReturns "A"
4peek()FRONT -> ["B"] <- REARReturns "B"

Speed & Memory

OperationBest CaseAverage CaseWorst CaseWhy?
Enqueue (Insert at Rear)$O(1)$$O(1)$$O(1)$Direct pointer update at rear.
Dequeue (Remove at Front)$O(1)$$O(1)$$O(1)$Direct pointer advance at front.
Peek (Front Lookup)$O(1)$$O(1)$$O(1)$Reads front.data directly.

Where You'll See It In Real Life

  • Office Printer Spoolers: Documents line up in a FIFO queue so pages print in arrival order.
  • Customer Support Call Centers: Callers placed on hold are answered in strict waiting order.
  • Message Brokers (Kafka / RabbitMQ): Incoming web requests queue up so backend servers process orders smoothly without crashing.

Traps To Avoid

  • Trap 1: Using Python's list.pop(0) to implement a queue.
    Fix: Always use collections.deque (popleft()) or linked nodes for $O(1)$ performance.
  • Trap 2: Forgetting to reset self.rear = None when the last item is dequeued.
    Fix: Whenever self.front becomes None, explicitly set self.rear = None.
  • Trap 3: Confusing a Queue (FIFO) with a Stack (LIFO).
    Fix: Stacks reverse order; Queues preserve arrival order.

Practice

  1. Easy: Simulate a hot-potato circle game where $N$ players pass a potato $K$ times per round using a queue.
  2. Medium: Implement a Queue using two Stacks with amortized $O(1)$ operations.
  3. Hard: Generate all binary numbers from 1 to N as strings using a Queue. (Hint: Enqueue "1", then repeatedly dequeue s and enqueue s+"0" and s+"1".)

TL;DR

  • A Queue follows FIFO (**First-In, First-Out**): items enter at the rear and leave from the front.
  • Using linked nodes or collections.deque keeps both enqueue and dequeue at $O(1)$ constant time.
  • Queues power task schedulers, print spoolers, breadth-first searches, and web traffic buffers.

References Consulted


Covered Log Update

Already covered: [Big-O notation, Arrays, Two Pointers, Strings, Sliding Window, Prefix Sums, Recursion basics, Singly Linked List, Doubly Linked List, Stack, Queue]