स्टैक (Stack)

प्लेटों का ढेर ऊपर से प्रयोग होता है: सबसे बाद में रखी प्लेट सबसे पहले उठाई जाती है। स्टैक ठीक इसी नियम पर बनी डेटा संरचना है, और यह वहाँ दिखती है जहाँ सबसे हाल की चीज़ से पहले निपटना हो — undo बटन, ब्राउज़र का back बटन, कोष्ठकों का मिलान, और कंप्यूटर द्वारा अंकगणित का मूल्यांकन। यह अध्याय स्टैक और उसकी दो संक्रियाओं को परिभाषित करता है, उसे पायथन सूची से लागू करता है, और फिर पेपर के प्रिय स्टैक-प्रश्नों पर काम करता है: push और pop के अनुक्रम का अनुरेखण, इन्फ़िक्स व्यंजकों को पोस्टफ़िक्स में बदलना, और पोस्टफ़िक्स व्यंजकों का चरण-दर-चरण मूल्यांकन।

स्टैक क्या है: अंतिम में आया, पहले बाहर (LIFO)

स्टैक एक रैखिक डेटा संरचना है जिसमें तत्व केवल एक सिरे पर जोड़े और हटाए जाते हैं, जिसे TOP कहते हैं। सबसे बाद में जोड़ा गया तत्व सदैव सबसे पहले हटता है, अतः स्टैक LIFO सिद्धांत — Last In, First Out — का पालन करता है। तत्व जोड़ना PUSH है; शीर्ष तत्व हटाना POP। पहले से भरे स्टैक पर push का प्रयास ओवरफ़्लो है; ख़ाली स्टैक से pop का प्रयास अंडरफ़्लो। पायथन सूची आवश्यकतानुसार बढ़ती है, अतः वहाँ व्यवहार में ओवरफ़्लो नहीं होता, पर अंडरफ़्लो होता है और हर pop से पहले उसकी जाँच करनी पड़ती है।

  • किसी स्ट्रिंग या सूची को उलटना: हर तत्व push करें, फिर सबको pop करें — वे उलटे क्रम में निकलते हैं।
  • टेक्स्ट एडिटर में undo और redo: हर परिवर्तन push होता है, और undo सबसे हाल वाले को pop करता है।
  • ब्राउज़र का back बटन: देखा गया हर पृष्ठ push होता है, और back पिछले पृष्ठ पर pop करता है।
  • कोष्ठकों का मिलान: हर खुलने वाला कोष्ठक push करें, हर बंद होने वाले पर एक pop करें; व्यंजक संतुलित है यदि कोई pop स्टैक को ख़ाली न पाए और अंत में स्टैक ख़ाली हो।

पायथन में स्टैक

पायथन सूची एक स्वाभाविक स्टैक बनती है यदि उसके अंत को शीर्ष माना जाए: append(x) push करता है और pop() (बिना तर्क) अंतिम तत्व हटाकर लौटाता है। पुस्तक संक्रियाओं को छोटे फ़ंक्शनों के रूप में बनाती है — isEmpty len(stack) == 0 लौटाता है, size len(stack), top (जिसे peek भी कहते हैं) stack[-1] बिना हटाए लौटाता है, और display तत्वों को ऊपर से नीचे छापता है। pop या peek करने वाला हर फ़ंक्शन पहले isEmpty जाँचता है, इसी से अंडरफ़्लो से बचा जाता है।

स्टैक से किसी शब्द को उलटना — यह KCATS छापता है:
s = []
for ch in "STACK":
s.append(ch)
r = ""
while s:
r += s.pop()
print(r)

🧠 push और pop का अनुरेखण
स्टैक को सूची के रूप में लिखें, शीर्ष दाईं ओर, और हर संक्रिया के बाद उसे अद्यतन करें। push 5, push 8, pop, push 3, push 9, pop, pop: [5] → [5, 8] → [5] (8 बाहर) → [5, 3] → [5, 3, 9] → [5, 3] (9 बाहर) → [5] (3 बाहर)। तत्व 8, 9, 3 क्रम में निकलते हैं और 5 शेष रहता है।

