Queue Concept and FIFO Principle in DSA Python

Mental Model

A queue is a line where the first person in is the first person out. We add items at the back and remove from the front.

Analogy: Imagine waiting in line at a coffee shop. The first person to get in line is the first to get served and leave the line.

front -> [item1] -> [item2] -> [item3] -> back -> null

Dry Run Walkthrough

Input: Start with empty queue, enqueue 1, enqueue 2, enqueue 3, then dequeue once

Goal: Show how items enter at the back and leave from the front following FIFO

Step 1: enqueue 1 to empty queue

front -> [1] -> back -> null

Why: We add the first item; front and back both point to it

Step 2: enqueue 2 at back

front -> [1] -> [2] -> back -> null

Why: Add new item at back, keep front at first item

Step 3: enqueue 3 at back

front -> [1] -> [2] -> [3] -> back -> null

Why: Add another item at back, queue grows

Step 4: dequeue from front

front -> [2] -> [3] -> back -> null

Why: Remove first item entered, front moves to next item

Result:

front -> [2] -> [3] -> back -> null

Annotated Code

DSA Python

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.back = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.back is None:
            self.front = new_node
            self.back = new_node
            return
        self.back.next = new_node
        self.back = new_node

    def dequeue(self):
        if self.front is None:
            return None
        removed_value = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.back = None
        return removed_value

    def __str__(self):
        values = []
        current = self.front
        while current:
            values.append(str(current.value))
            current = current.next
        return ' -> '.join(values) + ' -> null'

queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.dequeue()
print(queue)

if self.back is None:

check if queue is empty to set front and back to new node

self.back.next = new_node

link new node at the end of queue

self.back = new_node

update back pointer to new node

if self.front is None:

check if queue is empty before dequeue

self.front = self.front.next

move front pointer forward to remove first node

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

if queue becomes empty after dequeue, reset back pointer

Output

2 -> 3 -> null

Complexity Analysis

Time: O(1) because enqueue and dequeue only change pointers without traversing the queue

Space: O(n) because space grows linearly with number of items stored

vs Alternative: Compared to arrays where removing first element requires shifting all others O(n), queue linked list allows O(1) removal from front

Edge Cases

dequeue from empty queue

returns None and does not crash

DSA Python

if self.front is None:

enqueue first element to empty queue

front and back both point to the new node

DSA Python

if self.back is None:

dequeue last element making queue empty

front and back both reset to None

DSA Python

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

When to Use This Pattern

When you see a problem requiring first-in-first-out order, reach for the queue pattern because it naturally models waiting lines and ordered processing.

Common Mistakes

Mistake: Updating only the front pointer on dequeue but not resetting back when queue becomes empty
Fix: Add check to reset back pointer to None when front becomes None after dequeue

Summary

A queue stores items in order and removes them in the same order (FIFO).

Use a queue when you need to process items in the order they arrive, like tasks or requests.

The key insight is adding at the back and removing from the front keeps order simple and efficient.