Stack क्या हैं? [Operations, Expressions, Algorithm in Stack in Hindi]

Stack क्या हैं? (Operations, Expressions, Algorithm in Stack)

Stack क्या हैं? 

Linked List में नए node को किसी भी स्थान पर insert किया जा सकता है तथा किसी पुराने node को किसी भी स्थान से delete भी किया जा सकता है। यदि list ऐसा हो जिसमें insertion और deletion का कार्य केवल एक ही स्थान से हो तो इस प्रकार के data Structure को Stack कहते हैं।

Stack एक ऐसे data structure है जिसमें element को जिस ओर से insert किया जाता है उसी से ही उसे delete भी किया जाता है। इसमें एक open end और एक close end होता है। open end को stack का top कहते हैं जहाँ से element को insert एवं delete किया जाता है। stack में element को insert एवं delete करना last-in-first-out (LIFO) क्रम में होता है अर्थात सबसे अंत मे insert किया गया element सबसे पहले delete होता है। 

इसमें insert (store) operation को push एवं delete (retrieve) operation को pop कहते हैं। किसी party में एक के ऊपर एक रखे प्लेट Stack का उदाहरण है। stack को निम्नलिखित में से किसी एक प्रकार से प्रदर्शित कर सकते हैं:

Representation of Stack in Memory

Stack को memory में array एवं linked list दोनों की सहायता से प्रदर्शित किया जा सकता है। माना STACK एक stack है तथा MAX एक variable और TOP एक pointer है। MAX variable STACK में elements की अधिकतम संख्या को store करके रखता है तथा TOP pointer STACK के top element का address store करके रखता है अर्थात top element को point करता है। तब STACK को array की सहायता से memory में निम्नलिखित प्रकार से प्रदर्शित किया जा सकता है:

Note:

1. जब भी किसी element को Push (insert) किया जाता है तो top=top+1 हो जाता है।
2. जब भी किसी element को pop (delete) किया जाता है तो top=top+1 हो जाता है।
3. Overflow: यह तब होता है जब Top=MAX हो और हमें insertion करना हो अर्थात stack पूरा भरा हो।
4. Underflow: यह तब होता है जब Top=NULL हो और हमें deletion करना हो अर्थात stack पूरा खाली हो।

Operations in Stack: (Push) Insertion and Pop (Deletion) 

Push (Insertion) in Stack

Stack में नया element insert कराना बहुत आसान होता है। इसके लिए top pointer से जाँच करते हैं कि memory में नए element के लिए खाली स्थान है या नही। यदि memory में नए element के लिए खाली स्थान नही होता है तो overflow massage display करते हैं और return ले लेते हैं। और अगर यदि memory में नए element के लिए खाली स्थान होता है तो top pointer को अपने स्थान से एक स्थाम ऊपर set करते हैं। अंत मे top के नए स्थान पर नए element को insert कराते हैं और return ले लेते हैं।

Pop (Deletion) in the stack

Stack से पुराने element delete करना बहुत आसान होता है। इसके लिए top pointer से जांच करते हैं कि stack खाली तो नहीं है। यदि stack खाली होता है तो underflow manage display करते हैं और return ले लेते हैं। और यदि stack खाली नही होता तो इसके top element को store कर लेते हैं। अंत मे top pointer को अपने स्थान से नीचे set करते हैं जिससे top element delete हो जाता है और return ले लेते हैं।

Arithmetic Expressions and its Evaluation

अंकगणितीय व्यंजक (Arithmetic expression) एक ऐसे अंकगणितीय कथक (Arithmetic statement) होता है जो operators and operands (constants/variables) को एकसाथ संयोजित करके बनाया जाता है। इसका प्रयोग अंकगणितीय समस्याओं को हल करने ले लिए किया जाता है। जब भी हमे किसी अंकगणितीय समस्या के हल को व्यक्त करना होता है तो हम इसे एक arithmetic expression के रूप में लिखते हैं। कुछ अंकगणितीय समस्याएं एवं उनको हल करने के लिए arithmetic expression निम्नलिखित हैं:

Notation to Express Arithmetic Expressions

Arithmetic Expressions को व्यक्त करने के लिए निम्नलिखित तीन प्रकार के notation का प्रयोग किया जाता है:

1. Infix Notation
2. Postfix Notation
3. Pre Notation

Infix Notation

Arithmetic expression को व्यक्त करने की इस संकेत विधि में operators को operands के बीच के रख जाता है। यह सामान्य प्रकार का arithmetic expression होता है जिसका प्रयोग गणित में किया जाता हैं। इसमें operators एवं operands का position का निर्धारण नहीं करता है कि विभिन्न operation किस क्रम में होंगे। 

इसमें operations के क्रम को निर्धारित करने के लिए operator precedence rule का प्रयोग किया जाता है।
उदाहरण: a+b, a-b, a*b, a/b, a^b आदि।

Algorithm to Evaluate Infix Expression

Step 1: Infix Expression (1) को बार बार left to right शुरू से अंत तक scan करते चले जाते हैं जब तक कि expression पूरी तरह evaluate न हो जाए तथा प्रत्येक बार scan करने के बाद step 2 step 3 को करते हैं।

Step 2: Precedence rule के अनुसार यह decide करते हैं कि कौन से operation का precedence सबसे अधिक है।

Step 3: सबसे अधिक precedence वाले operation को करते हैं।

