Queue — FIFO semantics, enqueue - dequeue, circular array implementation

3.2.7 · Coding › Linear Data Structures

Queue KYA hai?

Isko Stack (LIFO) se compare karo: stack sabse recent ko remove karta hai; queue sabse purane ko remove karta hai.

FIFO kyun important hai?

Implement kaise karte hain: naïve array (aur ye kyun bura hai)

Idea: ek plain array mein front index aur rear index rakho.

• enqueue: rear pe likho, phir rear++.
• dequeue: front pe padho, phir front++.

Kaise: Circular Array (Ring Buffer)

Wrap-around modulo se hota hai: $\text{next}(i)=(i+1)\mathrm{mod}N$ jahaan $N$ capacity hai.

Layout ko first principles se derive karna

Hum arr[N] store karte hain, plus ek front index aur ek count (elements ki sankhya). count kyun, rear index ki jagah? Kyunki sirf front aur rear indices se "full" aur "empty" ek jaisa dikhta hai (dono front == rear dete hain). count track karna is ambiguity ko saaf hata deta hai.

• Queue ka Front arr[front] pe rehta hai.
• Rear (next free slot) derive hota hai: $\text{rear}=(\text{front}+\text{count})\mathrm{mod}N$.

Reference implementation

class CircularQueue:
    def __init__(self, N):
        self.arr = [None] * N
        self.N = N
        self.front = 0
        self.count = 0
 
    def is_empty(self): return self.count == 0
    def is_full(self):  return self.count == self.N
 
    def enqueue(self, x):
        if self.is_full(): raise OverflowError("queue full")
        rear = (self.front + self.count) % self.N   # WHY: next free slot
        self.arr[rear] = x
        self.count += 1
 
    def dequeue(self):
        if self.is_empty(): raise IndexError("queue empty")
        x = self.arr[self.front]
        self.front = (self.front + 1) % self.N       # WHY: wrap front forward
        self.count -= 1
        return x
 
    def peek(self):
        if self.is_empty(): raise IndexError("queue empty")
        return self.arr[self.front]

Chaaron core ops O(1) time mein, O(N) space mein hain. Shifting kabhi nahi.

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Connections

• Stack — LIFO (mirror image: newest-first vs oldest-first)
• Modular Arithmetic (woh % N jo ring banata hai)
• Breadth-First Search (BFS) (queue ka canonical user)
• Deque — Double-Ended Queue (generalization: dono ends pe add/remove)
• Circular Buffer / Ring Buffer (OS aur networking mein same structure)
• Amortized Analysis (linked-list queue se compare karo, koi resize cost nahi)
• Priority Queue (FIFO tod deta hai: arrival ki jagah priority se order)

Concept Map