Stack in data structure

Introduction of stacks

Stack ऐसा Data structure है जिसमें New Elements सिर्फ प्रारंभ में ही जोड़ा जा सकता है तथा सिर्फ प्रारंभ से ही किसी Element को Delete किया जा सकता है।

for example के लिए मानते है कि एक Launch box में 3 चपाती हैं। जब लंच बॉक्स में इन्हें रखा गया था तो उनका क्रम 1, 2 तथा 3 था। लेकिन Launch करते समय उनके प्रयोग का क्रम 3, 2 तथा 1 था । इस क्रम में अंत में Insert किया गया एलीमेंट सबसे पहले प्रयोग में लिया जा रहा है। इस तकनीक को Last In First Out (LIFO) कहा जाता है।इसी प्रकार एक Furniture की दुकान में दुकानदार Plastic की विभिन्न कुर्सियों को एक-के-ऊपर-एक रखता है, किन्तु जब उन्हें बेचता है तो जो कुर्सी अंत में रखी गई होती है, सबसे पहले उसे ही बेचता है।

इस प्रकार stack से आशय ऐसे Data Structure (डेटा स्ट्रक्चर) से है जो LIFO तकनीक पर कार्य करता हो। किंतु प्रश्न उठता है कि Data Structure (डेटा स्ट्रक्चर) में उपरोक्त उदाहरणों का क्या काम है? वास्तव में विभिन्न Software में यह तकनीक प्रयोग में ली जाती है।

C programming Language में Recursion को Handel करने के लिए operating system को stack की सहायता लेनी होती है।

उपरोक्त उदाहरण में जब Block A से वापस fact(a-1) कॉल किया जा रहा है तो Program का कंट्रोल Block B में स्विच हो रहा है। इस स्विच से पहले operating system ब्लॉक A में मौजूद सभी ऑटोमैटिक वेरिएबल्स को एक Stack में insert  कर देता है। ध्यान दें कि ब्लॉक A में वेरिएबल a की Value 3 है। यह वेरिएबल स्टैक में निम्नानुसार इंसर्ट हो जाएगाः

जब ब्लॉक B से वापस fact(a-1) कॉल किया जा रहा है तो कंट्रोल ब्लॉक c में स्विच करने से पहले ब्लॉक B के वेरिएबल्स निम्नानुसार स्टैक में इंसर्ट कर दिए जाएंगे। ध्यान दें कि यहां पर वेरिएबल a की वैल्यू 2 है।

अंत में जब ब्लॉक C में if(a== 1) कंडीशन true हो जाएगी तो फंक्शन का कंट्रोल वापस उससे पूर्व के ब्लॉक B में आ जाएगा। इस समय स्टैक के प्रारंभ से एलीमेंट निकाला जाएगा और वापस ब्लॉक B का वेरिएबल अपनी मूल वैल्यू प्राप्त करेगा। ध्यान दें कि स्टैक से निकाले जाने वाली वैल्यू 2 है, अतः ब्लॉक B में वेरिएबल a की वैल्यू 2 हो जाएगी। इसी कारण से स्टेटमेंट f=a fact(a-1) निम्नानुसार परिवर्तित हो जाएगाः

इसी प्रकार Block B फंक्शन का कंट्रोल वापस उससे पूर्व के Block A में आ जाएगा। इस समय फिर Stack के प्रारंभ से Element निकाला जाएगा और वापस Block A का Variable अपनी मूल Value प्राप्त करेगा। ध्यान दें कि अब Stack से निकाले जाने वाली वैल्यू 3 है, अतः Block में Variable a की वैल्यू 3 होगी। इसी कारण से स्टेटमेंट f=a*fact(a-1) निम्नानुसार परिवर्तित हो जाएगाः

इस प्रकार स्पष्ट है कि Operating System (ऑपरेटिंग सिस्टम) किस प्रकार स्टैक को प्रयोग में लेता है। इसी प्रकार अन्य कई कंडीशन ऐसी हो सकती हैं जब Stack का प्रयोग किया जा सकता है। इसके लिए Stack पर किए जाने वाले ऑपरेशन हमें समझने होंगे। इन ऑपरेशन को समझने के लिए निम्नांकित शब्दों का ज्ञान होना आवश्यक हैं:

