स्टैक: LIFO, push/pop और सीमित ऐरे

आप क्या सीखेंगे

स्टैक एक क्रम में तत्व रखता है, लेकिन जोड़ने और निकालने की अनुमति केवल एक छोर पर देता है। इस छोर को top कहते हैं। आप स्टैक के वास्तविक सदस्यों और उसके लिए रखी गई ऐरे की जगह में अंतर करेंगे, सफल तथा असफल क्रियाओं का ट्रेस बनाएँगे और बिना dynamic allocation के तीन पूर्णांकों की क्षमता वाला स्टैक लिखेंगे।

पूर्वज्ञान: C के सामान्य int चर, असाइनमेंट, तुलना, if, फ़ंक्शन, return, निश्चित आकार के ऐरे और शून्य से शुरू होने वाले इंडेक्स। int a[3] में वैध इंडेक्स 0, 1, 2 हैं। “रिकर्शन: आधार स्थिति और कॉल स्टैक” पढ़ा हो तो सबसे बाद में बुलाई गई कॉल के पहले लौटने का विचार परिचित होगा। यह उपयोगी संदर्भ है; यहाँ रिकर्शन लिखना आवश्यक नहीं है। नीचे प्रयुक्त structure और file-scope घोषणा यहीं समझाई गई हैं।

यह GATE CS की तैयारी का एक आधारभूत पाठ है, पूरा डेटा-स्ट्रक्चर कोर्स नहीं। expression evaluation, रिकर्शन का कार्यान्वयन, कई स्वतंत्र स्टैक, आकार बढ़ाना, linked storage और एक ही समय में कई क्रियाएँ इस पाठ के दायरे में नहीं हैं।

एक छोर और सही उपमा

एक संकरे प्लेट-होल्डर की कल्पना करें जिसमें प्लेट केवल ऊपर से रख या निकाल सकते हैं। पहले 4, फिर -1, फिर 7 रखने पर 7 सबसे ऊपर होगा। निकालने का क्रम 7, -1, 4 होगा। यही LIFO: last in, first out, यानी जो तत्व सबसे बाद में जोड़ा गया और अभी तक निकाला नहीं गया, वह अगली बार निकलेगा। पुराने तत्व बाकी हों, तब भी नया push अगला निकाला जाने वाला तत्व बदल सकता है।

होल्डर में ठीक तीन प्लेटों की जगह है। चौथी प्लेट जोड़ने की कोशिश असफल होगी; खाली होल्डर से निकालने की कोशिश भी असफल होगी। यह उपमा क्रम और क्षमता समझाती है। इसका मतलब यह नहीं कि C ऐरे ऊपर-नीचे चलते हैं, निकाले गए मान की बाइट मिट जाती हैं या हर स्टैक की क्षमता तीन है।

push(x) जगह होने पर x को top पर जोड़ता है। pop() तत्व होने पर top को निकालकर उसका मान बताता है। बिना निकाले top देखना अक्सर peek कहलाता है; यहाँ उसका कोड नहीं लिखेंगे। top का निर्णय आने के क्रम से होता है, मान के बड़े-छोटे होने से नहीं। ऋणात्मक मान भी धनात्मक मान के ऊपर हो सकता है।

निरूपण और साफ़ सीमाएँ

यह प्रोग्राम data[3] और used से केवल एक स्टैक संभालता है।

• क्षमता हमेशा 3 है: int के तीन स्थान, इंडेक्स 0 से 2 तक।
• used मौजूद तत्वों की संख्या है। invariant है 0 <= used <= 3। invariant वह तथ्य है जो शुरुआत में सही होता है और हर अनुमत क्रिया के बाद सही रहता है।
• used > 0 होने पर नीचे से ऊपर तक मौजूद तत्व data[0] से data[used - 1] हैं।
• गैर-खाली स्टैक का top इंडेक्स used - 1 है। खाली स्टैक का कोई top तत्व नहीं है।
• जगह होने पर अगला तत्व इंडेक्स used पर जाएगा। पूरा भरा होने पर used == 3 है; उस समय यह वैध ऐरे इंडेक्स नहीं है।
• बाकी स्थान स्टैक के सदस्य नहीं हैं। उनमें शुरुआती शून्य या पुराने pop के बाद बचे मान हो सकते हैं।

