क्यू: FIFO और सीमित सर्कुलर ऐरे

पहले क्या आना चाहिए और लक्ष्य

पूर्णांक चर, असाइनमेंट, तुलना, if, return, फ़ंक्शन कॉल, निश्चित आकार के ऐरे और शून्य से शुरू होने वाले इंडेक्स आने चाहिए। आउटपुट मान लौटाने के लिए जितना पॉइंटर सिंटैक्स चाहिए, वह यहीं समझाया गया है। पहले पढ़ा पाठ, रिकर्शन में ऐरे के सीमित प्रीफ़िक्स को पढ़ना, सीमित ऐरे का संदर्भ देता है। यहाँ उसी इंडेक्स समझ का उपयोग है; क्यू की इन क्रियाओं में रिकर्सिव कोड नहीं चाहिए। क्यू का निकालने का नियम कॉल स्टैक से अलग है। लक्ष्य है FIFO समझना और चार स्थानों वाले ऐरे में घूमकर शुरुआत पर लौटने का ट्रेस बनाना। भौतिक इंडेक्स का क्रम और तार्किक क्रम अलग रखें।

यह GATE CS की संकीर्ण आधारभूत इकाई है। लिंक्ड क्यू, डेक, प्रायोरिटी क्यू, समवर्ती क्यू, amortized analysis और पूरा डेटा-स्ट्रक्चर पाठ्यक्रम इसके बाहर हैं।

क्यू का वादा

क्यू एक क्रमबद्ध सूची रखता है। enqueue पीछे नया मान जोड़ता है। dequeue सामने का मान निकालकर बताता है। FIFO यानी पहले आया, पहले निकला: अभी मौजूद मानों में सबसे पहले जोड़ा गया मान अगला निकलेगा। enqueue(10), enqueue(20), dequeue के बाद 10 निकलता है और [20] बचता है। स्टैक का last-in-first-out नियम अलग है।

आने के क्रम में दिए गए सेवा टिकट सोचें। सबसे पुराना प्रतीक्षारत टिकट पहले बुलाया जाता है; नया टिकट पीछे जुड़ता है। यह उपमा केवल क्रम बताती है। वास्तविक लोग बीच में जा सकते हैं या प्राथमिकता पा सकते हैं; हमारी क्यू में ये क्रियाएँ नहीं हैं। सर्कुलर ऐरे जगह इस्तेमाल करने का तरीका है, नए आगमन को आगे आने की अनुमति नहीं।

स्पष्ट शर्तें और स्थिति का अर्थ

C11 प्रोग्राम में ठीक चार int स्थानों का एक निश्चित ऐरे है। डायनैमिक मेमोरी या आकार बदलना नहीं है। मान int में समाने वाले सामान्य पूर्णांक हैं; कोड उन्हें केवल कॉपी करता है, जोड़ता नहीं। उदाहरण में 10 से 60 तक मान हैं। क्रियाएँ एक के बाद एक चलती हैं और caller सीधे data, front या size नहीं बदलता।

• CAPACITY = 4; वैध भौतिक इंडेक्स 0,1,2,3 हैं।
• front हमेशा 0 से 3 तक है। क्यू खाली न हो तो वह अगला निकालने वाला स्थान है। खाली हो तो अगला enqueue उसी स्थान पर लिखेगा।
• size तत्वों की गिनती है: 0 <= size <= 4। size==0 पर खाली, size==4 पर पूरी भरी। चारों स्थान इस्तेमाल हो सकते हैं।
• सामने से k नंबर का तार्किक तत्व data[(front+k)%CAPACITY] पर है, जहाँ 0 <= k < size।
• नया तत्व डालने का इंडेक्स (front+size)%CAPACITY है, लेकिन लिखने से पहले पूर्ण होने की जाँच अनिवार्य है।
• dequeue को पहले से मौजूद, लिखने योग्य int आउटपुट चर का पता दें। वह चर क्यू के ऐरे और नियंत्रण चरों से अलग हो तथा कॉल के दौरान मौजूद रहे। null, अवैध या उसी क्यू के स्थान की ओर इशारा करने वाले आउटपुट पॉइंटर अनुमत नहीं हैं; इनकी स्वतः जाँच नहीं होती।
• दोनों फ़ंक्शन सफलता पर 1, विफलता पर 0 लौटाते हैं। निकला मान आउटपुट चर में मिलता है; लौटाया status वह मान नहीं है। विफलता में ऐरे के सभी स्थान, front और size जस के तस रहते हैं। खाली dequeue में आउटपुट चर भी नहीं बदलता।