• Push (पुश)
• Pop (पॉप)
• Peek (पीक)
• Top (टॉप)
• MAXSIZE (मैक्ससाइज़)
• Overflow (ओवेरफ्लो)
• Underflow  (अन्डरफ्लो) 
• Traversal (ट्रावर्ज़ल )

Push:-

Stack (स्टैक) में जब कोई नया Element (एलीमेंट) जोड़ा जाता है तो उस ऑपरेशन को Push कहा जाता है। Stack (स्टैक) में  Push (पुश) किया गया एलीमेंट हमेशा top (अंत) में ही जुड़ता है।

Pop:-

Stack (स्टैक) से जब कोई Stack (स्टैक) Delete (हटाया) किया जाता है तो उस ऑपरेशन को Pop (पॉप) कहा जाता है। Stack (स्टैक) से Pop (पॉप) किया गया एलीमेंट हमेशा अंत से ही Delete (हटाया) किया  जाता है। सामान्यतया एलीमेंट को डिलीट करने से पूर्व उसे प्रयोग में ले लिया जाता है।

Peek:-

Stack (स्टैक) से जब कोई एलीमेंट Use तो किया जाता है किंतु डिलीट नहीं किया जाता है तो उस ऑपरेशन को Peek (पीक) कहा जाता है। यह ऑपरेशन भी Pop (पॉप) की जैसे ही स्टैक के अंत पर ही किया जाता है।

Top:-

Stack (स्टैक) पर Operation करते  समय यह पता होना चाहिए कि Push / Pop (पुश / पॉप) करते समय कौनसा Element प्रयोग में आएगा। सामान्यतः यह कार्य top नाम के एक वेरिएबल के माध्यम से किया जाता है। इस प्रकार top ऐसा Pointer

होता है जो स्टैक के अंतिम (top) एलीमेंट को दर्शाता है।

MAXSIZE:-

जब Stack (स्टैक) को एरे में माध्यम से प्रयोग में लिया जाता है तो यह बताना होता है तो कि Array Stack (स्टैक) में अधिकतम कितने एलीमेंट स्टोर किए जा सकेंगे। सामान्यतः यह कार्य MAXSIZE (मैक्ससाइज़) नाम के वेरिएबल के माध्यम से किया जाता है।

Overflow:-

जब Stack (स्टैक) पूरा भर जाता है तो इस Condition (कंडीशन) को Overflow (ओवरफ्लो) कहा जाता है। अन्य शब्दों में जब Top वेरिएबल की वैल्यू MAXSIZE की वैल्यू के बराबर हो जाती है तथा यूज़र नया एलीमेंट पुश करने कोशिश करता है तो ऐसी कंडीशन को Overflow (ओवरफ्लो) कहा जाता है। ऐसी स्थिति में User  सिर्फ एलीमेंट्स को Delete कर सकता है, किंतु नया एलीमेंट जोड़ नहीं सकता।

Underflow:-

जब Stack (स्टैक) खाली होता है तथा यूज़र किसी एलीमेंट को Delete करने की कोशिश करता है तो ऐसी स्थिति को Underflow (अंडरफ्लो) कहा जाता है। ऐसी स्थिति में User सिर्फ नया एलीमेंट जोड सकता है, किंतु Pop नहीं कर सकता है। ऐसी स्थिति में Top वेरिएबल की वैल्यू को 1 पर रखा जाता है।

Traversal:-

Traversal (ट्रावर्ज़ल) शब्द Travel (ट्रेवल) शब्द से बना है, जिसका अर्थ होता है घूमना। Stack (स्टैक) पर Traversal (ट्रावर्ज़ल)  Operation से आशय Stack (स्टैक) के सभी एलीमेंट्स को Visite करना । विज़िट करते समय प्रत्येक एलीमेंट को प्रिंट करवाया जा सकता है या कोई अन्य ऑपरेशन किया जा सकता है।