4.1 Introduction to Queue

What is a Queue?

A queue is a linear data structure in which:

• Insertion is done at one end
• Deletion is done from the other end

Queue follows the principle:

FIFO – First In, First Out

📌 The element inserted first is removed first.

---

Real-Life Examples

• People standing in a queue
• Printer queue
• Ticket booking system
• CPU scheduling
• Call center requests

---

Queue Terminology

• Front → Position from where deletion occurs
• Rear → Position where insertion occurs
• Overflow → Queue is full
• Underflow → Queue is empty

---

Diagram (Conceptual)

FRONT → | 10 | 20 | 30 | ← REAR
(Delete)             (Insert)

---

4.2 Operations on Queue

1️⃣ ENQUEUE (Insertion)

• Adds an element at the rear
• Causes overflow if queue is full

2️⃣ DEQUEUE (Deletion)

• Removes an element from the front
• Causes underflow if queue is empty

3️⃣ PEEK / FRONT

• Returns the front element without removing it

4️⃣ DISPLAY

• Shows all queue elements

---

Error Conditions

Condition	Meaning
Overflow	Inserting into a full queue
Underflow	Deleting from an empty queue

---

4.3 Implementation of Queue using Python

Queues are implemented using lists in Python (NCERT method).

---

🔸 Linear Queue Using List (Menu Driven)

queue = []
MAX = 5

def enqueue():
    if len(queue) == MAX:
        print("Queue Overflow")
    else:
        item = int(input("Enter element: "))
        queue.append(item)
        print("Inserted:", item)

def dequeue():
    if len(queue) == 0:
        print("Queue Underflow")
    else:
        print("Deleted:", queue.pop(0))

def peek():
    if len(queue) == 0:
        print("Queue is empty")
    else:
        print("Front element:", queue[0])

def display():
    if len(queue) == 0:
        print("Queue is empty")
    else:
        print("Queue elements:", queue)

while True:
    print("\n1.Enqueue 2.Dequeue 3.Peek 4.Display 5.Exit")
    ch = int(input("Enter choice: "))
    if ch == 1:
        enqueue()
    elif ch == 2:
        dequeue()
    elif ch == 3:
        peek()
    elif ch == 4:
        display()
    elif ch == 5:
        break
    else:
        print("Invalid choice")

📌 Very important board practical program

---

Limitation of Linear Queue

• Wasted space after deletions
• Solved using Circular Queue (theory only in CBSE)

---

4.4 Introduction to Deque

What is a Deque?

A Deque (Double Ended Queue) allows:

• Insertion at both ends
• Deletion from both ends

📌 Unlike normal queue, deque is more flexible.

---

Types of Deque

1️⃣ Input Restricted Deque

• Insertion at one end
• Deletion at both ends

2️⃣ Output Restricted Deque

• Insertion at both ends
• Deletion at one end

---

Diagram

Insert/Delete ← | 10 | 20 | 30 | → Insert/Delete

---

4.5 Implementation of Deque Using Python

Deque can be implemented using list or collections.deque.

---

🔸 Deque Using List (NCERT Style)

deque = []

def insert_front(item):
    deque.insert(0, item)
    print("Inserted at front:", item)

def insert_rear(item):
    deque.append(item)
    print("Inserted at rear:", item)

def delete_front():
    if len(deque) == 0:
        print("Deque Underflow")
    else:
        print("Deleted from front:", deque.pop(0))

def delete_rear():
    if len(deque) == 0:
        print("Deque Underflow")
    else:
        print("Deleted from rear:", deque.pop())

def display():
    print("Deque elements:", deque)

insert_front(10)
insert_rear(20)
insert_front(5)
display()
delete_rear()
delete_front()
display()

---

🔸 Deque Using collections Module (Extra Knowledge)

from collections import deque

dq = deque()
dq.append(10)
dq.appendleft(5)
dq.pop()
dq.popleft()
print(dq)

📌 Mentioned in NCERT but list-based preferred in exams

---

📝 Queue vs Stack (Very Important Comparison)

Stack	Queue
LIFO	FIFO
One end	Two ends
Push/Pop	Enqueue/Dequeue
Used in recursion	Used in scheduling

---

🧠 NCERT EXAM SUMMARY (Must Learn)