इन्फ़िक्स, प्रीफ़िक्स और पोस्टफ़िक्स संकेतन

हम सामान्यतः संक्रियक (operator) को उसके संकार्यों (operands) के बीच लिखते हैं — इन्फ़िक्स संकेतन, जैसे A + B। इन्फ़िक्स को यह बताने के लिए वरीयता-नियमों और कोष्ठकों की आवश्यकता होती है कि पहले क्या हो: A + B * C में गुणा पहले होता है, और (A + B) * C जोड़ को पहले करवाता है। दो अन्य संकेतन संक्रियक को कहीं और रखते हैं। प्रीफ़िक्स (पोलिश) संकेतन में संक्रियक संकार्यों से पहले आता है: + A B। पोस्टफ़िक्स (रिवर्स पोलिश) में उनके बाद: A B +। पोस्टफ़िक्स और प्रीफ़िक्स को कोष्ठकों की बिल्कुल आवश्यकता नहीं, क्योंकि हर संक्रियक की स्थिति ही मूल्यांकन का क्रम तय कर देती है — इसीलिए कंप्यूटर मूल्यांकन से पहले पोस्टफ़िक्स में बदलते हैं।

एक ही व्यंजक तीन संकेतनों में
इन्फ़िक्सप्रीफ़िक्सपोस्टफ़िक्स
A + B+ A BA B +
A + B * C+ A * B CA B C * +
A * B + C+ * A B CA B * C +
(A + B) * (C - D)* + A B - C DA B + C D - *
A - B + C+ - A B CA B - C +

इन्फ़िक्स से पोस्टफ़िक्स बनाना, और पोस्टफ़िक्स का मूल्यांकन

इन्फ़िक्स से पोस्टफ़िक्स — स्टैक संक्रियक रखता है। इन्फ़िक्स व्यंजक को बाएँ से दाएँ पढ़ें। संकार्य सीधे आउटपुट में जाता है। बायाँ कोष्ठक push होता है। दायाँ कोष्ठक मेल खाने वाले बाएँ कोष्ठक तक संक्रियकों को pop करके आउटपुट में भेजता है, और उस बाएँ कोष्ठक को pop करके फेंक दिया जाता है। संक्रियक पहले स्टैक के शीर्ष पर अधिक या समान वरीयता वाले हर संक्रियक को pop करके आउटपुट में भेजता है, फिर स्वयं push होता है। पढ़ना पूरा होने पर जो बचे उसे pop करके आउटपुट में डालें। A + B * C के लिए: A बाहर; + push; B बाहर; * की वरीयता + से अधिक है, अतः वह ऊपर push होता है; C बाहर; अंत — पहले * फिर + pop, परिणाम A B C * +।

पोस्टफ़िक्स का मूल्यांकन — स्टैक संकार्य रखता है। बाएँ से दाएँ पढ़ें। हर संकार्य push करें। संक्रियक मिलने पर दो मान pop करें — पहला pop हुआ मान दायाँ संकार्य है, दूसरा बायाँ — संक्रिया लगाएँ और परिणाम push करें। अंत में ठीक एक मान बचता है, वही उत्तर है। 6 2 3 + * 4 - के लिए: 6, 2, 3 push; + 3 और 2 pop कर 5 push करता है → [6, 5]; * 5 और 6 pop कर 30 push करता है; 4 push; - 4 और 30 pop कर 30 − 4 = 26 push करता है।

⚠️ − और / के लिए क्रम मायने रखता है
8 2 / में पहला pop हुआ मान 2 और दूसरा 8 है, अतः संक्रिया 8 / 2 = 4 है, 2 / 8 नहीं। + और * के लिए दोनों संकार्यों को उलटने से कुछ नहीं बदलता, इसीलिए पेपर अपने मूल्यांकन-प्रश्न − और / के साथ बनाता है।

