Theory
Dead cells को reuse करना
पिछला lesson एक embarrassment पर ख़त्म हुआ: token queue ने Overflow declare किया जबकि दो cells खाली बैठे थे, क्योंकि front और rear सिर्फ़ दाएँ ही march करते हैं।
Canteen के physical token board के लिए fix ख़ूबसूरती से simple था: token 999 के बाद, counter बस 001 से फिर शुरू होता है। कोई भी लंबा board नहीं ख़रीदता; numbers wrap around करते हैं।
एक modulo operator आपके array को वही superpower देता है।
Theory
Row को एक ring में मोड़िए
5 array cells को एक row के बजाय एक circle में chairs समझिए। Rear clerk clockwise चलते हुए arrivals बिठाता है; front clerk clockwise चलते हुए serve करता है।
जब कोई भी clerk last chair पार करता है, अगला step naturally chair 0 पर पहुँचता है: एक circle पर कोई "end" नहीं होता। Freed chairs वापस खेल में आ जाती हैं जैसे ही clerks एक lap पूरा करते हैं। एक ring पर dead space exist ही नहीं कर सकता।
Theory
Wrap, formally
पूरा trick + 1 को modulo से replace करना है:
- Insert:
rear = (rear + 1) % SIZE; - Delete:
front = (front + 1) % SIZE;
SIZE 5 के साथ: 4 के बाद (4+1)%5 = 0 आता है। Row अब एक ring है।
इसके साथ नए tests आते हैं:
- Full:
(rear + 1) % SIZE == front(अगली seat front में टकरा जाएगी) - Empty:
front == -1
यह अजीब full test क्यों? पढ़ते रहिए; यह exam का favourite part है।
Practical
Ring, काम करते हुए
#include <iostream>
using namespace std;
#define SIZE 5
class CircularQueue {
int q[SIZE];
int front, rear;
public:
CircularQueue() { front = -1; rear = -1; }
void insert(int x) {
if ((rear + 1) % SIZE == front) { cout << "Full" << endl; return; }
if (front == -1) { front = 0; rear = 0; } // first element
else rear = (rear + 1) % SIZE; // the wrap
q[rear] = x;
}
void del() {
if (front == -1) { cout << "Empty" << endl; return; }
cout << "serving " << q[front] << endl;
if (front == rear) { front = -1; rear = -1; } // served the last one
else front = (front + 1) % SIZE; // the wrap
}
void display() {
if (front == -1) return;
int i = front;
while (true) {
cout << q[i] << " ";
if (i == rear) break;
i = (i + 1) % SIZE;
}
cout << endl;
}
};
int main() {
CircularQueue c;
for (int t = 1; t <= 4; t++) c.insert(t);
c.del(); c.del(); // serves 1, 2: cells 0,1 freed
c.insert(5); c.insert(6); // 6 WRAPS into cell 0
c.display(); // 3 4 5 6
return 0;
}
Think first
Wrap होते हुए देखिए
SIZE 5, operations बिल्कुल ऊपर वाले main() जैसे: insert 1..4, दो बार delete, insert 5, insert 6। कागज़ पर, हर step के बाद modulo के साथ (front, rear) track कीजिए। Token 6 किस CELL में उतरता है?
Show the answer
insert 1..4: front 0, rear 3। दो बार delete: front 2 (cells 0,1 free)।
insert 5: rear (3+1)%5 = 4।
insert 6: rear (4+1)%5 = 0: token 6 cell 0 में उतरता है, वही cell जो simple queue ने छोड़ दिया था।
Final: front 2, rear 0, contents (ring चलते हुए) 3 4 5 6। पिछले lesson का false overflow बस ग़ायब हो गया।
Quiz
Full test (rear + 1) % SIZE == front जानबूझकर एक slot क्यों बर्बाद करता है, सिर्फ़ "rear front से मिलता है" के बजाय?
- क्योंकि एक पूरी तरह full ring और एक empty ring दोनों rear == front जैसे दिखेंगे, तो उन्हें अलग बताने के लिए एक slot sacrifice किया जाता है
- क्योंकि modulo array का last index compute नहीं कर सकता
- क्योंकि front clerk को rest करने के लिए एक chair चाहिए
- यह ज़्यादातर textbooks में एक mistake है; rear == front ठीक काम करता है
Show the answer
क्योंकि एक पूरी तरह full ring और एक empty ring दोनों rear == front जैसे दिखेंगे, तो उन्हें अलग बताने के लिए एक slot sacrifice किया जाता है
एक ring पर, अगर आप हर seat भर दें, rear front तक पहुँच जाता है: बिल्कुल एक empty queue जैसी वही picture। Ambiguity! Standard fixes: एक seat जल्दी रुक जाना (यह test) या एक अलग count variable रखना। Option D trap है: rear == front तब तक "काम करता है" जब तक पहली बार आपका program full से empty नहीं बता पाता और garbage serve करता है।
Watch out
तीन circular slips
1. rear + 1 == front % SIZE के बिना लिखना: array के end पर wrap चुपचाप टूट जाता है।
2. last-element reset भूल जाना: जब front == rear हो और आप delete करें, दोनों को -1 पर लौटना ही चाहिए, वरना queue को लगता है एक ghost element बचा है।
3. एक ordinary for (i = front; i <= rear...) से display करना: एक wrap के बाद, rear front से NUMERICALLY छोटा है, और loop कुछ print नहीं करता। Modulo से चलिए, rear पर रुकिए।
Theory
Rings दुनिया चलाते हैं
Round-robin CPU scheduling (हर process को एक turn मिलता है, फिर वह ring में वापस जुड़ता है), आपके keyboard का input buffer, audio/video streaming buffers, और हाँ, token displays: सब circular queues हैं। कोई भी system जो finite memory पर हमेशा produce और consume करता है अपने array को एक ring में मोड़ता है, बिल्कुल जैसे आपने अभी किया।
Summary
Key takeaways
- Circular queue = एक array queue जिसके indexes wrap करते हैं: rear = (rear + 1) % SIZE, front भी वैसे ही।
- Freed cells reuse होते हैं; simple queue का false overflow ग़ायब हो जाता है।
- Full: (rear + 1) % SIZE == front (एक slot sacrifice); empty: front == -1।
- Last element delete करने से front और rear -1 पर reset होते हैं।
- Display को modulo से चलना चाहिए, कभी plain front-to-rear loop से नहीं।
- Applications: round-robin scheduling, keyboard और streaming buffers।
- Memory hook: row को एक ring में मोड़िए।