• Queue follows FIFO
• Enqueue → insertion at rear
• Dequeue → deletion from front
• Overflow → full queue
• Underflow → empty queue
• Deque allows operations at both ends
• Stack ≠ Queue (very common question)

Board-Level Solved Programs (10 Programs)

---

Program 1: Create a Queue Using List

queue = []
queue.append(10)
queue.append(20)
queue.append(30)

print("Queue:", queue)

📌 Concept: Queue creation using list

---

Program 2: Enqueue Operation (Insertion)

queue = []

def enqueue(item):
    queue.append(item)
    print("Inserted:", item)

enqueue(10)
enqueue(20)
enqueue(30)
print(queue)

📌 Concept: Insertion at rear

---

Program 3: Dequeue Operation (Deletion)

queue = [10, 20, 30]

def dequeue():
    if len(queue) == 0:
        print("Queue Underflow")
    else:
        print("Deleted:", queue.pop(0))

dequeue()
print(queue)

📌 Concept: Deletion from front

---

Program 4: Queue Overflow Condition

queue = []
MAX = 3

def enqueue(item):
    if len(queue) == MAX:
        print("Queue Overflow")
    else:
        queue.append(item)

enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)
print(queue)

📌 Concept: Overflow check

---

Program 5: Queue Underflow Condition

queue = []

if len(queue) == 0:
    print("Queue Underflow")
else:
    queue.pop(0)

📌 Concept: Underflow check

---

Program 6: Display Front Element (Peek)

queue = [5, 10, 15]

if len(queue) == 0:
    print("Queue is empty")
else:
    print("Front element:", queue[0])

📌 Concept: Peek operation

---

Program 7: Display Queue Elements

queue = [10, 20, 30, 40]

print("Queue elements:")
for item in queue:
    print(item)

📌 Concept: Traversal

---

Program 8: Menu-Driven Queue Program

queue = []

while True:
    print("\n1.Enqueue 2.Dequeue 3.Display 4.Exit")
    ch = int(input("Enter choice: "))

    if ch == 1:
        item = int(input("Enter element: "))
        queue.append(item)
    elif ch == 2:
        if len(queue) == 0:
            print("Queue Underflow")
        else:
            print("Deleted:", queue.pop(0))
    elif ch == 3:
        print("Queue:", queue)
    elif ch == 4:
        break
    else:
        print("Invalid choice")

📌 VERY IMPORTANT practical program

---

Program 9: Deque – Insert at Front and Rear

dq = []

dq.insert(0, 10)   # insert front
dq.append(20)     # insert rear
dq.insert(0, 5)

print("Deque:", dq)

📌 Concept: Deque insertion

---

Program 10: Deque – Delete from Front and Rear

dq = [5, 10, 20, 30]

print("Deleted from front:", dq.pop(0))
print("Deleted from rear:", dq.pop())
print("Deque:", dq)

📌 Concept: Deque deletion

---

Case-Study Questions (CBSE 2025 Pattern)

---

Case Study 1: Printer Queue System

A printer processes print jobs in the order they are received.

Questions:

1. Which data structure is used? ✔ Queue

2. Which principle does it follow? ✔ FIFO

3. Write a Python program to simulate printer queue.

   queue = []
   
   def add_job(job):
   queue.append(job)
   
   def process_job():
   if len(queue) == 0:
       print("No jobs to process")
   else:
       print("Processing:", queue.pop(0))
   
   add_job("Doc1")
   add_job("Doc2")
   process_job()
   process_job()
   

---

Case Study 2: Call Centre Management

A call centre handles incoming calls in the order received.

Questions:

1. Which queue operation removes a call? ✔ Dequeue

2. What happens if no calls are present? ✔ Underflow

3. Write a Python function to remove calls safely.

   def handle_call(queue):
   if len(queue) == 0:
       print("No calls waiting")
   else:
       print("Handling call:", queue.pop(0))
   

---

Case Study 3: Railway Reservation Counter

Passengers are served one by one at a reservation counter.

Questions:

1. Why is stack not suitable here? ✔ Stack follows LIFO, but passengers must be served FIFO.

2. What type of queue allows insertion and deletion at both ends? ✔ Deque

3. Write code to demonstrate deque usage.

   dq = []
   dq.append("P1")
   dq.append("P2")
   dq.insert(0, "VIP")
   
   print(dq)
   

---