इन सीमाओं में front+size अधिकतम 7 और front+1 अधिकतम 4 है; ये C के न्यूनतम int दायरे में भी आते हैं। धनात्मक 4 से शेष लेने पर इंडेक्स 0 से 3 तक मिलता है। बहुत बड़ी क्षमता के लिए अलग अंकगणितीय सुरक्षा जाँच चाहिए।

नियम से पूरा C11 प्रोग्राम

enqueue पहले पूर्ण क्यू को अस्वीकार करता है, फिर अगले खाली तार्किक स्थान पर लिखकर size बढ़ाता है। dequeue पहले खाली क्यू को अस्वीकार करता है, फिर सामने का मान आउटपुट में कॉपी करता है, front को घूमते क्रम में बढ़ाता है और size घटाता है। बाकी तत्व खिसकते नहीं और निकला स्थान मिटाया नहीं जाता।

#include <stdio.h>

#define CAPACITY 4

int data[CAPACITY] = {0};
int front = 0;
int size = 0;

int enqueue(int value) {
    if (size == CAPACITY) {
        return 0;
    }
    int insertion = (front + size) % CAPACITY;
    data[insertion] = value;
    size = size + 1;
    return 1;
}

int dequeue(int *out) {
    if (size == 0) {
        return 0;
    }
    *out = data[front];
    front = (front + 1) % CAPACITY;
    size = size - 1;
    return 1;
}

int main(void) {
    int removed = -1;
    enqueue(10);
    enqueue(20);
    enqueue(30);
    dequeue(&removed);
    printf("removed=%d\n", removed);
    enqueue(40);
    enqueue(50);
    int full_status = enqueue(60);
    printf("front=%d size=%d full_enqueue=%d\n", front, size, full_status);
    while (dequeue(&removed)) {
        printf("%d ", removed);
    }
    printf("\nfront=%d size=%d\n", front, size);
    return 0;
}

आउटपुट:

removed=10
front=1 size=4 full_enqueue=0
20 30 40 50 
front=1 size=0

enqueue(60) से पहले क्यू पूरी भरी है। छापने से पहले उसका लौटाया status, full_status में रखा जाता है। स्थिति बदलने वाली कॉल को अलग कथन में रखने से printf के अलग-अलग आर्ग्युमेंट के अनिश्चित मूल्यांकन क्रम पर निर्भरता नहीं रहती।

नया सिंटैक्स

#include <stdio.h> से printf की घोषणा मिलती है। #define CAPACITY 4, CAPACITY टोकन को 4 से बदलने का निर्देश है। फ़ंक्शन के बाहर के तीन चर इस एक-क्यू उदाहरण की साझा global स्थिति हैं; बड़े प्रोग्राम स्थिति को दूसरे ढंग से संगठित कर सकते हैं। int data[CAPACITY] = {0} चारों स्थान शून्य से आरंभ करता है। शून्य खाली होने का संकेत नहीं है; सदस्यता size तय करता है।

% पूर्णांक भाग का शेष है। (3+1)%4 = 0, इसलिए इंडेक्स 3 के बाद 0 आता है। == समानता जाँचता है; = मान लिखता है। size = size + 1 गिनती एक बढ़ाता है और size = size - 1 एक घटाता है। ब्रेस कथनों का समूह बनाते हैं। int insertion उस enqueue कॉल का स्थानीय पूर्णांक घोषित करता है।

