Chapter 4: Queue

CBSE Unit: NOT in current CBSE syllabus (2025-26) Status: Supplementary, may be added in future syllabus updates Priority: PREPARE, strong candidate for syllabus inclusion (natural extension of Stack)

---

Key Concepts

4.1 What is a Queue?

• Linear data structure following FIFO (First In First Out) principle, Also called FCFS (First Come First Served), Elements added at REAR (tail) and removed from FRONT (head), Think: people in a bank line, cars at a toll booth, train ticket waiting list

4.2 Stack vs Queue

Feature	Stack	Queue
Principle	LIFO (Last In First Out)	FIFO (First In First Out)
Insert end	TOP	REAR
Remove end	TOP (same end)	FRONT (opposite end)
Insert operation	PUSH	ENQUEUE
Remove operation	POP	DEQUEUE
Real-life analogy	Stack of plates	People in a line
Use case	Undo/Redo, recursion	Job scheduling, print queue

Key difference: In a stack, insertion and deletion happen at the same end (TOP). In a queue, insertion happens at REAR and deletion happens at FRONT (opposite ends).

4.3 Applications

Real-life:

• Train ticket waiting list (W/L1 confirmed first), Customer service call queue (IVRS hold), Vehicles at toll booth / fuel pump, Students in morning assembly line, Patients waiting at a hospital (first come, first served), Passengers boarding a bus in order

Computer Science:

• Web server handling concurrent requests, OS job scheduling (FIFO basis for processor access), Print queue (multiple print jobs from shared printer), Keyboard buffer (keystrokes processed in order), BFS (Breadth First Search) in graphs/trees, Messaging systems and task queues

4.4 Queue Operations

Operation	Description	Exception
ENQUEUE	Insert element at REAR	Overflow (queue full)
DEQUEUE	Remove element from FRONT	Underflow (queue empty)
PEEK / FRONT	View FRONT element without removing	Underflow (queue empty)
IS EMPTY	Check if queue is empty	-
IS FULL	Check if queue is full (fixed-size only)	-
SIZE	Count elements	-

4.5 Enqueue and Dequeue Trace

Let us trace a sequence of operations on an initially empty queue:

Operations: Enqueue(10), Enqueue(20), Enqueue(30), Dequeue(), Enqueue(40), Dequeue(), Peek()

Step	Operation	Queue (front -> rear)	Returned Value	front	rear
1	Enqueue(10)	[10]	-	10	10
2	Enqueue(20)	[10, 20]	-	10	20
3	Enqueue(30)	[10, 20, 30]	-	10	30
4	Dequeue()	[20, 30]	10	20	30
5	Enqueue(40)	[20, 30, 40]	-	20	40
6	Dequeue()	[30, 40]	20	30	40
7	Peek()	[30, 40]	30	30	40

Another trace, testing underflow:

Step	Operation	Queue	Returned Value	Note
1	Enqueue('A')	['A']	-
2	Enqueue('B')	['A', 'B']	-
3	Dequeue()	['B']	'A'	FIFO: 'A' came first
4	Dequeue()	[]	'B'	Queue now empty
5	Dequeue()	[]	UNDERFLOW	Cannot dequeue from empty queue

4.6 Implementation in Python Using List

myQueue = list()

def enqueue(myQueue, element):
    myQueue.append(element)       # add at REAR (end of list)

def isEmpty(myQueue):
    return len(myQueue) == 0

def dequeue(myQueue):
    if not isEmpty(myQueue):
        return myQueue.pop(0)     # remove from FRONT (index 0)
    else:
        print("Underflow! Queue is empty")
        return None

def size(myQueue):
    return len(myQueue)

def peek(myQueue):
    if isEmpty(myQueue):
        print("Queue is empty")
        return None
    else:
        return myQueue[0]         # view FRONT element

def display(myQueue):
    if isEmpty(myQueue):
        print("Queue is empty")
    else:
        print("Queue (front -> rear):", myQueue)

Key: append() adds at rear, pop(0) removes from front. This is the fundamental difference from stack where both operations happen at the same end.

4.7 Implementation Using List with Separate Functions (Detailed)

queue = []

def enqueue(queue, item):
    """Add item to the rear of the queue"""
    queue.append(item)
    print(f"Enqueued: {item}")

def dequeue(queue):
    """Remove and return item from the front of the queue"""
    if len(queue) == 0:
        print("Underflow! Queue is empty")
        return None
    else:
        item = queue.pop(0)
        print(f"Dequeued: {item}")
        return item

def peek(queue):
    """Return front element without removing"""
    if len(queue) == 0:
        print("Queue is empty")
        return None
    else:
        return queue[0]

