क्यू — अध्ययन नोट्स

1. परिचय

क्यू (Queue) एक रैखिक डेटा संरचना है जो FIFO (First In, First Out) सिद्धांत पर कार्य करती है। इसका अर्थ है कि जो तत्व सबसे पहले जोड़ा जाता है, वही सबसे पहले निकाला भी जाता है। क्यू को समझने का सबसे सरल उदाहरण किसी टिकट काउंटर पर लगी कतार (line) है - सबसे पहले आया व्यक्ति सबसे पहले टिकट प्राप्त करता है। इसी प्रकार, डाकघर, बैंक या किसी दुकान पर लगी कतारें क्यू का जीवन से उदाहरण हैं। क्यू में तत्वों का प्रवेश एक सिरे पीछे (Rear/Tail) से होता है और निष्कासन दूसरे सिरे सामने (Front/Head) से होता है।

क्यू का उपयोग कंप्यूटर विज्ञान में अनेक स्थानों पर होता है, जैसे प्रिंटर स्पूलिंग (जहाँ प्रिंट कार्य क्रम से निष्पादित होते हैं), ऑपरेटिंग सिस्टम में प्रक्रिया अनुसूचन (process scheduling), मैसेज कतारें, और ब्रेडथ फर्स्ट सर्च (BFS) एल्गोरिथ्म।

2. क्यू की मूल अवधारणाएँ (Basic Concepts)

• फ्रंट (Front/Head): क्यू का वह सिरा जहाँ से तत्व निकाले (dequeue) जाते हैं।
• रियर (Rear/Tail): क्यू का वह सिरा जहाँ पर नए तत्व जोड़े (enqueue) जाते हैं।
• Enqueue: क्यू में नया तत्व जोड़ने की क्रिया।
• Dequeue: क्यू से फ्रंट तत्व निकालने की क्रिया।
• Underflow: खाली क्यू से तत्व निकालने का प्रयास।
• Overflow: पूर्ण क्यू में तत्व जोड़ने का प्रयास (निश्चित आकार की क्यू में)।

क्यू की विशेषताएँ:

1. यह एक रैखिक डेटा संरचना है।
2. यह FIFO सिद्धांत का पालन करती है।
3. प्रवेश रियर से और निष्कासन फ्रंट से होता है।
4. सूची कार्यान्वयन में enqueue की समय जटिलता O(1) होती है।

3. क्यू के मुख्य ऑपरेशन (Operations on Queue)

3.1 Enqueue ऑपरेशन

Enqueue ऑपरेशन क्यू के पीछे (रियर) में नया तत्व जोड़ता है:

def enqueue(queue, element):
    queue.append(element)
    print(element, "क्यू में जुड़ा")

यहाँ append() विधि तत्व को सूची के अंत में जोड़ती है, जो क्यू का रियर है।

3.2 Dequeue ऑपरेशन

Dequeue ऑपरेशन क्यू के सामने (फ्रंट) से तत्व निकालता है:

def dequeue(queue):
    if is_empty(queue):
        print("क्यू खाली है (Underflow)")
        return None
    return queue.pop(0)

यहाँ pop(0) सूची का पहला तत्व (फ्रंट) निकालता है।

3.3 अन्य सहायक ऑपरेशन

def is_empty(queue):
    return len(queue) == 0

def front_element(queue):
    if is_empty(queue):
        return None
    return queue[0]

def display(queue):
    print("क्यू (फ्रंट से रियर):", queue)

पूर्ण कार्यान्वयन का उदाहरण:

queue = []

enqueue(queue, 10)
enqueue(queue, 20)
enqueue(queue, 30)
print(dequeue(queue))    # 10
print(dequeue(queue))    # 20
display(queue)           # [30]

4. सर्कुलर क्यू (Circular Queue)

सामान्य क्यू में dequeue के बाद फ्रंट बढ़ता है और रिक्त स्थानों का उपयोग नहीं हो पाता, जिससे स्थान नष्ट होता है। इस समस्या को हल करने के लिए सर्कुलर क्यू का उपयोग किया जाता है, जिसमें अंतिम स्थान के बाद पहला स्थान आता है (वृत्ताकार क्रम)। इससे क्यू के सभी स्थानों का पूर्ण उपयोग होता है।

सर्कुलर क्यू में अगला सूचकांक इस सूत्र से प्राप्त होता है:

(सूचकांक + 1) % आकार

क्यू के भरे या खाली होने की स्थिति अलग करने के लिए विशेष ध्यान देना पड़ता है, क्योंकि दोनों में फ्रंट और रियर समान हो सकते हैं।

5. क्यू के अनुप्रयोग (Applications of Queue)

1. प्रिंटर स्पूलिंग: कई दस्तावेज़ों को प्रिंट करने का कार्य क्यू में व्यवस्थित होता है, पहले भेजा गया दस्तावेज़ पहले प्रिंट होता है।
2. प्रक्रिया अनुसूचन (Process Scheduling): ऑपरेटिंग सिस्टम में प्रक्रियाओं को FIFO क्यू के माध्यम से निष्पादित किया जाता है।
3. मैसेज कतारें: सॉफ़्टवेयर के विभिन्न घटकों के बीच संदेशों का आदान-प्रदान क्यू द्वारा होता है।
4. ब्रेडथ फर्स्ट सर्च (BFS): ग्राफ/ट्री की यात्रा में BFS एल्गोरिथ्म क्यू का उपयोग करता है।
5. CPU/डिस्क अनुसूचन: संसाधनों के लिए प्रतीक्षा कर रही प्रक्रियाओं को क्यू में व्यवस्थित किया जाता है।
6. कॉल सेंटर की प्रतीक्षा कतार: ग्राहक सेवा में प्रतीक्षा कर रहे कॉल क्यू में रखे जाते हैं।