int dequeue(int *out) में * बताता है कि out, int का पॉइंटर यानी किसी पूर्णांक चर का पता है। &removed, main के चर का पता देता है। *out = data[front] में * उस पते वाले चर तक पहुँचकर निकला मान लिखता है। C पते की कॉपी पास करता है; उस पते के माध्यम से helper caller का चर बदल सकता है। ऐरे की कॉपी नहीं बनती। पॉइंटर अंकगणित नहीं है।

int main(void) बिना पैरामीटर वाला प्रवेश फ़ंक्शन है। printf में %d पूर्णांक छापता है; \n नई पंक्ति है। while (dequeue(&removed)) हर जाँच पर dequeue बुलाता है: 1 मिलने पर अंदर के कथन चलते हैं, 0 मिलने पर लूप रुकता है। आखिरी विफल जाँच पुराने आउटपुट को नहीं छापती। main का return 0 सामान्य समापन बताता है; helpers में यही 0 विफलता का status है। return तुरंत वर्तमान फ़ंक्शन समाप्त करता है।

डाउनलोड वाली queue.c में main के चारों ओर #ifndef QUEUE_TEST और #endif केवल परीक्षण के लिए हैं। queue_test.c, QUEUE_TEST को परिभाषित करके इसी implementation के साथ अपना परीक्षण main चलाती है। ऊपर दिखाए पूरे प्रोग्राम को यह परीक्षण-संबंधी शर्त नहीं चाहिए।

हल किया ट्रेस: इंडेक्स घूमते हैं, FIFO नहीं बदलता

हर पंक्ति क्रिया के बाद की स्थिति है। डैश का अर्थ वह स्थान वर्तमान क्यू का सदस्य नहीं है, भले उसमें पुराना पूर्णांक पड़ा हो।

50 डालने से पहले (front+size)%4 = (1+3)%4 = 0 है। स्थान 0 फिर इस्तेमाल हुआ, पर 50 सबसे नया है। पूरी भरी स्थिति में अगला संभावित इंडेक्स (1+4)%4 = 1 है, जहाँ सामने का 20 है। पूर्ण होने की जाँच 20 को मिटने से बचाती है।

अब चार dequeue के आउटपुट 20,30,40,50 होंगे। (front,size) क्रमशः (2,3), (3,2), (0,1), (1,0) होगा। अगला खाली dequeue status 0 लौटाता है और आउटपुट 50 ही रहता है। अब enqueue 70 इंडेक्स (1+0)%4 = 1 पर लिखकर स्थिति (1,1) बनाता है। खाली होने पर front को 0 करना आवश्यक नहीं।

सही क्यों और कितना काम

पूर्ण न होने पर जीवित तार्किक offset 0 से size-1 तक हैं। अगला offset size खाली स्थान है क्योंकि चार से कम लगातार सर्कुलर स्थान भरे हैं। वहाँ लिखने से पुराने क्रम को छेड़े बिना पीछे तत्व जुड़ता है; size बढ़ाने से ठीक एक सदस्य बढ़ता है। खाली न होने पर offset 0 वैध है। front आगे करने से बचे तत्व का पुराना offset k नया offset k-1 होता है; size घटाने से केवल सबसे पुराना तत्व निकलता है। जाँचें अवैध सदस्य पढ़ने या भरे स्थान पर लिखने से पहले हैं।

सामान्य स्थिर-लागत int क्रियाओं में दोनों helpers निश्चित संख्या में जाँच, असाइनमेंट और अंकगणित करते हैं, इसलिए हर enqueue/dequeue O(1) है। यहाँ O(1) तत्वों की गिनती से स्वतंत्र सीमित काम बताता है; O(C) और O(n) क्रमशः क्षमता C और संसाधित तत्वों की संख्या n के अनुपात में वृद्धि बताते हैं। ये शुरुआती वृद्धि-विवरण हैं, औपचारिक asymptotic analysis का प्रमाण नहीं। कोई छिपा shift लूप नहीं। यहाँ जगह चार स्थान है; क्षमता C हो तो O(C)। n तत्वों को पूरा निकालना या छापना O(n) काम है, जबकि एक dequeue O(1) है।