मुख्य बिंदु

  • स्टैक एक ही सिरे, TOP, पर जोड़ता-हटाता है, अतः वह LIFO है; PUSH जोड़ता है, POP शीर्ष हटाता है।
  • भरे स्टैक पर push ओवरफ़्लो है; ख़ाली स्टैक से pop अंडरफ़्लो — हर pop से पहले isEmpty जाँचें।
  • पायथन सूची को स्टैक बनाने पर append() push करता है, pop() pop करता है और stack[-1] शीर्ष को देखता है।
  • स्टैक डेटा उलटते हैं, undo और back बटन चलाते हैं, और कोष्ठकों के संतुलन की जाँच करते हैं।
  • प्रीफ़िक्स संक्रियक को पहले, पोस्टफ़िक्स अंत में रखता है; किसी को कोष्ठक नहीं चाहिए। A + B * C पोस्टफ़िक्स में A B C * + है।
  • रूपांतरण में स्टैक संक्रियक रखता है; मूल्यांकन में संकार्य, और पहला pop हुआ मान दायाँ संकार्य होता है।

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

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

  1. निम्नलिखित कोड का आउटपुट क्या है?
    s = []
    for ch in "STACK":
    s.append(ch)
    r = ""
    while s:
    r += s.pop()
    print(r)

    1. STACK
    2. KCATS
    3. K
    4. SKCAT
    उत्तर देखें

    उत्तर: B — KCATS

    लूप S, T, A, C, K push करता है, जिससे K शीर्ष पर रहता है; फिर while लूप सूची ख़ाली होने तक pop करता है, पहले K और अंत में S, अतः r बनता है KCATS — स्टैक अपने से होकर जाने वाली हर चीज़ को उलट देता है। STACK के लिए पहले-आया-पहले-गया निष्कासन चाहिए, जो क्यू है, और केवल K भूल जाता है कि while लूप स्टैक ख़ाली होने तक pop करता रहता है।

  2. इन्फ़िक्स व्यंजक A + B * C का पोस्टफ़िक्स रूप क्या है?

    1. A B + C *
    2. A B C + *
    3. + A * B C
    4. A B C * +
    उत्तर देखें

    उत्तर: D — `A B C * +`

    गुणा की वरीयता जोड़ से अधिक है, अतः पहले B * C बनता है और B C * लिखा जाता है; उस परिणाम में A जोड़ने से A B C * + मिलता है। A B + C * तो (A + B) * C का पोस्टफ़िक्स है, जो वरीयता की अनदेखी वाला पाठ है। + A * B C इसी व्यंजक का सही रूप है, पर प्रीफ़िक्स संकेतन में, पोस्टफ़िक्स में नहीं।

  3. इन्फ़िक्स व्यंजक (A + B) * (C - D) को पोस्टफ़िक्स में बदलिए।

    1. A B + C D - *
    2. A B C D + - *
    3. * + A B - C D
    4. A B + * C D -
    उत्तर देखें

    उत्तर: A — `A B + C D - *`

    हर कोष्ठक पहले एक इकाई बनता है: A + B बनता है A B + और C - D बनता है C D -; उन्हें जोड़ने वाला * दोनों के बाद आता है, अतः A B + C D - *। प्रीफ़िक्स रूप * + A B - C D सही संकेतन है, पर ग़लत प्रकार का। * को दोनों आधों के बीच लिखना अब भी इन्फ़िक्स में सोचना है, और किसी संक्रियक से पहले चारों संकार्य इकट्ठे करना बदल देता है कि हर संक्रियक किन मानों को जोड़ता है।

  4. स्टैक का प्रयोग कर पोस्टफ़िक्स व्यंजक 6 2 3 + * 4 - का मूल्यांकन कीजिए।

    1. 14
    2. -26
    3. 26
    4. 8
    उत्तर देखें

    उत्तर: C — 26

    6, 2 और 3 push; + 3 और 2 pop कर 5 push करता है; * 5 और 6 pop कर 30 push करता है; 4 push; - पहले 4 फिर 30 pop करके 30 − 4 = 26 निकालता है। −26 उसी क्रम में घटाता है जिसमें मान pop हुए, 4 − 30, यह भूलकर कि पहला pop हुआ मान दायाँ संकार्य है। 14 जोड़ होने से पहले 6 को 2 से गुणा करने से आता है।

  5. एक ख़ाली स्टैक पर संक्रियाएँ push(5), push(8), pop(), push(3), push(9), pop(), pop() इसी क्रम में की जाती हैं। तत्व किस क्रम में बाहर आते हैं?

    1. 8, 3, 9
    2. 8, 9, 3
    3. 5, 8, 3
    4. 9, 3, 5
    उत्तर देखें

    उत्तर: B — 8, 9, 3

    5 और 8 push होने के बाद पहला pop 8 हटाता है; फिर 5 के ऊपर 3 और 9 push होते हैं, अतः अगले दो pop पहले 9 और फिर 3 हटाते हैं, और स्टैक पर 5 बचता है। 8, 3, 9 का क्रम बाद वाली मदों को उनके आने के क्रम में हटाता है, जो क्यू का व्यवहार है, और 5, 8, 3 स्टैक के शीर्ष के बजाय तल से शुरू करता है।

  6. जब कोई प्रोग्राम ख़ाली स्टैक से तत्व pop करने का प्रयास करता है तो उस स्थिति को क्या कहते हैं?

    1. ओवरफ़्लो
    2. टकराव (Collision)
    3. अंडरफ़्लो
    4. गतिरोध (Deadlock)
    उत्तर देखें

    उत्तर: C — अंडरफ़्लो

    जिस स्टैक में कुछ न हो उससे हटाना अंडरफ़्लो है, और स्टैक फ़ंक्शन pop से पहले isEmpty जाँचकर इससे बचता है। ओवरफ़्लो इसका उलटा है, पहले से भरे स्टैक पर push करना। टकराव हैशिंग का शब्द है जब दो कुंजियाँ एक ही स्थान पर आएँ, और गतिरोध एक-दूसरे की प्रतीक्षा करती प्रक्रियाओं का वर्णन है — दोनों में से कोई स्टैक की स्थिति नहीं।

  7. अभिकथन (A): पोस्टफ़िक्स व्यंजक को यह दिखाने के लिए कभी कोष्ठकों की आवश्यकता नहीं होती कि उसकी संक्रियाएँ किस क्रम में होंगी। कारण (R): पोस्टफ़िक्स संकेतन में संकार्यों के सापेक्ष हर संक्रियक की स्थिति मूल्यांकन का क्रम तय करती है।

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

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

    पोस्टफ़िक्स में संक्रियक स्टैक पर ठीक अपने पहले के दो मानों पर कार्य करता है, अतः वह कहाँ खड़ा है यही तय करता है कि वह कब लगेगा — A B + C * और A B C * + बिना किसी कोष्ठक के अलग-अलग अर्थ रखते हैं। यही स्थिति-नियम कोष्ठकों के अनावश्यक होने का कारण है, अतः R, A की व्याख्या करता है। "R व्याख्या नहीं है" चुनना यह अनदेखा करता है कि स्थिति ठीक वरीयता और कोष्ठकों का ही स्थान लेती है।

  8. निम्नलिखित कोड द्वारा क्या छापा जाता है?
    stack = [10, 20, 30]
    stack.append(stack.pop() + stack[-1])
    print(stack)

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

    उत्तर: D — `[10, 20, 50]`

    पायथन पहले बायाँ संकार्य मूल्यांकित करता है: stack.pop() 30 हटाकर लौटाता है और [10, 20] बचता है, अतः अब stack[-1] 20 है; उनका योग 50 जोड़ा जाता है, परिणाम [10, 20, 50]। 60 वाला उत्तर stack[-1] को 30 पढ़ता है, मानो pop अभी हुआ ही न हो। सूची में 30 रखना भूलता है कि pop तत्व को हटा देता है, और [10, 50] 20 को भी हटा देता है, जो [-1] से झाँकना कभी नहीं करता।