Day 11: Queue Data Structure | FIFO Principles & O(1) Implementation
Understand FIFO scheduling, O(1) enqueue/dequeue operations, and real-world buffers.
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 (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
- Avoid the Naive Array Trap: Calling
list.pop(0)shifts every remaining item left, turning $O(1)$ into slow $O(N)$ work. - Use Linked Nodes or
deque: Maintain dedicatedfrontandrearpointers for true $O(1)$ speed at both ends. - Enqueue at the Rear ($O(1)$): Attach the new item right behind
rear, then sliderearonto the new item. - Dequeue from the Front ($O(1)$): Grab the value at
front, advancefrontforward, 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
| Step | Action Taken | Queue State (FRONT -> REAR) | Output / Return |
|---|---|---|---|
| 1 | enqueue("A") | FRONT -> ["A"] <- REAR | None |
| 2 | enqueue("B") | FRONT -> ["A"] -> ["B"] <- REAR | None |
| 3 | dequeue() | FRONT -> ["B"] <- REAR | Returns "A" |
| 4 | peek() | FRONT -> ["B"] <- REAR | Returns "B" |
Speed & Memory
| Operation | Best Case | Average Case | Worst Case | Why? |
|---|---|---|---|---|
| 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 usecollections.deque(popleft()) or linked nodes for $O(1)$ performance. - Trap 2: Forgetting to reset
self.rear = Nonewhen the last item is dequeued.
Fix: Wheneverself.frontbecomesNone, explicitly setself.rear = None. - Trap 3: Confusing a Queue (FIFO) with a Stack (LIFO).
Fix: Stacks reverse order; Queues preserve arrival order.
Practice
- Easy: Simulate a hot-potato circle game where $N$ players pass a potato $K$ times per round using a queue.
- Medium: Implement a
Queueusing two Stacks with amortized $O(1)$ operations. - Hard: Generate all binary numbers from
1toNas 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.dequekeeps bothenqueueanddequeueat $O(1)$ constant time. - Queues power task schedulers, print spoolers, breadth-first searches, and web traffic buffers.
References Consulted
- GeeksforGeeks - Queue Data Structure — referenced for verification — all content above is original.
- Programiz - Queue Data Structure and Implementation — referenced for verification — all content above is original.
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]