def display(queue):
    """Display all elements from front to rear"""
    if len(queue) == 0:
        print("Queue is empty")
    else:
        print("Front ->", end=" ")
        for item in queue:
            print(item, end=" ")
        print("<- Rear")

def size(queue):
    """Return number of elements in queue"""
    return len(queue)

# --- Testing ---
enqueue(queue, 10)       # Enqueued: 10
enqueue(queue, 20)       # Enqueued: 20
enqueue(queue, 30)       # Enqueued: 30
display(queue)           # Front -> 10 20 30 <- Rear
print("Size:", size(queue))  # Size: 3
print("Front:", peek(queue)) # Front: 10
dequeue(queue)           # Dequeued: 10
dequeue(queue)           # Dequeued: 20
display(queue)           # Front -> 30 <- Rear
dequeue(queue)           # Dequeued: 30
dequeue(queue)           # Underflow! Queue is empty

4.8 Queue Using collections.deque (Efficient)

Python's list.pop(0) is O(n) because all elements must shift left. For better performance, use collections.deque which provides O(1) operations at both ends.

from collections import deque

queue = deque()

# Enqueue
queue.append('A')       # deque(['A'])
queue.append('B')       # deque(['A', 'B'])
queue.append('C')       # deque(['A', 'B', 'C'])

# Dequeue
item = queue.popleft()  # 'A' -  O(1) operation!
print(item)             # A
print(queue)            # deque(['B', 'C'])

# Peek
print(queue[0])         # B (front element)

# Size
print(len(queue))       # 2

Why deque is better:

Operation	list	deque
Enqueue (append)	O(1)	O(1)
Dequeue (pop from front)	O(n), pop(0) shifts all	O(1), popleft()
Peek (front element)	O(1), queue[0]	O(1), queue[0]

4.9 Queue of Fixed Size

Sometimes we need a queue with a maximum capacity (e.g., printer can hold only 5 jobs):

class FixedQueue:
    def __init__(self, capacity):
        self.queue = []
        self.capacity = capacity
    
    def is_empty(self):
        return len(self.queue) == 0
    
    def is_full(self):
        return len(self.queue) == self.capacity
    
    def enqueue(self, item):
        if self.is_full():
            print("Overflow! Queue is full")
        else:
            self.queue.append(item)
            print(f"Enqueued: {item}")
    
    def dequeue(self):
        if self.is_empty():
            print("Underflow! Queue is empty")
            return None
        else:
            return self.queue.pop(0)
    
    def display(self):
        if self.is_empty():
            print("Queue is empty")
        else:
            print("Queue:", self.queue)

# Usage
q = FixedQueue(3)
q.enqueue(10)      # Enqueued: 10
q.enqueue(20)      # Enqueued: 20
q.enqueue(30)      # Enqueued: 30
q.enqueue(40)      # Overflow! Queue is full
q.display()        # Queue: [10, 20, 30]

4.10 Deque (Double Ended Queue), Pronounced as "deck", Addition/removal from both ends (front and rear), Can simulate both stack and queue, Applications: browser history (stack-like), undo/redo, palindrome checking

from collections import deque

dq = deque()
dq.append('a')        # add at rear      -> deque(['a'])
dq.appendleft('b')    # add at front     -> deque(['b', 'a'])
dq.append('c')        # add at rear      -> deque(['b', 'a', 'c'])
dq.appendleft('d')    # add at front     -> deque(['d', 'b', 'a', 'c'])

print(dq)             # deque(['d', 'b', 'a', 'c'])

dq.pop()              # remove from rear  -> 'c'
dq.popleft()          # remove from front -> 'd'

print(dq)             # deque(['b', 'a'])

Deque as both Stack and Queue:

If you use...	It behaves like...
append() + pop()	Stack (LIFO), both at rear
appendleft() + popleft()	Stack (LIFO), both at front
append() + popleft()	Queue (FIFO), rear in, front out
appendleft() + pop()	Queue (FIFO), front in, rear out

Deque operations summary:

Operation	Description
append(x)	Add x to the right (rear) end
appendleft(x)	Add x to the left (front) end
pop()	Remove and return from right (rear)
popleft()	Remove and return from left (front)
dq[0]	Peek at front
dq[-1]	Peek at rear
len(dq)	Number of elements

4.11 Practical Application: Palindrome Checker Using Deque

from collections import deque

def is_palindrome(word):
    dq = deque(word.lower())
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

print(is_palindrome("madam"))    # True
print(is_palindrome("hello"))    # False
print(is_palindrome("racecar"))  # True

---

Important Programs

Menu-driven queue program (Complete)