6. स्टैक और क्यू में अंतर

7. प्राथमिकता क्यू (Priority Queue)

प्राथमिकता क्यू में तत्वों को उनकी प्राथमिकता के अनुसार निकाला जाता है, न कि प्रवेश क्रम के अनुसार। सबसे अधिक (या निम्न) प्राथमिकता वाला तत्व सबसे पहले निकलता है। इसका उपयोग अस्पताल आपातकालीन विभाग, ऑपरेटिंग सिस्टम के कार्य अनुसूचन आदि में होता है।

import heapq

priority_queue = []
heapq.heappush(priority_queue, 30)
heapq.heappush(priority_queue, 10)
heapq.heappush(priority_queue, 20)
print(heapq.heappop(priority_queue))   # 10 - न्यूनतम प्राथमिकता

8. क्यू के आउटपुट का विश्लेषण (Output Analysis)

क्यू के ऑपरेशनों के परिणाम को चरणबद्ध रूप से समझना परीक्षा के कोड-आउटपुट प्रश्नों के लिए आवश्यक है:

queue = []
queue.append(5)          # enqueue(5) → क्यू: [5]
queue.append(8)          # enqueue(8) → क्यू: [5, 8]
queue.pop(0)             # dequeue() → 5 निकला, क्यू: [8]
queue.append(3)          # enqueue(3) → क्यू: [8, 3]
print(queue[0])          # फ्रंट = 8
print(queue)             # [8, 3]

यहाँ प्रत्येक चरण में फ्रंट और रियर की स्थिति को ध्यान से देखना चाहिए। जब pop(0) किया जाता है तो फ्रंट से तत्व निकलता है और बाकी तत्व आगे सरक जाते हैं। इस प्रकार FIFO क्रम बना रहता है। अभ्यास के लिए विभिन्न क्रमों के enqueue/dequeue को हाथ से लिखकर हल करें, क्योंकि यह क्यू की समझ को गहरा करता है और परीक्षा में आत्मविश्वास देता है। इसी प्रकार सर्कुलर क्यू के प्रश्नों में फ्रंट और रियर के सूचकांकों की गणना modulo नियम से करनी चाहिए।

त्वरित पुनरावृत्ति तालिकाएँ

क्यू के मुख्य ऑपरेशन

क्यू के प्रकार

माइंड मैप

महत्वपूर्ण आरेख (SVG)

आरेख 1: क्यू में Enqueue और Dequeue

आरेख 2: सर्कुलर क्यू

सामान्य गलतियाँ

1. dequeue में pop(0) के बजाय pop() का उपयोग: सूची का अंतिम तत्व pop() निकालता है जो LIFO (स्टैक) जैसा होगा; क्यू के लिए pop(0) अर्थात फ्रंट तत्व निकालना आवश्यक है।
2. फ्रंट और रियर को भ्रमित करना: प्रवेश रियर से और निष्कासन फ्रंट से होता है; इन्हें उलटने से FIFO सिद्धांत टूट जाता है।
3. Underflow की जाँच न करना: खाली क्यू से dequeue करने पर IndexError आता है; पहले is_empty जाँच करें।
4. सर्कुलर क्यू में modulo को भूलना: सर्कुलर क्यू में अगला सूचकांक (i+1) % आकार होता है; इसे भूलने से पूर्ण स्थान उपयोग नहीं होता।
5. dequeue के बाद स्थान मुक्त मानना: रैखिक क्यू में dequeue के बाद भी फ्रंट के सामने के स्थान रिक्त रहते हैं; स्थान का पुन: उपयोग सर्कुलर क्यू में संभव है।
6. queue[-1] को फ्रंट समझना: क्यू का फ्रंट queue[0] होता है और रियर queue[-1]।

परीक्षा युक्तियाँ

1. Enqueue और Dequeue के चरणबद्ध परिणाम लिखने का अभ्यास करें, विशेषकर सर्कुलर क्यू के साथ।
2. FIFO का स्मरण रखें: "First In, First Out" - जो पहले आया, वह पहले गया।
3. स्टैक और क्यू के सिरों का अंतर लिखित रूप में तैयार रखें, यह वस्तुनिष्ठ प्रश्नों में बार-बार आता है।
4. प्रिंटर स्पूलिंग, प्रक्रिया अनुसूचन और BFS जैसे अनुप्रयोगों के नाम याद रखें।
5. pop(0) क्यू के लिए और pop() स्टैक के लिए - इस जोड़ी को गलती से भी न बदलें।
6. प्राथमिकता क्यू के लिए heapq मॉड्यूल (heappush, heappop) की जानकारी रखें।

निष्कर्ष

क्यू एक FIFO सिद्धांत पर आधारित रैखिक डेटा संरचना है जिसमें तत्व रियर से जुड़ते हैं और फ्रंट से निकलते हैं। पाइथन में इसे सूची की append() और pop(0) विधियों से कार्यान्वित किया जा सकता है। सर्कुलर क्यू स्थान का पूर्ण उपयोग करता है और प्राथमिकता क्यू तत्वों को प्राथमिकता के क्रम में निकालता है। प्रिंटर स्पूलिंग, प्रक्रिया अनुसूचन और BFS जैसे अनुप्रयोगों में क्यू का महत्वपूर्ण योगदान है। स्टैक के साथ क्यू के अंतर को स्पष्ट रूप से समझना परीक्षा में बहुत सहायक होता है। चरणबद्ध अभ्यास से क्यू की अवधारणाओं में पूर्ण दक्षता प्राप्त की जा सकती है।