क्यू (Queue) और डेक (Deque)

टिकट खिड़की पर जो पहले आया उसे पहले सेवा मिलती है, और नए लोग पीछे जुड़ते हैं। क्यू इसी नियम पर बनी डेटा संरचना है, और यह वहाँ स्वाभाविक मॉडल है जहाँ अनुरोधों को उनके आने के क्रम में निपटाना हो — प्रिंटर की प्रतीक्षा करते प्रिंट-कार्य, वेब सर्वर तक पहुँचते अनुरोध, हेल्प डेस्क पर प्रतीक्षारत कॉल। यह अध्याय क्यू और उसकी संक्रियाओं को परिभाषित करता है, उसे पायथन सूची से लागू करता है, और फिर डेक (deque) से परिचय कराता है, ऐसी क्यू जो दोनों सिरों पर जोड़ने और हटाने की अनुमति देती है और इसलिए स्टैक या क्यू दोनों की तरह व्यवहार कर सकती है। यहाँ के प्रश्न अधिकतर अनुरेखण हैं: हर संक्रिया में front और rear का पीछा करें।

क्यू क्या है: पहले आया, पहले गया (FIFO)

क्यू एक क्रमबद्ध रैखिक सूची है जिसमें तत्व एक सिरे, REAR (जिसे tail भी कहते हैं), पर जोड़े जाते हैं और दूसरे सिरे, FRONT (जिसे head भी कहते हैं), से हटाए जाते हैं। जो तत्व सबसे देर से प्रतीक्षा कर रहा हो वह सदैव पहले हटता है, अतः क्यू FIFO सिद्धांत — First In, First Out — का पालन करती है। rear पर तत्व जोड़ना ENQUEUE है; front का तत्व हटाना DEQUEUE। ख़ाली क्यू से dequeue करना अंडरफ़्लो है; निश्चित क्षमता वाली भरी क्यू में enqueue करना ओवरफ़्लो।

स्टैक और क्यू साथ-साथ
विशेषतास्टैकक्यू
सिद्धांतLIFOFIFO
प्रयुक्त सिरेदोनों संक्रियाओं के लिए एक सिरा (TOP)जोड़ने के लिए REAR, हटाने के लिए FRONT
जोड़ना / हटानाPUSH / POPENQUEUE / DEQUEUE
दैनिक उदाहरणप्लेटों का ढेरटिकट खिड़की की कतार
  • दैनिक जीवन में: रेल टिकटों की प्रतीक्षा-सूची, टोल प्लाज़ा पर वाहन, कॉल सेंटर पर प्रतीक्षारत ग्राहक।
  • कंप्यूटिंग में: एक साझा प्रिंटर को भेजे गए प्रिंट-कार्य, वेब सर्वर पर आते अनुरोध, और प्रोसेसर की प्रतीक्षा करते कार्यों का ऑपरेटिंग सिस्टम द्वारा शेड्यूल।

पायथन में क्यू

पायथन सूची के साथ पुस्तक front को सूचकांक 0 पर और rear को अंत में रखती है। enqueue है myQueue.append(element); dequeue है myQueue.pop(0), जो पहला तत्व हटाकर लौटाता है; peek बिना हटाए myQueue[0] लौटाता है; isEmpty len(myQueue) == 0 जाँचता है और size len(myQueue) लौटाता है। स्टैक की तरह dequeue और peek को पहले isEmpty जाँचना चाहिए।

एक छोटा अनुरेखण — यह [20, 30, 15] छापता है, क्योंकि front से dequeue हुआ तत्व 10 है और 10 + 5 rear पर जुड़ता है:
q = []
q.append(10)
q.append(20)
q.append(30)
x = q.pop(0)
q.append(x + 5)
print(q)