तीनों स्थानों में शुरुआती शून्य होने पर भी स्टैक खाली है। caller को used या ऐरे सीधे नहीं बदलना चाहिए; आरंभ के बाद केवल दिखाए push/pop इस्तेमाल करें। कॉल एक-एक करके हों, साथ-साथ नहीं। कोड मनमाने ढंग से खराब किए गए state की जाँच करने वाला validator नहीं है। कोई भी मान जो C के int में समा सकता है, payload हो सकता है: -1, 0, INT_MIN, INT_MAX भी। इन मानों की केवल कॉपी होती है, उनमें जोड़ नहीं होता। INT_MIN और INT_MAX, <limits.h> में उस implementation के सबसे छोटे और सबसे बड़े int के नाम हैं; अलग validation प्रोग्राम उन्हें जाँचता है। हम कोई निश्चित bit width नहीं मानते। केवल छोटा count अपनी स्थापित सीमा के भीतर बढ़ता-घटता है।

सफलता और रखे हुए मान को अलग रखें

push सफलता पर 1 और भरे स्टैक पर असफलता के लिए 0 लौटाता है। यह status है, डाला गया मान नहीं। यदि pop केवल एक पूर्णांक लौटाए और -1 का अर्थ “खाली” हो, तो वास्तविक -1 तत्व से उसका अंतर कैसे करेंगे? इसलिए pop दो फ़ील्ड वाली structure लौटाएगा:

• ok: सफलता के लिए 1, खाली स्टैक की असफलता के लिए 0;
• value: निकला हुआ तत्व; केवल ok == 1 होने पर उपयोगी।

असफल pop में कोड value को 0 से शुरू करता है, लेकिन यह केवल placeholder है। इसका अर्थ यह नहीं कि स्टैक में 0 था। payload इस्तेमाल करने से पहले हमेशा ok जाँचें। structure लौटाने से इस शुरुआती उदाहरण में pointer और output-parameter वाली वाक्यरचना की ज़रूरत नहीं पड़ती।

पूरा C11 प्रोग्राम

ट्रेस पढ़ने से पहले आउटपुट का अनुमान लगाएँ। state बदलने वाली हर कॉल printing से पहले अलग statement में है। इसलिए आउटपुट C में फ़ंक्शन arguments के मूल्यांकन के क्रम पर निर्भर नहीं है।

#include <stdio.h>

static int data[3] = {0, 0, 0};
static int used = 0;

struct PopResult {
    int ok;
    int value;
};

int push(int value) {
    if (used == 3) {
        return 0;
    }
    data[used] = value;
    used = used + 1;
    return 1;
}

struct PopResult pop(void) {
    struct PopResult result = {0, 0};
    if (used == 0) {
        return result;
    }
    used = used - 1;
    result.ok = 1;
    result.value = data[used];
    return result;
}

int main(void) {
    struct PopResult result;
    int status;
    result = pop();
    printf("empty: %d %d\n", result.ok, used);
    status = push(4);
    printf("push 4: %d %d\n", status, used);
    status = push(-1);
    printf("push -1: %d %d\n", status, used);
    status = push(7);
    printf("push 7: %d %d\n", status, used);
    status = push(9);
    printf("full: %d %d\n", status, used);
    result = pop();
    if (result.ok == 1) {
        printf("pop: %d %d\n", result.value, used);
    }
    result = pop();
    if (result.ok == 1) {
        printf("pop: %d %d\n", result.value, used);
    }
    status = push(2);
    printf("push 2: %d %d\n", status, used);
    result = pop();
    if (result.ok == 1) {
        printf("pop: %d %d\n", result.value, used);
    }
    result = pop();
    if (result.ok == 1) {
        printf("pop: %d %d\n", result.value, used);
    }
    result = pop();
    printf("empty again: %d %d\n", result.ok, used);
    return 0;
}

इस प्रोग्राम की वाक्यरचना