तीन निरूपण: नियम न मिलाएँ

1. हमारी count-आधारित सर्कुलर क्यू: front अगला निकालने का स्थान, size गिनती और insertion=(front+size)%4। खाली size=0, पूर्ण size=4, उपयोगी क्षमता चार। खाली और पूर्ण दोनों में insertion तथा front बराबर होते हैं; size उन्हें अलग करता है।
2. साधारण बिना घूमने वाली linear क्यू: next-insertion इंडेक्स केवल बढ़ता है। चार स्थान भरने के बाद दो dequeue से 0 और 1 खाली हुए, पर insertion अभी 4 है। जो संस्करण न खिसकाता, न reset करता, न wrap करता है, वह खाली शुरुआती स्थान फिर इस्तेमाल नहीं कर सकता और अंत पर enqueue अस्वीकार करता है। यह उस implementation की सीमा है, FIFO या हर linear-array implementation की नहीं।
3. एक वैकल्पिक सर्कुलर नियम एक स्थान खाली छोड़ता है: front अगला निकालने का स्थान, rear अगला डालने का स्थान। front==rear पर खाली; (rear+1)%4==front पर पूर्ण। चार भौतिक स्थानों में अधिकतम तीन तत्व आते हैं। यहाँ size counter नहीं है। इस full test को हमारे count-आधारित कोड में न मिलाएँ; स्थान खो जाएगा या rear का अर्थ गलत होगा। rear की दूसरी परिभाषाएँ भी हैं; पहले स्थिति का अर्थ तय करें।

मुख्य बातें

• FIFO आगमन और निकासी का क्रम है, बढ़ते भौतिक इंडेक्स नहीं।
• enqueue से पहले size==4, dequeue से पहले size==0 जाँचें।
• insertion पुराने front और size से निकालें, फिर size बढ़ाएँ।
• सफल dequeue में front को modulo चार बढ़ाएँ और size घटाएँ।
• पुरानी ऐरे कोशिकाएँ सदस्य नहीं हैं। शून्य भी वैध मान है।
• status और निकला मान अलग हैं। विफल क्रिया क्यू और आउटपुट जस के तस रखती है।
• count और reserved-slot नियमों की उपयोगी क्षमता तथा जाँचें अलग हैं।

आगे जाने से पहले

नया तत्व पहले निकाल रहे हों तो FIFO दोहराएँ। पूरी क्यू में सामने का तत्व मिटे तो full guard को लिखने से पहले रखें। wraparound के बाद इंडेक्स 0,1,2,3 को ही क्रम न मानें; front से शुरू करके size तत्व लें। खाली, एक तत्व, पूर्ण, विफल क्रिया, कुछ निकालकर फिर भरना और पूरा खाली करके भरना जाँचें।

स्रोत और सीमा

यह ऑफ़लाइन पाठ स्थानीय रूप से समीक्षा किए गए GATE CS प्रोग्रामिंग और डेटा-स्ट्रक्चर आधारभूत संदर्भ को आगे बढ़ाता है। नया syllabus सत्यापन, आधिकारिक पिछले वर्ष का प्रश्न, mock परीक्षा या पूरा पाठ्यक्रम होने का दावा नहीं है। C11 शिक्षण का चुनाव है, परीक्षा के भाषा-संस्करण का दावा नहीं। व्याख्याएँ और छह प्रश्न मौलिक हैं। कोई पाठ्यक्रम वर्ष या CMS प्रकाशन नहीं दिया गया है।

पहले स्वयं करें: दो छोटे अभ्यास

अभ्यास 1: मान और विफलता अलग हैं

खाली count-आधारित क्यू में front=2,size=0 है और out=99 है। enqueue(-1), dequeue(&out), dequeue(&out) करें। उत्तर पढ़ने से पहले हर status, हर क्रिया के बाद out और अंतिम (front,size) लिखें।