⚠️ pop() स्टैक है, pop(0) क्यू है
एक ही सूची पर pop() अंतिम तत्व हटाता है (LIFO) और pop(0) पहला (FIFO)। कोड-आउटपुट प्रश्न इसी पर टिके होते हैं कि कौन-सा लिखा है, इसलिए अनुरेखण से पहले कोष्ठक पढ़ें।

डेक: दोहरे सिरे वाली क्यू

डेक (deque) ("डेक" उच्चारित, double-ended queue का संक्षेप) एक क्रमबद्ध रैखिक सूची है जिसमें दोनों सिरों पर तत्व जोड़े और हटाए जा सकते हैं। इसलिए यह पहले की दोनों संरचनाओं का सामान्यीकरण है: एक ही सिरे पर जोड़ने और हटाने से यह स्टैक की तरह व्यवहार करता है, और एक सिरे पर जोड़ने व दूसरे से हटाने से क्यू की तरह। इसकी संक्रियाएँ insertFront, insertRear, deletionFront और deletionRear हैं, और दोनों सिरों को पढ़ने के लिए getFront और getRear। पायथन सूची के साथ: insertFront है insert(0, x), insertRear है append(x), deletionFront है pop(0) और deletionRear है pop()।

डेक का अनुरेखण — इन पंक्तियों के बाद सूची ['D', 'A', 'C'] है:
d = []
d.append("A")
d.insert(0, "B")
d.append("C")
d.pop(0)
d.insert(0, "D")
चरण-दर-चरण: [A] → [B, A] → [B, A, C] → [A, C] (front से B हटा) → [D, A, C]।

डेक से पैलिंड्रोम की जाँच। शब्द का हर वर्ण rear पर जोड़ें। फिर जब तक एक से अधिक वर्ण बचे हों, एक front से और एक rear से हटाकर उनकी तुलना करें; कोई भी बेमेल हो तो शब्द पैलिंड्रोम नहीं है। "madam" और "level" पास होते हैं; "lever" पहली ही तुलना में, l बनाम r, विफल होता है। पुस्तक द्वारा बताए अन्य उपयोगों में ऐसे व्यक्ति को कतार के आगे फिर जुड़ने देना जो थोड़ी देर के लिए हटा था, और सीमित ब्राउज़िंग-इतिहास या undo-सूची रखना शामिल है, जहाँ नई प्रविष्टियाँ एक सिरे पर आने पर सबसे पुरानी दूसरे सिरे से हटा दी जाती है।

