Lesson 2 � Beginner

Queue & Deque: FIFO ka Power

Queue stack ka ulta hai � jo pehle aaya hai wo pehle jaayega (FIFO). Jaise bank mein line � pehle aaya pehle serve. Python mein collections.deque se efficient queue banti hai. BFS, task scheduling, aur circular buffer � sab queue pe based hain.

? 22 min✓ Beginner✓ Stack basics

Queue kya hai?

WHAT

Queue ek linear data structure hai jisme insertion ek end se hoti hai (rear/back) aur deletion doosre end se (front). Jise FIFO � First In, First Out kehte hain. Jo sabse pehle aaya hai wo sabse pehle nikalta hai. Stack ke bilkul ulta.

WHEN

Jab tumhe elements ko order mein process karna ho � jaise BFS traversal, task scheduling, printer queue, ya buffer management. Jab "pehle aaya pehle jaayega" ka scene ho � queue use karo.

WHERE

BFS graph traversal, OS process scheduling, printer spooling, message queues (RabbitMQ, Kafka), event handling, buffer I/O � sab queue pe based hain.

Mental Model: Imagine karo bank mein line lagi hai. Jo sabse pehle aaya hai wo sabse pehle counter pe jaayega. Naya aadmi line ke peeche lagega. Queue bhi aise hi kaam karta hai � front se nikalo, rear se daalo.

# Queue ka visual representation
# enqueue(10) ? [10]
# enqueue(20) ? [10, 20]
# enqueue(30) ? [10, 20, 30]
# dequeue() ? [20, 30] (10 nikla � pehle aaya tha)
# dequeue() ? [30] (20 nikla)

# Front = pehle element = 20 (ab)
# Rear = last element = 30

Python deque � Best way to make Queue

Python list se queue banana possible hai but inefficient hai � pop(0) O(n) hota hai. collections.deque use karo � dono taraf se O(1) insertion/deletion:

from collections import deque

# Queue banao using deque
q = deque()

# ENQUEUE � rear pe element daalo
q.append(10)
q.append(20)
q.append(30)
print(q) # deque([10, 20, 30])

# DEQUEUE � front se element nikalo
front = q.popleft()
print(front) # 10 (jo pehle aaya tha)
print(q) # deque([20, 30])

# PEEK � front element dekho
print(q[0]) # 20

# SIZE
print(len(q)) # 2

# IS EMPTY
print(len(q) == 0) # False

deque vs list

List ka pop(0) O(n) hai kyunki sab elements shift hote hain. Deque ka popleft() O(1) hai � doubly linked list pe based hai. Hamesha queue ke liye deque use karo.

deque ka faayda

Deque dono taraf se O(1) insertion/deletion deta hai. Isliye ye stack aur queue dono ban sakti hai. Python mein sabse versatile linear data structure hai.

Kab list use karein?

Agar sirf end pe insert/delete karna hai (stack) toh list kaafi hai. Agar front se operations chahiye toh deque use karo. List random access ke liye better hai.

Why deque? Python ki list contiguous memory block hai. Jab tum pop(0) karte ho toh baaki sab elements ek position shift hote hain � O(n). Deque doubly linked list hai � har node alag memory mein hai, sirf pointers change hote hain � O(1).

Circular Queue Concept

Normal queue mein ek problem hai � time ke saath queue aage badhti jaati hai aur piche space waste hoti hai. Circular queue mein last position first ko connect hota hai:

# Circular Queue � space reuse karta hai
# Imagine: [_, _, 30, 40, _] mein agar 50 aaye toh
# 50 first position pe jaayega: [50, _, 30, 40, _]

class CircularQueue:
 def __init__(self, capacity):
 self.queue = [None] * capacity
 self.capacity = capacity
 self.front = 0
 self.rear = -1
 self.size = 0
 
 def enqueue(self, item):
 if self.size == self.capacity:
 print("Queue full!")
 return
 self.rear = (self.rear + 1) % self.capacity
 self.queue[self.rear] = item
 self.size += 1
 
 def dequeue(self):
 if self.size == 0:
 print("Queue empty!")
 return None
 item = self.queue[self.front]
 self.front = (self.front + 1) % self.capacity
 self.size -= 1
 return item

cq = CircularQueue(3)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
print(cq.dequeue()) # 10
cq.enqueue(40) # 40 first position pe jaayega
print(cq.queue) # [40, 20, 30]

Interview Tip: Circular queue ka concept samajh lo � (rear + 1) % capacity aur (front + 1) % capacity. Ye pattern circular buffer aur ring buffer mein use hota hai. Modulo operator se index wrap around hota hai.

Real-World Queue Uses

from collections import deque

# USE CASE 1: BFS Traversal (Graph)
def bfs(graph, start):
 visited = set()
 queue = deque([start])
 visited.add(start)
 result = []
 
 while queue:
 node = queue.popleft()
 result.append(node)
 for neighbor in graph[node]:
 if neighbor not in visited:
 visited.add(neighbor)
 queue.append(neighbor)
 return result

# USE CASE 2: Task Scheduling (Round Robin)
tasks = deque(["Task1", "Task2", "Task3", "Task4"])
time_slice = 2
for _ in range(len(tasks)):
 current = tasks.popleft()
 print(f"Running {current} for {time_slice}ms")
 tasks.append(current) # Wapas line mein laga do

# USE CASE 3: Sliding Window Maximum
def max_sliding_window(nums, k):
 q = deque() # indices store karenge
 result = []
 for i in range(len(nums)):
 while q and q[0] < i - k + 1:
 q.popleft()
 while q and nums[q[-1]] < nums[i]:
 q.pop()
 q.append(i)
 if i >= k - 1:
 result.append(nums[q[0]])
 return result

Try it: code khud likho

Exercise

Question: Two stacks se queue implement karo. Queue mein [1, 2, 3] enqueue karo aur 2 baar dequeue karo. Answer mein dequeued elements likho (comma-separated, jaise "1,2").

Question: Simple graph: {'A': ['B','C'], 'B': ['D'], 'C': [], 'D': []} ka BFS traversal karo starting from 'A'. Answer mein traversal order likho (jaise "A,B,C,D").

Common mistakes

List se queue banana: Python list se pop(0) mat karo � O(n) hai. Hamesha collections.deque use karo queues ke liye.
deque mein indexing galat: Deque mein q[0] se front access karte ho but q[-1] se rear. popleft() front se nikalta hai, pop() rear se.
Circular queue mein wrap-around bhool jaana: Modulo operator use karna bhool jana � (rear + 1) % capacity. Bina modulo ke index out of bounds aayega.
Thread safety: Multi-threaded environment mein deque thread-safe nahi hai. queue.Queue use karo threads ke liye � usme locks lage hote hain.

Lesson complete?

Queue & Deque samajh aa gaye✓ Ab Monotonic Stack seekhte hain � ye stack ka advanced pattern hai jo interview mein bahut powerful hai.