हल: enqueue status 1 देता है और इंडेक्स (2+0)%4=2 पर -1 लिखता है; out 99 रहता है और स्थिति (2,1) होती है। पहला dequeue status 1 देता है, out में -1 लिखता है और स्थिति (3,0) करता है। दूसरा status 0 देता है; out -1 और स्थिति (3,0) ही रहती है। ऋणात्मक payload -1 विफलता का संकेत नहीं है।

अभ्यास 2: क्रम बचाकर स्थान दोबारा इस्तेमाल करें

हमारी क्यू में front=3,size=3 और तार्किक सूची [11,22,33] है। भरे भौतिक इंडेक्स लिखें। फिर dequeue, enqueue(44), enqueue(55), enqueue(66) का ट्रेस बनाएँ। status, निकला मान, अंतिम front/size और तार्किक क्रम बताएँ।

हल: शुरू में इंडेक्स 3,0,1 पर 11,22,33 हैं। dequeue status 1 और आउटपुट 11 देता है; front=0,size=2 होता है। enqueue 44 इंडेक्स 2 पर लिखकर size=3 करता है; enqueue 55 इंडेक्स 3 पर लिखकर size=4 करता है। दोनों status 1 हैं। enqueue 66 बिना बदलाव 0 लौटाता है। अंतिम (front,size)=(0,4) और तार्किक सूची [22,33,44,55] है। स्थान 3 पर अब सबसे नया 55 है, निकाला गया सबसे पुराना 11 नहीं।

छह मौलिक एकल-उत्तर प्रश्न

हर प्रश्न में ठीक एक विकल्प चुनें। उसी प्रश्न में दिया नियम इस्तेमाल करें।

1

शुरू में खाली क्यू पर enqueue(8), enqueue(3), dequeue, enqueue(5), dequeue चलते हैं। क्रम से निकले दो मान क्या हैं?

A. 3, 5 B. 8, 3 C. 8, 5 D. 3, 8

2

हमारी क्षमता-4 count-आधारित क्यू में front=3, size=2 और तार्किक सूची [7,9] है। सफल enqueue(6) किस इंडेक्स पर लिखता है और (front,size) क्या रहता है?

A. इंडेक्स 1; (3,3) B. इंडेक्स 2; (3,3) C. इंडेक्स 1; (0,3) D. इंडेक्स 3; (3,3)

3

हमारी क्यू में front=2, size=4 है। enqueue(99) को क्या करना चाहिए?

A. data[2] पर नया मान लिखकर 1 लौटाए। B. 0 लौटाकर size को 0 करे। C. 1 लौटाए क्योंकि इंडेक्स 0 हमेशा फिर इस्तेमाल हो सकता है। D. हर स्थान, front और size बिना बदले 0 लौटाए।

4

हमारी क्यू में front=3, size=1 और data[3]=0 है। out शुरू में 77 है। dequeue(&out) दो बार बुलाकर status लिखें। (पहला status, दूसरा status, अंतिम out, अंतिम front, अंतिम size) क्या है?

A. (0,0,77,3,1) B. (1,0,77,0,0) C. (1,0,0,0,0) D. (1,1,0,1,-1)

5

दो क्यू में चार-चार भौतिक ऐरे स्थान हैं। पहली हमारी front+size वाली है। दूसरी एक स्थान खाली रखती है: front अगला निकालने का, rear अगला डालने का; front==rear पर खाली और (rear+1)%4==front पर पूर्ण। क्रम से अधिकतम जीवित तत्वों की संख्या क्या है?

A. 4 और 4 B. 4 और 3 C. 3 और 4 D. 3 और 3

6

साधारण बिना घूमने वाली चार-स्थान linear क्यू इंडेक्स 0 से 3 भरती है। दो dequeue के बाद 0 और 1 खाली हैं और next-insertion इंडेक्स 4 है। यह संस्करण कभी shift, reset या wrap नहीं करता। सही कथन कौन-सा है?