#include <stdio.h> से printf की घोषणा मिलती है। %d एक int छापता है; format string के बाद दिए मान बाएँ से दाएँ उसके placeholders के अनुरूप हैं। \n नई output पंक्ति शुरू करता है। उद्धरण चिह्न text की सीमा बताते हैं।

सभी फ़ंक्शन से पहले की घोषणाएँ file scope पर हैं: फ़ंक्शन उसी data और used तक पहुँचते हैं। यहाँ static इन नामों को internal linkage देता है, यानी वे इस source file के भीतर रहते हैं। file-scope objects का जीवन पूरे प्रोग्राम तक रहता है। यह एक साझा स्टैक है, हर क्रिया के लिए नया ऐरे नहीं। यह छोटा डिज़ाइन कई स्वतंत्र स्टैक बनाने का interface नहीं है।

struct PopResult { ... }; दो नामित int फ़ील्ड वाला record type बनाता है। बंद brace के बाद semicolon आवश्यक है। struct PopResult result = {0, 0}; स्थानीय record बनाकर घोषणा के क्रम में पहले ok, फिर value को शुरुआती मान देता है। dot operator से result.ok और result.value फ़ील्ड चुने जाते हैं। struct PopResult pop(void) ऐसा record मान के रूप में लौटाता है; parameter सूची में void का अर्थ है कोई argument नहीं। return result; caller को परिणाम की कॉपी देता है; समाप्त हो चुके स्थानीय चर तक पहुँच नहीं देता। result = pop(); caller के चर में लौटा record रखता है। caller का result और pop का स्थानीय result, समान नाम के बावजूद अलग objects हैं।

int main(void) बिना parameters वाला प्रवेश फ़ंक्शन है; आखिर का return 0 सामान्य समाप्ति दर्शाता है। = मान देता है और == समानता जाँचता है। braces कथनों का समूह बनाते हैं; चल चुका return फ़ंक्शन को तुरंत समाप्त करता है। data[used] वर्तमान count को इंडेक्स की तरह इस्तेमाल करता है। प्रोग्राम pre/post-increment की जगह स्पष्ट used = used + 1 तथा used = used - 1 लिखता है। main में result की कोई फ़ील्ड पढ़ने से पहले उसे पूरा लौटा record मिल चुका होता है; status को भी छापने से पहले मान दिया जाता है।

हल किया ट्रेस 1: सफलता और दोनों असफलताएँ

नीचे कोष्ठक में केवल वास्तविक तत्व नीचे से ऊपर तक हैं, ऐरे के सभी स्थान नहीं।

प्रोग्राम का ठीक आउटपुट:

empty: 0 0
push 4: 1 1
push -1: 1 2
push 7: 1 3
full: 0 3
pop: 7 2
pop: -1 1
push 2: 1 2
pop: 2 1
pop: 4 0
empty again: 0 0

निकले मानों का क्रम 7, -1, 2, 4 है। असफल push से 9 जुड़ता ही नहीं। -1 निकालने पर ok == 1 है, इसलिए यह खाली होने का संकेत नहीं है।

हल किया ट्रेस 2: ऐरे में मान होना सदस्यता नहीं है

4, -1, 7 के सफल pushes के बाद ऐरे [4, -1, 7] और used 3 है। pop पहले used को 2 करता है, फिर data[2] पढ़कर 7 लौटाता है। ऐरे अब भी [4, -1, 7] है, पर स्टैक [4, -1] है। कोई shifting या clearing नहीं होती। दूसरा pop, used को 1 करके data[1] == -1 लौटाता है। अब push(2) इंडेक्स 1 पर लिखकर used को 2 करता है। ऐरे [4, 2, 7] है लेकिन वास्तविक सदस्य [4, 2] हैं। इंडेक्स 2 पर बचा 7 top नहीं है। इसीलिए किसी विशेष payload को “खाली” का चिह्न मानने की जगह count रखते हैं।

हर एक्सेस सुरक्षित क्यों है और क्रम क्यों ज़रूरी है