मुख्य बिंदु

  • क्यू REAR पर जोड़ती और FRONT से हटाती है, अतः वह FIFO है; संक्रियाएँ ENQUEUE और DEQUEUE हैं।
  • ख़ाली क्यू से dequeue अंडरफ़्लो है; भरी निश्चित-आकार क्यू में enqueue ओवरफ़्लो।
  • पायथन सूची में enqueue है append(x), dequeue है pop(0), और front है myQueue[0]।
  • क्यू प्रिंट-कार्यों, वेब-सर्वर अनुरोधों और कार्य-शेड्यूलिंग का मॉडल है — जो कुछ आगमन के क्रम में सेवा पाए।
  • डेक दोनों सिरों पर जोड़ने-हटाने देता है: एक ही सिरा स्टैक देता है, विपरीत सिरे क्यू।
  • पैलिंड्रोम की जाँच डेक भरकर front और rear से हटाए वर्णों की तुलना से होती है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. निम्नलिखित कोड का आउटपुट क्या है?
    q = []
    q.append(10)
    q.append(20)
    q.append(30)
    x = q.pop(0)
    q.append(x + 5)
    print(q)

    1. [10, 20, 35]
    2. [20, 30, 15]
    3. [15, 20, 30]
    4. [20, 30, 35]
    उत्तर देखें

    उत्तर: B — `[20, 30, 15]`

    pop(0) front का तत्व, 10, हटाता है, अतः सूची [20, 30] बनती है; फिर 10 + 5 = 15 rear पर जुड़ता है, परिणाम [20, 30, 15]। [10, 20, 35] pop(0) को pop() मानता है, जो स्टैक की तरह rear से 30 हटाता। [15, 20, 30] नए तत्व को front पर रखता है, और [20, 30, 35] ग़लत तत्व में 5 जोड़ता है।

  2. कौन-सा कथन क्यू का सही वर्णन करता है?

    1. तत्व एक ही सिरे, जिसे top कहते हैं, पर जोड़े और हटाए जाते हैं
    2. तत्व सूची में किसी भी स्थान पर जोड़े या हटाए जा सकते हैं
    3. तत्व सदैव अपने मानों के आरोही क्रम में हटाए जाते हैं
    4. तत्व rear पर जोड़े जाते हैं और front से हटाए जाते हैं
    उत्तर देखें

    उत्तर: D — तत्व rear पर जोड़े जाते हैं और front से हटाए जाते हैं

    क्यू दो सिरों का प्रयोग करती है — नए तत्व rear पर जुड़ते हैं और सबसे पुराना front से जाता है — यही उसे पहले-आया-पहले-गया बनाता है। एक ही top पर जोड़ना-हटाना स्टैक का वर्णन है। किसी भी स्थान से हटाना उसे साधारण सूची बना देता, और मान के अनुसार हटाना प्राथमिकता-क्रम का वर्णन है, आगमन-क्रम का नहीं जिसे क्यू रखती है।

  3. सूची d को डेक के रूप में प्रयोग किया जाता है। इन कथनों के बाद print(d) क्या दिखाता है?
    d = []
    d.append("A")
    d.insert(0, "B")
    d.append("C")
    d.pop(0)
    d.insert(0, "D")

    1. ['D', 'B', 'A']
    2. ['D', 'A', 'C']
    3. ['B', 'A', 'D']
    4. ['A', 'C', 'D']
    उत्तर देखें

    उत्तर: B — `['D', 'A', 'C']`

    अनुरेखण करें: [A], फिर front पर B डालने से [B, A], C जोड़ने से [B, A, C], pop(0) front से B हटाकर [A, C] छोड़ता है, और front पर D डालने से [D, A, C]। B और A पर समाप्त उत्तर pop(0) को rear से C हटाना मानता है। D को अंत में रखना insert(0, x), जो front पर जोड़ता है, को append से उलझाना है, जो rear पर जोड़ता है।

  4. एक ख़ाली क्यू से आरंभ कर 4, 7 और 2 इसी क्रम में enqueue किए जाते हैं; फिर एक dequeue होता है, 9 enqueue होता है, और एक और dequeue होता है। अब front पर कौन-सा तत्व है?

    1. 7
    2. 9
    3. 2
    4. 4
    उत्तर देखें

    उत्तर: C — 2

    क्यू [4, 7, 2] है; पहला dequeue 4 हटाता है, [7, 2]; 9 rear पर जुड़ता है, [7, 2, 9]; दूसरा dequeue 7 हटाता है और [2, 9] बचता है, अतः front पर 2 है। 9 rear है, जो उत्तर तब होता जब क्यू को स्टैक समझ लिया जाए। 7 दूसरे dequeue से पहले का front है, और 4 सबसे पहले क्यू से निकल गया।

  5. कई उपयोगकर्ता एक साझा प्रिंटर को दस्तावेज़ भेजते हैं, और दस्तावेज़ उसी क्रम में छपने चाहिए जिसमें भेजे गए। इसके लिए कौन-सी डेटा संरचना सबसे उपयुक्त है?

    1. क्यू
    2. स्टैक
    3. दस्तावेज़ के आकार पर आधारित डिक्शनरी
    4. दस्तावेज़ के नाम के अनुसार वर्णक्रम में क्रमित सूची
    उत्तर देखें

    उत्तर: A — क्यू

    आगमन के क्रम में छापना पहले-आया-पहले-गया है, जो ठीक क्यू है: हर नया कार्य rear पर जुड़ता है और प्रिंटर front का कार्य लेता है। स्टैक सबसे हाल में भेजा दस्तावेज़ पहले छापता, अतः जिसने पहले भेजा वह सबसे देर प्रतीक्षा करता। आकार या नाम से क्रमित करना उस आगमन-क्रम की अनदेखी है जिसकी प्रश्न माँग करता है।

  6. एक डेक को इस प्रकार प्रयोग किया जाता है कि हर जोड़ और हर हटाव केवल front सिरे पर हो। तब वह कैसा व्यवहार करता है?

    1. क्यू की तरह, क्योंकि front वहीं है जहाँ से क्यू तत्व हटाती है
    2. क्रमित सूची की तरह, क्योंकि front पर सदैव सबसे छोटा तत्व रहता है
    3. स्टैक की तरह, क्योंकि सबसे बाद में डाला तत्व सबसे पहले हटता है
    4. यह काम नहीं कर सकता, क्योंकि डेक को अपने दोनों सिरों का प्रयोग करना ही होगा
    उत्तर देखें

    उत्तर: C — स्टैक की तरह, क्योंकि सबसे बाद में डाला तत्व सबसे पहले हटता है

    जब जोड़ना और हटाना एक ही सिरा साझा करें, तो सबसे बाद में जोड़ा तत्व ही सदैव अगला हटता है — LIFO, एक स्टैक, सिरा चाहे जो चुना जाए। क्यू वाला विकल्प "front" शब्द पर अटकता है, पर क्यू को विपरीत सिरे पर जोड़ना चाहिए। डेक दोनों सिरों की अनुमति देता है, दोनों की अनिवार्यता नहीं, और उसमें कुछ भी तत्वों को क्रमित नहीं रखता।

  7. अभिकथन (A): जब पाठ्यपुस्तक की तरह पायथन सूची से क्यू लागू की जाती है, तो dequeue को myQueue.pop(0) लिखा जाता है। कारण (R): क्यू का front सूची के सूचकांक 0 पर रखा जाता है।

    1. A और R दोनों सत्य हैं, और R, A की सही व्याख्या है
    2. A और R दोनों सत्य हैं, पर R, A की सही व्याख्या नहीं है
    3. A सत्य है, पर R असत्य है
    4. A असत्य है, पर R सत्य है
    उत्तर देखें

    उत्तर: A — A और R दोनों सत्य हैं, और R, A की सही व्याख्या है

    enqueue सूची के अंत में जोड़ता है, अतः rear अंत है और front — सबसे पुराना तत्व — सूचकांक 0 पर है; dequeue को वहीं से हटाना होगा, जो pop(0) करता है। इसलिए R ही वह कारण है जिससे A ऐसा लिखा जाता है। R को "व्याख्या नहीं" कहना यह चूकना है कि front के लिए सूचकांक 0 का चुनाव ही तय करता है कि कौन-सा pop प्रयोग होगा।

  8. निम्नलिखित कोड क्या छापता है?
    def is_pal(word):
    dq = []
    for ch in word:
    dq.append(ch)
    while len(dq) > 1:
    if dq.pop(0) != dq.pop():
    return False
    return True
    print(is_pal("level"), is_pal("lever"))

    1. True True
    2. False False
    3. False True
    4. True False
    उत्तर देखें

    उत्तर: D — True False

    "level" के लिए front और rear के जोड़े l–l और फिर e–e हैं, और बीच का अकेला v लूप समाप्त करता है, अतः True। "lever" के लिए पहला हटाया गया जोड़ा front से l और rear से r है; वे भिन्न हैं और फ़ंक्शन तुरंत False लौटाता है। True True तभी आता जब तुलना अंतिम अक्षर की अनदेखी करती, और उलटा जोड़ा इसमें उलझता है कि कौन-सा शब्द दोनों ओर से एक-सा पढ़ा जाता है।