A. दो खाली स्थान होते हुए भी ऐरे के अंत पर enqueue अस्वीकार करना होगा। B. कहीं और दो खाली स्थान होने से data[4] पर लिख सकता है। C. अब हर FIFO क्यू पूर्ण ही होगी। D. सर्कुलर implementation जगह फिर इस्तेमाल करने के लिए सबसे नया तत्व पहले निकालेगा।

उत्तर और हर विकल्प की व्याख्या

1: B

A गलत है। 3 फिर 5 निकालना सबसे नए आगमन को चुनता है, जो स्टैक जैसा नियम है।

B सही है। स्थितियाँ [8], [8,3], [3], [3,5], [5] हैं। निकले मान 8 फिर 3 हैं।

C गलत है। 8 निकलने के बाद प्रतीक्षारत 3, नए 5 से आगे है।

D गलत है। पहले आया 8 मौजूद हो तो पहला निकला मान 3 नहीं हो सकता।

2: A

A सही है। 7 और 9 इंडेक्स 3 और 0 पर हैं। (3+2)%4=1 खाली है। केवल size बढ़कर स्थिति (3,3) होती है।

B गलत है। इंडेक्स 2 लेने से अगला तार्किक स्थान 1 छूटेगा। घूमने के बाद अकेला size insertion इंडेक्स नहीं है।

C गलत है। enqueue front नहीं बढ़ाता; ऐसा करने से सबसे पुराना सदस्य तार्किक सूची से छूट जाएगा।

D गलत है। इंडेक्स 3 पर सामने का 7 है। वहाँ लिखने से मौजूद मान खो जाएगा।

3: D

A गलत है। (2+4)%4=2 पर सबसे पुराना तत्व है; full guard इस लेखन को रोकता है।

B गलत है। विफलता क्यू खाली नहीं करती; चारों सदस्य रहते हैं।

C गलत है। घूमकर केवल खाली स्थान फिर इस्तेमाल होते हैं; size=4 में कोई खाली नहीं।

D सही है। पहली जाँच size==CAPACITY सत्य पाकर किसी लेखन या गिनती बदलने से पहले 0 लौटाती है।

4: C

A गलत है। रखा हुआ शून्य वैध तत्व है; size=1 पर पहली निकासी सफल है।

B गलत है। पहली सफल कॉल out में 0 लिखती है। दूसरी विफल कॉल इसी 0 को रखती है, मूल 77 को नहीं।

C सही है। पहली कॉल status 1 लौटाकर मान 0 लिखती है, front को 3 से 0 और size को 0 करती है। दूसरी 0 लौटाती है और कुछ नहीं बदलती।

D गलत है। खाली होने की जाँच दूसरी सफल निकासी, front बढ़ने और ऋणात्मक size को रोकती है।

5: B

A गलत है। दूसरे संस्करण को केवल दोनों इंडेक्स से पूर्ण और खाली अलग रखने के लिए चार में से एक स्थान छोड़ना होता है।

B सही है। count, size=0 और size=4 अलग करता है, इसलिए चारों स्थान उपयोगी हैं। दूसरा नियम एक छोड़कर तीन तत्व रखता है।

C गलत है। क्षमताएँ उलटी हैं; स्थान छोड़ने वाला reserved-slot नियम है।

D गलत है। हमारे स्पष्ट size count में स्थान छोड़ना आवश्यक नहीं है।

6: A

A सही है। अगला लेखन स्थान 3 से बाहर है और दिए नियम पुराने स्थान वापस नहीं लेते। सर्कुलर implementation FIFO रखते हुए खाली स्थान इस्तेमाल कर सकता है।

B गलत है। चार-स्थान ऐरे में data[4] बाहर है। कहीं और खाली कोशिका होने से यह इंडेक्स वैध नहीं होता।

C गलत है। केवल दो तत्व बचे हैं। इस खास भंडारण नियम में जगह दोबारा नहीं मिलती; क्यू की परिभाषा यह सीमा नहीं लगाती।

D गलत है। सर्कुलर भंडारण सबसे पुराने को पहले निकालता है। घूमने से इंडेक्स बदलते हैं, FIFO नहीं।