Theory
Token line से असली code तक
आप concept Queue (FIFO) lesson से जानते हैं: पहला token अंदर, पहला serve।
अब canteen को यह चलता हुआ चाहिए: 5 token slots का एक array, एक customer आने पर एक insert, एक serve होने पर एक delete, counter के ऊपर screen के लिए एक display।
सब कुछ दो integers पर टिका है: front (अगला कौन serve होगा) और rear (सबसे नया token कहाँ गया)। उन्हें move होते देखिए, और देखिए वे पीछे क्या छोड़ते हैं।
Theory
Pointers वाले दो clerks
Token board पर दो clerks की कल्पना कीजिए:
- Rear clerk हर नए arrival को अगले खाली slot में stamp करता है, दाएँ move करते हुए।
- Front clerk जिसे भी point करता है उसे serve करता है, फिर वह भी दाएँ step करता है।
कोई भी clerk कभी बाएँ step नहीं करता। Arrivals rear को दाएँ धकेलते हैं, service front को दाएँ धकेलती है, और उनके बीच का gap ही असली waiting line है।
Theory
तीनों operations, precisely
Array q[SIZE], front = -1, rear = -1 (empty) के साथ।
Insert (enqueue) x:
1. Full है? अगर rear == SIZE - 1: Overflow, रुक जाइए।
2. पहला element? अगर front == -1, front = 0 set कीजिए।
3. rear = rear + 1; q[rear] = x;
Delete (dequeue):
1. Empty है? अगर front == -1 या front > rear: Underflow, रुक जाइए।
2. q[front] serve कीजिए, फिर front = front + 1;
Display: front से rear तक i के लिए q[i] print कीजिए।
Practical
Token queue, पूरी
#include <iostream>
using namespace std;
#define SIZE 5
class TokenQueue {
int q[SIZE];
int front, rear;
public:
TokenQueue() { front = -1; rear = -1; }
void insert(int x) {
if (rear == SIZE - 1) { cout << "Overflow" << endl; return; }
if (front == -1) front = 0; // first ever element
q[++rear] = x;
cout << "token " << x << " joined" << endl;
}
void del() {
if (front == -1 || front > rear) { cout << "Underflow" << endl; return; }
cout << "serving token " << q[front] << endl;
front++;
}
void display() {
for (int i = front; i <= rear && front != -1; i++)
cout << q[i] << " ";
cout << endl;
}
};
int main() {
TokenQueue t;
t.insert(101); t.insert(102); t.insert(103);
t.del(); // serves 101 (FIFO)
t.display(); // 102 103
return 0;
}
Think first
दोनों clerks को trace कीजिए
SIZE 5 है। Operations: insert 1, insert 2, insert 3, delete, delete, insert 4। कागज़ पर, हर step के बाद front और rear track कीजिए। वे कहाँ ख़त्म होते हैं, और अब कौन से array cells unreachable हैं?
Show the answer
insert 1: front 0, rear 0। insert 2: rear 1। insert 3: rear 2।
delete (1 serve करता है): front 1। delete (2 serve करता है): front 2।
insert 4: rear 3।
End state: front = 2, rear = 3, queue में 3 और 4 हैं।
Cells 0 और 1 dead हैं: दोनों clerks इनसे आगे निकल चुके हैं और कोई बाएँ step नहीं करता। Queue 5 में से 2 slots occupy करता है फिर भी future capacity का सिर्फ़ 1 slot बचता है। यह corpse trail याद रखिए; यह नीचे वाला exam सवाल बनता है।
Quiz
वह trace जारी रखते हुए (front=2, rear=3, SIZE=5): आप 5 insert करते हैं, फिर 6 insert करते हैं। दूसरे insert पर क्या होता है?
- Overflow declare होता है भले ही cells 0 और 1 खाली बैठे हों
- दोनों succeed होते हैं; queue automatically cell 0 में wrap करता है
- Underflow, क्योंकि front कभी 0 पर reset नहीं हुआ
- दूसरा insert front पर token 3 को overwrite करता है
Show the answer
Overflow declare होता है भले ही cells 0 और 1 खाली बैठे हों
insert 5 rear को 4 (last index) पर रखता है। insert 6 फिर rear == SIZE-1 पाता है और Overflow report करता है, जबकि दो बिल्कुल अच्छे cells शुरुआत में dead पड़े हैं: simple queue का false overflow flaw। Cell 0 में wrap करना (option B) बिल्कुल वह है जो एक simple queue नहीं कर सकता; वह upgrade circular queue है, अगला lesson।
Watch out
वे conditions जो students confuse करते हैं
Overflow check INSERT पर: rear == SIZE - 1।
Underflow check DELETE पर: front == -1 || front > rear।
इन्हें swap करना (insert पर front check करना) classic written-exam slip है। पहले insert पर one-time if (front == -1) front = 0; भी मत भूलिए: इसके बिना, display और delete हमेशा के लिए index -1 को घूरते हैं, भले ही inserts "काम" किए हों।
Theory
Flaw ही feature request है
हर deletion एक cell को strand करता है: काफ़ी traffic दिया जाए, KOI भी simple queue अपनी dead space में डूब जाता है, size चाहे कुछ भी हो। इसे fix करने को सिर्फ़ एक idea चाहिए: rear (और front) को index 0 तक wrap around करने दीजिए, row को एक ring में बदलते हुए। यही circular queue है, और अब आप बिल्कुल जानते हैं यह क्यों invent हुआ।
Summary
Key takeaways
- एक array पर simple queue: front serve करता है, rear receive करता है; दोनों -1 से शुरू होते हैं और सिर्फ़ दाएँ move करते हैं।
- Insert: overflow check (rear == SIZE-1), first-element fix (front = 0), फिर q[++rear] = x।
- Delete: underflow check (front == -1 या front > rear), q[front] serve कीजिए, front++।
- Display front से rear तक चलता है।
- Deleted cells dead space बन जाते हैं: शुरुआत में empty cells के साथ false overflow।
- यह flaw circular queue के wrap-around को motivate करता है।
- Memory hook: दो clerks जो कभी बाएँ step नहीं करते।