Queue

What is a queue?Queue kya hota hai?

A queue is a FIFO (first in, first out) list: insert at the rear, delete from the front — like a line at a ticket counter.Queue ek FIFO (first in, first out) list hai: rear pe insert, front se delete — bilkul ticket counter ki line ki tarah.

Simple vs circular queueSimple vs circular queue

In a simple array queue, the front moves forward on every dequeue, so space at the start is wasted. A circular queue wraps indices with mod n to reuse that space.Simple array queue mein har dequeue pe front aage badhta hai, toh shuru ki jagah waste ho jaati hai. Circular queue indices ko mod n se wrap karke wo jagah dobara use karta hai.

int q[N], front = 0, rear = 0;   // one slot kept empty

int isEmpty(void) { return front == rear; }
int isFull(void)  { return (rear + 1) % N == front; }
void enqueue(int x) { if (!isFull()) { q[rear] = x; rear = (rear + 1) % N; } }
int  dequeue(void)  { int x = q[front]; front = (front + 1) % N; return x; }

Common mistakeCommon galtiWith this convention a circular queue of size N holds at most N − 1 elements. Some books use a count variable instead — read the question's convention carefully.Is convention mein size N ki circular queue maximum N − 1 elements hold karti hai. Kuch books count variable use karti hain — question ka convention dhyan se padho.

VariantsVariants

Queue using two stacksDo stacks se queue

• Enqueue: push onto stack S1 — O(1).
• Dequeue: if S2 is empty, pop everything from S1 and push into S2; then pop S2.
• Each element moves at most twice, so dequeue is amortised O(1) (worst case O(n)).

• Enqueue: stack S1 pe push — O(1).
• Dequeue: agar S2 khaali hai toh S1 se sab pop karke S2 mein push karo; phir S2 se pop.
• Har element maximum do baar move hota hai, isliye dequeue amortised O(1) hai (worst case O(n)).

Stack using two queuesDo queues se stack

Either push is O(n) (rotate the new element to the front) and pop is O(1), or push is O(1) and pop is O(n). One of the two operations must be costly.Ya toh push O(n) (naye element ko rotate karke front pe lao) aur pop O(1), ya push O(1) aur pop O(n). Dono mein se ek operation mehenga hoga hi.

Where queues are usedQueue kahan use hoti hai

• BFS traversal of graphs and level-order traversal of trees.
• CPU scheduling (round robin), printer spooling.
• Buffers between producer and consumer.

• Graphs ka BFS traversal aur trees ka level-order traversal.
• CPU scheduling (round robin), printer spooling.
• Producer aur consumer ke beech buffers.