Circular Queue: insert, delete and display

📖 Theory

મરેલાં ખાનાં ફરી વાપરવાં

ગયો પાઠ શરમજનક રીતે પૂરો થયો: token ના queue એ બે ખાનાં ખાલી બેઠાં હોવા છતાં Overflow જાહેર કર્યો, કારણ કે front અને rear ફક્ત જમણે જ કૂચ કરે છે.

Canteen એ પોતાના ખરેખરા token ના પાટિયા માટે કરેલો ઉકેલ સુંદર રીતે સાદો હતો: token 999 પછી, ગણતરી ફરી 001 થી શરૂ થાય છે. કોઈ લાંબું પાટિયું ખરીદતું નથી; આંકડા વળી જાય છે.

એક modulo નું operator તમારા array ને એ જ મહાશક્તિ આપે છે.

📖 Theory

હરોળને વાળીને વીંટી બનાવો

5 array નાં ખાનાંને હરોળને બદલે વર્તુળ માં ગોઠવેલી ખુરશીઓ તરીકે કલ્પો. પાછળનો કારકુન ઘડિયાળની દિશામાં ચાલીને આવનારાને બેસાડે છે; આગળનો કારકુન ઘડિયાળની દિશામાં ચાલીને પીરસે છે.

કોઈ પણ કારકુન છેલ્લી ખુરશી વટાવે, ત્યારે પછીનું ડગલું સ્વાભાવિક રીતે ખુરશી 0 પર પડે છે: વર્તુળ પર કોઈ "છેડો" હોતો જ નથી. કારકુન ફેરો પૂરો કરે એ ક્ષણે છૂટેલી ખુરશીઓ ફરી રમતમાં આવી જાય છે. વીંટી પર મરેલી જગ્યા હોઈ જ ન શકે.

📖 Theory

વળી જવું, ઔપચારિક રીતે

આખી યુક્તિ એટલે + 1 ને modulo થી બદલવું:

• Insert: rear = (rear + 1) % SIZE;
• Delete: front = (front + 1) % SIZE;

SIZE 5 સાથે: 4 પછી આવે છે (4+1)%5 = 0. હરોળ હવે વીંટી છે.

એની સાથે નવી કસોટીઓ આવે છે:

• ભરેલો: (rear + 1) % SIZE == front (પછીની બેઠક front સાથે અથડાત)
• ખાલી: front == -1

ભરેલાની આ વિચિત્ર કસોટી કેમ? વાંચતા રહો; એ પરીક્ષાનો સૌથી પ્રિય ભાગ છે.

⌨️ Practical

વીંટી, કામ કરતી

#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

વળી જવાનું નજરે જુઓ

SIZE 5, અને ઉપરના main() માં છે બરાબર એ જ ક્રિયાઓ: 1 થી 4 insert, બે વાર delete, 5 insert, 6 insert. કાગળ પર દરેક પગલા પછી modulo સાથે (front, rear) નોંધો. Token 6 કયા ખાનામાં ઊતરે છે?

🧩 Quiz

ભરેલાની કસોટી ફક્ત "rear એ front ને મળે છે" ને બદલે (rear + 1) % SIZE == front કેમ છે, જે જાણી જોઈને એક ખાનું બગાડે છે?

1. કારણ કે સાવ ભરેલી વીંટી અને ખાલી વીંટી બંને rear == front જેવી જ દેખાત, એટલે એમને અલગ પાડવા એક ખાનું બલિદાન અપાય છે
2. કારણ કે modulo એ array નો છેલ્લો index ગણી શકતું નથી
3. કારણ કે આગળના કારકુનને આરામ કરવા ખુરશી જોઈએ
4. એ મોટા ભાગનાં પાઠ્યપુસ્તકોની ભૂલ છે; rear == front બરાબર ચાલે છે

⚠️ Watch out

Circular ની ત્રણ લપસણ

1. rear + 1 == front ને % SIZE વગર લખવું: array ના છેડે વળી જવાનું ચૂપચાપ તૂટી પડે છે.

2. છેલ્લા ઘટકનું ફરી ગોઠવવું ભૂલી જવું: જ્યારે front == rear હોય અને તમે delete કરો, ત્યારે બંને -1 પર પાછા આવવા જ જોઈએ, નહીં તો queue માને છે કે એક ભૂતિયો ઘટક બાકી છે.

3. સામાન્ય for (i = front; i <= rear...) થી display કરવું: વળી ગયા પછી rear એ front કરતાં સંખ્યાની રીતે નાનો હોય છે, અને loop કશું છાપતું નથી. Modulo સાથે ચાલો, rear પર અટકો.

📖 Theory

વીંટીઓ દુનિયા ચલાવે છે

Round-robin CPU નું scheduling (દરેક process ને વારો મળે, પછી એ ફરી વીંટીમાં જોડાય), તમારા keyboard નું input નું buffer, audio/video ના streaming નાં buffers, અને હા, token ના પડદા: બધાં circular queues. મર્યાદિત memory પર અંતહીન રીતે ઉત્પન્ન અને વપરાશ કરતી કોઈ પણ વ્યવસ્થા આખરે પોતાના array ને વીંટીમાં વાળે છે, બરાબર એ જ રીતે જે રીતે તમે હમણાં કર્યું.

✅ Summary

Key takeaways

• Circular queue = એવો array નો queue જેના indexes વળી જાય છે: rear = (rear + 1) % SIZE, front પણ એ જ રીતે.
• છૂટેલાં ખાનાં ફરી વપરાય છે; સાદા queue નો ખોટો overflow અદૃશ્ય થઈ જાય છે.
• ભરેલો: (rear + 1) % SIZE == front (એક ખાનું બલિદાન); ખાલી: front == -1.
• છેલ્લો ઘટક delete કરવાથી front અને rear -1 પર પાછા ગોઠવાય છે.
• Display એ modulo સાથે ચાલવું જોઈએ, ક્યારેય સાદા front થી rear ના loop થી નહીં.
• ઉપયોગ: round-robin scheduling, keyboard અને streaming નાં buffers.
• Memory hook: હરોળને વાળીને વીંટી બનાવો.