queue = []
while True:
    print("\n===== QUEUE OPERATIONS =====")
    print("1. Enqueue")
    print("2. Dequeue")
    print("3. Peek (view front)")
    print("4. Display queue")
    print("5. Size of queue")
    print("6. Exit")
    ch = int(input("Enter your choice: "))
    
    if ch == 1:
        item = input("Enter element to enqueue: ")
        queue.append(item)
        print(f"'{item}' enqueued successfully")
    elif ch == 2:
        if queue:
            removed = queue.pop(0)
            print(f"Dequeued: '{removed}'")
        else:
            print("Underflow! Queue is empty")
    elif ch == 3:
        if queue:
            print(f"Front element: '{queue[0]}'")
        else:
            print("Queue is empty")
    elif ch == 4:
        if queue:
            print("Queue (front -> rear):", queue)
        else:
            print("Queue is empty")
    elif ch == 5:
        print(f"Queue size: {len(queue)}")
    elif ch == 6:
        print("Exiting...")
        break
    else:
        print("Invalid choice!")

Queue of integers with sum and average

queue = []

def enqueue(queue, item):
    queue.append(item)

def dequeue(queue):
    if queue:
        return queue.pop(0)
    return None

def queue_sum(queue):
    return sum(queue)

def queue_avg(queue):
    if queue:
        return sum(queue) / len(queue)
    return 0

# Add some numbers
for num in [10, 25, 30, 15, 20]:
    enqueue(queue, num)

print("Queue:", queue)                    # [10, 25, 30, 15, 20]
print("Sum:", queue_sum(queue))           # 100
print("Average:", queue_avg(queue))       # 20.0

dequeue(queue)                            # removes 10
print("After dequeue:", queue)            # [25, 30, 15, 20]
print("New average:", queue_avg(queue))   # 22.5

Simulating a print queue

from collections import deque
import random

print_queue = deque()

# Simulate adding print jobs
jobs = ["Report.pdf", "Letter.docx", "Invoice.xlsx", "Photo.jpg", "Notes.txt"]
for job in jobs:
    pages = random.randint(1, 20)
    print_queue.append((job, pages))
    print(f"Added to queue: {job} ({pages} pages)")

print(f"\nTotal jobs in queue: {len(print_queue)}")

# Process print jobs (FIFO)
print("\n--- Processing Print Queue ---")
while print_queue:
    job_name, pages = print_queue.popleft()
    print(f"Printing: {job_name} ({pages} pages)... Done")

print("All jobs completed!")

Queue with string elements (student names)

admission_queue = []

def add_student(queue, name):
    queue.append(name)
    print(f"  {name} joined the queue. Position: {len(queue)}")

def process_student(queue):
    if queue:
        name = queue.pop(0)
        print(f"  Processing admission for: {name}")
        return name
    else:
        print("  No students in queue!")
        return None

def display_queue(queue):
    if queue:
        print("  Current queue:", " -> ".join(queue))
    else:
        print("  Queue is empty")

# Simulate admission day
print("--- Admission Queue ---")
add_student(admission_queue, "Aarav")
add_student(admission_queue, "Priya")
add_student(admission_queue, "Rahul")
add_student(admission_queue, "Sneha")
display_queue(admission_queue)

print("\n--- Processing ---")
process_student(admission_queue)
process_student(admission_queue)
display_queue(admission_queue)

---

Important Definitions

Term	Definition
Queue	Linear data structure following FIFO (First In First Out) principle
FIFO	First In First Out, element inserted first is removed first
Enqueue	Operation to add an element at the rear of the queue
Dequeue	Operation to remove an element from the front of the queue
Front	The end of the queue from which elements are removed
Rear	The end of the queue at which elements are added
Peek	View the front element without removing it
Overflow	Error when trying to enqueue into a full queue (fixed-size)
Underflow	Error when trying to dequeue from an empty queue
Deque	Double-ended queue, allows insertion/deletion at both ends

---

Key Points Students Miss

1. Queue removes from FRONT, stack removes from TOP, don't confuse
2. pop(0) for dequeue, pop() (no argument) for stack pop, argument matters!
3. In Python, pop(0) is O(n), for production code, use collections.deque with popleft()
4. Deque is NOT the same as queue, deque allows operations at both ends
5. If insertion and deletion happen from same end of deque, it behaves as a stack
6. Always check for underflow before dequeue and overflow before enqueue (fixed-size)
7. Queue maintains insertion order - the order elements were added is preserved
8. append() is the same for both stack and queue, the difference is in removal (pop() vs pop(0))

---

Board Exam Tips

1. If asked to "implement queue using list", use append() for enqueue and pop(0) for dequeue
2. Always handle the underflow condition in dequeue, marks are deducted if you skip this
3. For tracing questions, draw the queue state after each operation as shown in the trace table
4. Know the difference between stack and queue, it is a very common 2-mark question
5. The term "FIFO" alone is not enough, explain it as "First In First Out" and relate to real-life example
6. If asked about deque, clearly state it supports operations at BOTH ends (not just one)