शुरुआत में used == 0 होने से invariant सही है। full push, ऐरे या count बदलने से पहले लौटता है। अन्यथा invariant से 0 <= used <= 2 मिलता है, इसलिए data[used] वैध है। लिखने के बाद count बढ़ाने से 1 <= used <= 3 होता है। पुराने तत्वों का क्रम बचता है और नया मान आखिरी वास्तविक तत्व बनता है।

खाली pop किसी ऐरे एक्सेस या count के बदलाव से पहले लौटता है। अन्यथा पुराना used, 1 से 3 तक है। पहले 1 घटाने से 0 से 2 तक का इंडेक्स मिलता है, ठीक पुराने top का इंडेक्स। उसे पढ़ने से आखिरी तत्व मिलता है और नई वास्तविक prefix से वह बाहर हो जाता है। count सीमा में रहता है। दोनों असफलताओं में पूरा ऐरे और used अपरिवर्तित रहते हैं। लौटा result record output है, संग्रहीत stack state का हिस्सा नहीं।

pop में घटाने से पहले data[used] न पढ़ें: वह वास्तविक स्टैक से बाहर है और भरे स्टैक पर ऐरे से भी बाहर है। खाली count न घटाएँ और full जाँचने से पहले न लिखें। C अपने आप array bounds नहीं जाँचता। हम इन गलत विकल्पों को चलाकर अवैध एक्सेस नहीं करते, बल्कि तर्क से गलती पहचानते हैं।

हर push/pop में सीमित संख्या में जाँच, assignments और अधिकतम एक ऐरे एक्सेस होता है। इसलिए इस fixed-array मॉडल में हर क्रिया का worst-case समय O(1) है: काम वर्तमान तत्वों की संख्या के साथ नहीं बढ़ता। इसका अर्थ CPU cycles की कोई निश्चित संख्या नहीं है। यहाँ हमेशा तीन integer slots और एक count की जगह है। इसी तरह निश्चित क्षमता C हो तो backing storage O(C) और क्रियाएँ O(1) होंगी, बशर्ते count में C समा सके। आकार अपने आप बढ़ाने वाला implementation अलग है और यहाँ उसका विश्लेषण नहीं है।

मुख्य बातें

• LIFO सबसे बाद में जुड़े अभी मौजूद तत्व को चुनता है, सबसे बड़े या सबसे पहले जुड़े मान को नहीं।
• used संख्या है। गैर-खाली top का इंडेक्स used - 1 है; नया insertion इंडेक्स used केवल जगह होने पर है।
• खाली: used == 0; भरा: used == 3।
• push लिखने से पहले full जाँचता है। pop घटाने या पढ़ने से पहले empty जाँचता है।
• असफल क्रियाएँ storage और count नहीं बदलतीं।
• pop का success और payload अलग हैं; -1 और 0 सामान्य वैध मान हैं।
• निकालने से सदस्यता बदलती है; पुरानी बाइट मिटाना ज़रूरी नहीं।

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

अभ्यास 1: खाली, एक तत्व, फिर खाली

खाली स्टैक से शुरू करें। push(0), pop(), pop() चलाएँ। उत्तर देखने से पहले हर कदम के बाद count तथा हर क्रिया का status लिखें; निकला मान केवल सफलता पर बताएँ।

हल: push(0) 1 लौटाकर used को 0 से 1 करता है; तत्व [0] हैं। पहला pop {1, 0} लौटाकर used को 0 करता है। उसने वास्तव में रखा हुआ शून्य निकाला। दूसरा pop {0, 0} लौटाता है, used 0 ही रहता है और कोई तत्व नहीं निकलता। पूरे समय ऐरे [0, 0, 0] है, लेकिन वास्तविक सदस्यता बदलती है। इसलिए शून्य वाले स्थान गिनकर खाली होने का निर्णय नहीं कर सकते।

अभ्यास 2: असफल push के बाद सफल pop

खाली स्टैक से शुरू करें। push(5), push(-1), push(6), push(9), pop(), push(2) करें। असफल क्रिया, निकला मान, आखिरी used और नीचे से ऊपर तक अंतिम क्रम का अनुमान लगाएँ।

