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.

Practice

1. What does FIFO stand for in the context of a queue?

easy

A. First In, Final Output

B. Fast Input, Fast Output

C. Fast In, Fast Out

D. First In, First Out

Solution

1. Step 1: Understand FIFO meaning

   FIFO means the first element added to the queue is the first one to be removed.

2. Step 2: Match the acronym

   First In, First Out exactly matches FIFO.

3. Final Answer:

   First In, First Out -> Option D

4. Quick Check:

   FIFO = First In, First Out [OK]

Hint: Remember queue removes items in order added [OK]

Common Mistakes:

• Confusing FIFO with LIFO
• Thinking FIFO means last in first out
• Mixing up acronym meanings

2. Which of the following is the correct way to add an element '5' to a queue named q in Python using the queue.Queue module?

easy

A. q.put(5)

B. q.push(5)

C. q.enqueue(5)

D. q.add(5)

Solution

1. Step 1: Recall queue.Queue methods

   The Python queue.Queue class uses put() to add elements.

2. Step 2: Identify correct method

   enqueue(), push(), and add() are not valid methods for queue.Queue.

3. Final Answer:

   q.put(5) -> Option A

4. Quick Check:

   Use put() to add in queue.Queue [OK]

Hint: Use put() to add items in Python queue.Queue [OK]

Common Mistakes:

• Using enqueue() which is not in queue.Queue
• Using push() from stack terminology
• Using add() which is not a queue method

3. What will be the output of the following Python code using a list as a queue?

q = []
q.append(10)
q.append(20)
q.append(30)
print(q.pop(0))
print(q)

medium

A. 10
[20, 30]

B. 30
[10, 20]

C. 10
[30, 20]

D. 20
[10, 30]

Solution

1. Step 1: Understand list as queue

   Appending adds to the end: q = [10, 20, 30].

2. Step 2: pop(0) removes first element

   pop(0) removes and returns 10, leaving q = [20, 30].

3. Final Answer:

   10 [20, 30] -> Option A

4. Quick Check:

   pop(0) removes first = 10 [OK]

Hint: pop(0) removes first item in list acting as queue [OK]

Common Mistakes:

• Thinking pop() removes last item
• Confusing append with insert
• Expecting pop(0) to remove last element

4. Identify the error in the following code snippet that tries to implement a queue using a list:

q = []
q.pop()
q.append(1)
print(q)

medium

A. pop() removes last element but queue removes first

B. pop() on empty list causes error

C. append() should be before pop()

D. print() syntax is incorrect

Solution

1. Step 1: Check pop() on empty list

   Initially q is empty, so q.pop() causes IndexError.

2. Step 2: Confirm other statements

   append(1) and print(q) are correct syntax and order does not fix pop on empty.

3. Final Answer:

   pop() on empty list causes error -> Option B

4. Quick Check:

   pop() empty list = IndexError [OK]

Hint: Don't pop from empty list; causes error [OK]

Common Mistakes:

• Ignoring empty list before pop
• Thinking pop() removes first element
• Assuming append order fixes error

5. You have a queue that initially contains [1, 2, 3]. You perform these operations:

q.append(4)
first = q.pop(0)
q.append(first * 10)
print(q)

What is the final state of the queue?

hard

A. [1, 2, 3, 4, 10]

B. [2, 3, 4, 40]

C. [2, 3, 4, 10]

D. [2, 3, 4, 1]

Solution

1. Step 1: Initial queue and append

   Start with q = [1, 2, 3]. After q.append(4), q = [1, 2, 3, 4].

2. Step 2: pop(0) removes first element

   first = q.pop(0) removes 1, so first = 1 and q = [2, 3, 4].

3. Step 3: append first * 10

   q.append(1 * 10) adds 10, so q = [2, 3, 4, 10].

4. Final Answer:

   [2, 3, 4, 10] -> Option C

5. Quick Check:

   Remove first, add 10 times it at end [OK]

Hint: Pop first, multiply, append result at end [OK]

Common Mistakes:

• Appending before popping first
• Multiplying wrong element
• Not updating queue after pop