Theory
Token ની હરોળથી ખરેખરા code સુધી
Queue (FIFO) ના પાઠ પરથી ખ્યાલ તમને આવડે છે: પહેલું token અંદર, પહેલું પીરસાય.
હવે canteen ને એ ચાલતું જોઈએ છે: 5 token નાં ખાનાંનો array, ગ્રાહક આવે ત્યારે insert, પીરસાય ત્યારે delete, અને counter ઉપરના પડદા માટે display.
બધું બે પૂર્ણાંક પર ટકે છે: front (હવે કોને પીરસવાનું છે) અને rear (સૌથી નવું token ક્યાં ગયું). એમને ખસતાં જુઓ, અને એ પાછળ શું છોડે છે એ પણ જુઓ.
Theory
Pointers વાળા બે કારકુન
Token ના પાટિયા પાસે બે કારકુન કલ્પો:
- પાછળનો કારકુન દરેક નવા આવનારને પછીના ખાલી ખાનામાં નોંધે છે, જમણે ખસતાં.
- આગળનો કારકુન એ જેની તરફ ચીંધે છે એને પીરસે છે, પછી એ પણ જમણે ડગલું ભરે છે.
એકેય કારકુન ક્યારેય ડાબે ડગલું ભરતો નથી. આવનારા rear ને જમણે ધકેલે છે, સેવા front ને જમણે ધકેલે છે, અને એમની વચ્ચેનું અંતર એ જ ખરેખરી રાહ જોતી હરોળ છે.
Theory
ત્રણેય ક્રિયાઓ, ચોકસાઈથી
Array q[SIZE], જેમાં front = -1, rear = -1 (ખાલી).
Insert (enqueue) x:
1. ભરેલો છે? જો rear == SIZE - 1: Overflow, અટકો.
2. પહેલો ઘટક છે? જો front == -1, તો front = 0 કરો.
3. rear = rear + 1; q[rear] = x;
Delete (dequeue):
1. ખાલી છે? જો front == -1 કે front > rear: Underflow, અટકો.
2. q[front] ને પીરસો, પછી front = front + 1;
Display: front થી rear સુધીના દરેક i માટે q[i] છાપો.
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
બે કારકુનને અનુસરો
SIZE એ 5 છે. ક્રિયાઓ: insert 1, insert 2, insert 3, delete, delete, insert 4. કાગળ પર દરેક પગલા પછી front અને rear નોંધો. એ ક્યાં પૂરા થાય છે, અને array નાં કયાં ખાનાં હવે અપ્રાપ્ય છે?
Show the answer
insert 1: front 0, rear 0. insert 2: rear 1. insert 3: rear 2.
delete (1 પીરસાયું): front 1. delete (2 પીરસાયું): front 2.
insert 4: rear 3.
અંતિમ સ્થિતિ: front = 2, rear = 3, queue માં 3 અને 4 છે.
ખાનાં 0 અને 1 મરી ગયાં: બંને કારકુન એમને વટાવી ગયા છે અને એકેય ડાબે ડગલું ભરતો નથી. Queue 5 માંથી 2 ખાનાં રોકે છે છતાં ભવિષ્યની ક્ષમતાનું ફક્ત 1 ખાનું બાકી છે. લાશોની આ પગદંડી યાદ રાખો; નીચે એ જ પરીક્ષાનો પ્રશ્ન બને છે.
Quiz
એ જ પ્રવાસ આગળ ચલાવતાં (front=2, rear=3, SIZE=5): તમે 5 insert કરો છો, પછી 6. બીજા insert પર શું થાય છે?
- ખાનાં 0 અને 1 ખાલી બેઠાં હોવા છતાં Overflow જાહેર થાય છે
- બંને સફળ થાય છે; queue આપોઆપ ખાનું 0 તરફ વળી જાય છે
- Underflow, કારણ કે front ક્યારેય 0 પર પાછો ગોઠવાયો નહીં
- બીજું insert આગળના token 3 પર લખી નાખે છે
Show the answer
ખાનાં 0 અને 1 ખાલી બેઠાં હોવા છતાં Overflow જાહેર થાય છે
5 નું insert rear ને 4 પર મૂકે છે (છેલ્લો index). પછી 6 નું insert જુએ છે કે rear == SIZE-1 અને Overflow જાહેર કરે છે, જ્યારે શરૂઆતમાં બે એકદમ સારાં ખાનાં મરેલાં પડ્યાં છે: આ સાદા queue ની ખોટા overflow ની ખામી છે. ખાનું 0 તરફ વળી જવું (વિકલ્પ B) એ બરાબર એ છે જે સાદો queue કરી શકતો નથી; એ સુધારો એટલે circular queue, હવે પછીનો પાઠ.
Watch out
Students જે શરતો ગૂંચવે છે
Overflow ની ચકાસણી INSERT પર: rear == SIZE - 1.
Underflow ની ચકાસણી DELETE પર: front == -1 || front > rear.
એમને અદલાબદલ કરવી (insert પર front તપાસવો) એ લેખિત પરીક્ષાની જાણીતી લપસણ છે. અને પહેલા insert પરનું એક વારનું if (front == -1) front = 0; ભૂલશો નહીં: એના વગર insert "ચાલ્યા" હોવા છતાં display અને delete કાયમ index -1 તાક્યા કરે છે.
Theory
ખામી જ સુધારાની માંગણી છે
દરેક delete એક ખાનું નકામું છોડી દે છે: પૂરતી અવરજવર થાય તો કોઈ પણ સાદો queue માપ ગમે તે હોય તોય પોતાની જ મરેલી જગ્યામાં ડૂબી જાય છે. એને સુધારવા ફક્ત એક વિચાર જોઈએ: rear (અને front) ને index 0 તરફ વળી જવા દો, અને હરોળ વીંટી બની જાય. એ જ circular queue છે, અને હવે તમને બરાબર ખબર છે કે એની શોધ કેમ થઈ.
Summary
Key takeaways
- Array પરનો સાદો queue: front પીરસે છે, rear ઝીલે છે; બંને -1 થી શરૂ થાય છે અને ફક્ત જમણે જ ખસે છે.
- Insert: overflow ની ચકાસણી (rear == SIZE-1), પહેલા ઘટકનો સુધારો (front = 0), પછી q[++rear] = x.
- Delete: underflow ની ચકાસણી (front == -1 કે front > rear), q[front] પીરસો, front++.
- Display એ front થી rear સુધી ચાલે છે.
- Delete થયેલાં ખાનાં મરેલી જગ્યા બની જાય છે: શરૂઆતમાં ખાલી ખાનાં હોવા છતાં ખોટો overflow.
- એ ખામી જ circular queue ના વળી જવાનું કારણ છે.
- Memory hook: બે કારકુન જે ક્યારેય ડાબે ડગલું ભરતા નથી.