हल: पहले तीन pushes सफल होकर [5, -1, 6] बनाते हैं और used == 3 होता है। push(9) 0 लौटाकर कुछ नहीं बदलता। इसलिए pop {1, 6} लौटाता है, 9 नहीं; अब [5, -1] और count 2 हैं। push(2) इंडेक्स 2 फिर इस्तेमाल करके सफल होता है। अंतिम स्टैक [5, -1, 2] और used == 3 है। असफलता ने न जगह ली, न मान बदला; सफल pop ने बाद के push के लिए जगह बनाई।

आगे बढ़ने से पहले

हर क्रिया के बाद, असफल क्रिया समेत, नीचे से ऊपर तक क्रम बनाएँ। सबसे पुराना मान निकाला हो तो LIFO दोहराएँ। इंडेक्स 3 इस्तेमाल किया हो तो क्षमता, count और top अलग करें। -1 को failure माना हो तो status देखें। पुराना मान फिर दिखाई दे तो used से चुनी वास्तविक prefix चिह्नित करें।

स्रोत और दायरा

यह मौलिक offline आधार-पाठ पहले समीक्षा किए स्थानीय रिकर्शन संदर्भ, विशेषकर अलग call state और सीमित ऐरे prefix, से आगे बढ़ता है। इसमें नया syllabus verification या exam-year assignment नहीं किया गया है। C11 शिक्षण के लिए चुना गया है। छह मौलिक single-choice अभ्यास आधिकारिक पुराने प्रश्न, पूरा mock या पूर्ण कोर्स-कवरेज का प्रमाण नहीं हैं। कोई सामग्री प्रकाशित या CMS में import नहीं की गई है।

छह मौलिक अभ्यास प्रश्न

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

प्रश्न 1

खाली स्टैक पर push(6), push(-1), pop(), push(8), pop(), pop() करें। सभी pushes के लिए जगह है। तीन सफल pops क्रम से कौन-से मान लौटाते हैं?

A. 6, -1, 8 B. -1, 8, 6 C. 8, -1, 6 D. -1, 6, 8

प्रश्न 2

क्षमता 3 है। खाली स्टैक पर push(2), push(5), push(-1), फिर push(9) करें। चौथा push क्या लौटाता है और बाद में नीचे से ऊपर तक स्टैक क्या है?

A. 1; [5, -1, 9] B. 0; [2, 5, 9] C. 0; [2, 5, -1] D. 1; [2, 5, -1, 9]

प्रश्न 3

दिखाए implementation में used == 2 है। कौन-सा कथन सही है?

A. top इंडेक्स 2 पर है और अगला push इंडेक्स 3 पर लिखेगा। B. top इंडेक्स 1 पर है और अगला सफल push इंडेक्स 2 पर लिखेगा। C. दो तत्व होने से top इंडेक्स 0 पर है। D. इंडेक्स 2 आखिरी वैध इंडेक्स है, इसलिए स्टैक भरा है।

प्रश्न 4

खाली स्टैक पर सफल push(-1) के बाद दो बार pop बुलाएँ। दिखाए कोड के अनुसार लौटे records (ok, value) का कौन-सा जोड़ा सही है?

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

प्रश्न 5

खाली स्टैक पर push(3), push(4), pop(), push(8) करें। दिखाए implementation में पूरा ऐरे data[0..2], used और top का मान क्या होगा?

A. [3, 8, 0]; used=2; top=8 B. [3, 4, 8]; used=3; top=8 C. [8, 3, 0]; used=2; top=3 D. [3, 4, 0]; used=2; top=4

प्रश्न 6

pop से पहले invariant 0 <= used <= 3 मानें। कौन-सा तर्क हर अनुमत अवस्था में सुरक्षित ऐरे एक्सेस सिद्ध करता है?

A. पहले data[used] पढ़ें, फिर empty जाँचें; ऐरे इंडेक्स अपने आप जाँचता है। B. खाली हो तब भी पहले घटाएँ; ऋणात्मक इंडेक्स का अर्थ कोई तत्व नहीं है। C. used==0 पर तुरंत लौटें; अन्यथा 1..3 वाले count को घटाकर 0..2 करें, फिर उस इंडेक्स को पढ़ें। D. used==0 होने पर भी data[used-1] पढ़ें; बाद का status उस read को रद्द कर देगा।