Some Infix Expressions with their Solutions

(1) 5+3*4

      5+12

      17

Postfix Notation

Arithmetic expression को व्यक्त करने की इस संकेत विधि में operators को operands के बाद में रखा जाता है। यह विशेष प्रकार का arithmetic expression होता है जिसका प्रयोग computer में किया जाता है। इसमें operators एवं operands का position ही निर्धारित करता है कि विभिन्न operation किस क्रम में होंगे। 

अतः इसमें operations के क्रम को निर्धारित करने के लिए किसी प्रकार के operator precedence rule का प्रयोग नही किया जाता है। computer समान्यतः infix notation में लिखे गए arithmetic expression को पहले postfix notation में परिवर्तित करता है फिर इसे stack की सहायता से हल करता है।

Algorithm to Evaluate Postfix Expression

Step 1: Postfix expression (P) के एक-एक character को left to right scan करते चले जाते हैं जब तक कि expression पूरी तरह से evaluate न हो जाए तथा प्रत्येक बार scan करने के बाद step 2 और step 3 को करते हैं।

Step 2: यदि operand (constant/variable) प्राप्त होता है तो इसे stack में push करते हैं।

Step 3: यदि कोई operator (+ - * / ^) प्राप्त होता है तो stack के top (a) और next to top (b) element को pop करते हैं और b*c के क्रम में गणना कर परिणाम को पुनः stack में push करते हैं।

Some Postfix Expressions with their Solutions

Prefix Notation

Arithmetic expression को व्यक्त करने की इस संकेत विधि में operators को operands के पहले रखा जाता है। इसे polish notation भी कहा जाता है। Postfix expression की तरह इसमे भी operators एवं operands का position ही यह निर्धारित करता है कि विभिन्न operation किस क्रम में होंगे। 

अतः इसमें भी operations के क्रम को निर्धारित करने के लिए किसी प्रकार के operator precedence rule का प्रयोग नही किया जाता है। Prefix expression  को भी postfix expression की तरह ही stack की सहायता से हल किया जाता है लेकिन इसमें scanning right to left होता है और गणना का क्रम a*b होता है।

Algorithm to Evaluate Postfix Expression

Step 1: Postfix expression (P) के एक-एक character को right to left scan करते चले जाते हैं जब तक कि expression पूरी तरह से evaluate न हो जाए तथा प्रत्येक बार scan करने के बाद step 2 और step 3 को करते हैं।

Step 2: यदि operand (constant/variable) प्राप्त होता है तो इसे stack में push करते हैं।

Step 3: यदि कोई operator (+ - * / ^) प्राप्त होता है तो stack के top (a) और next to top (b) element को pop करते हैं और a*b के क्रम में गणना कर परिणाम को पुनः stack में push करते हैं।

Some Prefix Expressions with their Solutions

Application of Stack:

1. Programming languages में expressions को evaluate करने के लिए Stack का प्रयोग किया जाता है।
2. एक notation में लिखे हुए expression को दूसरे notation में बदलने के लिए Stack का प्रयोग किया जाता है।
3. जब एक function दूसरे function को call करता है तो Stack का प्रयोग किया जाता है।
4. Recursive function को हल करने के लिए Stack का प्रयोग किया जाता है।
5. Stack का प्रयोग number base को बदलने के लिए भी किया जाता है।

Difference Between Stack and Queue:

Stack	Queue
(1) stack में elements का insertion एवं deletion एक ही ओर से होता है।	(1) Queue में elements का insertion एवं deletion दूसरी ओर से होता है।
(2) इसमें एक open end और एक close end होता है। open end को top कहते हैं।	(2) इसमें दो open end होता है। जिन्हें front और rear कहते हैं।
(3) इसमें elements को store एवं retrieve करना LIFO क्रम में होता है।	(3) इसमें elements को store एवं retrieve करना FIFO क्रम में होता है।
(4) इसमें store एवं retrieve operations को विशेष रूप से push और pop कहते हैं।	(4) इसमें store एवं retrieve operations को सामान्य रूप से insertion और deletion कहते हैं।
(5) इसका प्रयोग मुख्यतः expressions को हल करने के लिए किया जाता है।	(5) इसका प्रयोग मुख्यतः processor job scheduling में किया जाता है।
(6) उदाहरण-किसी पार्टी में एक के ऊपर एक रखे प्लेट।	(6) उदाहरण-किसी पार्टी में प्लेट लेने के लिए एक के पीछे एक खड़े लोग।

Stack क्या हैं? (Operations, Expressions, Algorithm in Stack in Hindi)

Friends, मैं पूरी कोशिश करता हु की इन Post के माध्यम से आपको जो संदेह करना पूरी तरह से clear हो जाये फिर भी आप को सुझाव देना चाहते हैं तो इसके लिए आप comment box के माध्यम से दे सकते हैं।

Friends मुझे बहुत पूरी उम्मीद है कि ये पोस्ट आपको जरूर पसंद आई होगी और मुझे खुसी है कि मैं आपके लिए कुछ का जानकारी इस ब्लॉग के माध्यम से दे सका और इसी प्रकार किसी बारे में जानकारियां प्राप्त करना हैं तो इसके लिए आप comment box के माध्यम से दे सकते हैं Post अच्छी लगी तो इसे दोस्तो के Share जरूर करें धन्यवाद।