उत्तर और हर विकल्प का कारण

1: B

A गलत है। यह सबसे पहले आए तत्व को पहले निकालता है; पहले दो pushes के बाद top -1 है, 6 नहीं।

B सही है। अवस्थाएँ [] → [6] → [6,-1] → [6] → [6,8] → [6] → [] हैं; निकले मान -1, 8, 6 हैं।

C गलत है। पहले pop के समय 8 अभी आया ही नहीं है। भविष्य के सभी insertions को एक साथ उलट नहीं सकते।

D गलत है। push(8) के बाद 8, 6 के ऊपर है; इसलिए दूसरा pop 8 निकालेगा।

2: C

A गलत है। भरे स्टैक का push सबसे पुराना तत्व हटाकर सफलता नहीं बताता।

B गलत है। असफलता में वर्तमान top -1 को 9 से नहीं बदला जा सकता।

C सही है। तीन सफल pushes के बाद used 3 है। full की जाँच किसी write से पहले 0 लौटाती है; count और सभी स्थान वैसे ही रहते हैं।

D गलत है। ऐरे में अधिकतम तीन तत्व समाते हैं। जाँच चौथा तत्व डालने से रोकती है।

3: B

A गलत है। यह count को top इंडेक्स मानता है और अगला insertion ऐरे के बाहर कराएगा।

B सही है। दो तत्व इंडेक्स 0 और 1 पर हैं। इसलिए top, used-1=1 है और खाली स्थान 2 पर अगला push होगा।

C गलत है। इंडेक्स 0 नीचे का तत्व है; दो तत्वों में top इंडेक्स 1 पर है।

D गलत है। used=2 का मतलब दो भरे स्थान हैं, तीन नहीं। full के लिए used=3 चाहिए।

4: D

A गलत है। -1 वैध payload है; सफल निकालने पर ok=1 चाहिए। असफल record (0,0) से शुरू होता है, (0,-1) से नहीं।

B गलत है। पहले pop के बाद स्टैक खाली है, इसलिए दूसरे का ok 0 है। placeholder शून्य सफलतापूर्वक निकला तत्व नहीं है।

C गलत है। सफल payload -1 है, 0 नहीं। असफलता में शुरुआती (0,0) record ही रहता है।

D सही है। पहला pop used को 1 से 0 करके (1,-1) देता है। दूसरा बिना स्टैक बदले शुरुआती (0,0) लौटाता है; उसकी value payload नहीं है।

5: A

A सही है। दो pushes के बाद ऐरे [3,4,0], used=2 है। pop बिना मिटाए used=1 करके 4 लौटाता है। push(8) स्थान 1 पर लिखकर used=2 करता है; top data[1]=8 है।

B गलत है। pop ने वास्तविक count घटाया था। अगला push स्थान 2 पर आगे नहीं जोड़ता, स्थान 1 फिर इस्तेमाल करता है।

C गलत है। push पुराने नीचे के तत्व 3 को खिसकाता नहीं; वह इंडेक्स 0 पर रहता है।

D गलत है। जगह होने से push(8) सफल होता है और स्थान 1 के पुराने 4 को बदलता है।

6: C

A गलत है। C अपने आप सीमा नहीं जाँचता और full पर data[3] सीमा के बाहर है। छोटे count पर भी यह वास्तविक top नहीं है।

B गलत है। शून्य घटाकर -1 होता है, जो वैध इंडेक्स और count invariant दोनों से बाहर है। ऋणात्मक इंडेक्स खाली होने का चिह्न नहीं है।

C सही है। पहले लौटने से empty पर कोई read नहीं होता। गैर-खाली पुराना count 1, 2 या 3 है; घटाने पर इंडेक्स 0, 1 या 2 मिलता है, ठीक पुराना top।

D गलत है। खाली used पर इंडेक्स -1 मिलता है। बाद का status पहले हो चुका अवैध एक्सेस वापस नहीं कर सकता।