मेन्यू

चित्रण के साथ C ++ में स्टैक डेटा संरचना

stack data structure c with illustration

अनुभवी पीडीएफ के लिए sql डेवलपर साक्षात्कार प्रश्न और उत्तर

समस्याओं को खत्म करने के लिए हमारे साधन का प्रयास करें

सी ++ में स्टैक के बारे में जानने के लिए आपको बस इतना ही चाहिए।

स्टैक एक मौलिक डेटा संरचना है जिसका उपयोग तत्वों को रैखिक फैशन में संग्रहीत करने के लिए किया जाता है।

स्टैक इस प्रकार है LIFO (अंतिम में, पहले बाहर) आदेश या दृष्टिकोण जिसमें ऑपरेशन किए जाते हैं। इसका मतलब यह है कि जिस तत्व को पिछली बार स्टैक में जोड़ा गया था वह स्टैक से निकाला जाने वाला पहला तत्व होगा।

=> सभी के लिए संपूर्ण C ++ प्रशिक्षण श्रृंखला देखने के लिए यहां जाएं।

ढेर

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

C ++ में ढेर

एक स्टैक वास्तविक जीवन के ढेर या उन चीजों के ढेर के समान है जिन्हें हम एक के ऊपर एक स्टैक करते हैं।

नीचे दिए गए स्टैक का सचित्र प्रतिनिधित्व है।

स्टैक का सचित्र प्रतिनिधित्व

जैसा कि ऊपर दिखाया गया है, एक-दूसरे के ऊपर ढेर प्लेटों का ढेर है। यदि हम इसमें एक और आइटम जोड़ना चाहते हैं, तो हम इसे स्टैक के शीर्ष पर जोड़ते हैं जैसा कि ऊपर की आकृति (बाएं हाथ की ओर) में दिखाया गया है। स्टैक में एक आइटम जोड़ने के इस ऑपरेशन को 'कहा जाता है' धक्का दें ”।

दाईं ओर, हमने एक विपरीत ऑपरेशन दिखाया है यानी हम एक आइटम को स्टैक से हटाते हैं। यह भी उसी छोर से यानी स्टैक के ऊपर से किया जाता है। इस ऑपरेशन को “कहा जाता है। पॉप ”।

जैसा कि उपरोक्त आंकड़े में दिखाया गया है, हम देखते हैं कि पुश और पॉप एक ही छोर से किए जाते हैं। यह LIFO आदेश का पालन करने के लिए स्टैक बनाता है। वह स्थिति या अंत जिसमें से वस्तुओं को धक्का दिया जाता है या स्टैक से / के लिए बाहर निकाला जाता है, उसे 'कहा जाता है' ढेर के ऊपर ”।

प्रारंभ में, जब स्टैक में कोई आइटम नहीं होते हैं, तो स्टैक के शीर्ष को -1 पर सेट किया जाता है। जब हम स्टैक में एक आइटम जोड़ते हैं, तो स्टैक के शीर्ष को 1 से बढ़ा दिया जाता है यह दर्शाता है कि आइटम जोड़ा गया है। जब इसका विरोध किया जाता है, तो स्टैक के ऊपर पॉपअप होने पर स्टैक के शीर्ष को 1 से घटाया जाता है।

इसके बाद, हम स्टैक डेटा संरचना के कुछ बुनियादी ऑपरेशन देखेंगे जिन्हें स्टैक को लागू करते समय हमें आवश्यकता होगी।

बुनियादी संचालन

निम्नलिखित मूल ऑपरेशन हैं जो स्टैक द्वारा समर्थित हैं।

  • धक्का दें - एक तत्व को ढेर में जोड़ता या धकेलता है।
  • पॉप - स्टैक से किसी तत्व को निकालता या निकालता है।
  • झांकना - स्टैक के शीर्ष तत्व को प्राप्त करता है, लेकिन इसे हटाता नहीं है।
  • पूर्ण है - यदि स्टैक भरा हुआ है तो टेस्ट।
  • खाली है - यदि स्टैक खाली है तो टेस्ट करें।

चित्रण

स्टैक इलस्ट्रेशन

उपरोक्त चित्रण ऑपरेशन के अनुक्रम को दर्शाता है जो स्टैक पर किया जाता है। प्रारंभ में, स्टैक खाली है। एक खाली स्टैक के लिए, स्टैक का शीर्ष -1 पर सेट है।

अगला, हम स्टैक में तत्व 10 को धक्का देते हैं। हम देखते हैं कि स्टैक का शीर्ष अब तत्व 10 को इंगित करता है।

अगला, हम तत्व 20 के साथ एक और धक्का ऑपरेशन करते हैं, जिसके परिणामस्वरूप स्टैक के शीर्ष अब 20 को इंगित करता है। यह राज्य तीसरा आंकड़ा है।

अब अंतिम आंकड़े में, हम एक पॉप () ऑपरेशन करते हैं। पॉप ऑपरेशन के परिणामस्वरूप, स्टैक के शीर्ष पर बताया गया तत्व स्टैक से हटा दिया जाता है। इसलिए आकृति में, हम देखते हैं कि तत्व 20 को स्टैक से हटा दिया गया है। इस प्रकार स्टैक का शीर्ष अब 10 को इंगित करता है।

इस तरह, हम आसानी से स्टैक द्वारा उपयोग किए जाने वाले लिफो दृष्टिकोण को बाहर कर सकते हैं।

कार्यान्वयन

# 1) Arrays का उपयोग करना

निम्नलिखित सरणियों का उपयोग करके स्टैक का C ++ कार्यान्वयन निम्नलिखित है:

#include using namespace std; #define MAX 1000 //max size for stack class Stack { int top; public: int myStack(MAX); //stack array Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //pushes element on to the stack bool Stack::push(int item) { if (top >= (MAX-1)) { cout << 'Stack Overflow!!!'; return false; } else { myStack(++top) = item; cout<

आउटपुट:

स्टैक पुश

दो

४

६

स्टैक पॉप:

६

४

दो

आउटपुट में, हम देख सकते हैं कि तत्वों को एक क्रम में स्टैक में धकेल दिया जाता है और रिवर्स ऑर्डर में स्टैक से बाहर पॉपअप किया जाता है। यह स्टैक के लिए LIFO (लास्ट इन, फर्स्ट आउट) दृष्टिकोण प्रदर्शित करता है।

स्टैक के उपरोक्त सरणी कार्यान्वयन के लिए, हम यह निष्कर्ष निकाल सकते हैं कि इसे लागू करना बहुत आसान है क्योंकि इसमें कोई संकेत शामिल नहीं हैं। लेकिन एक ही समय में, स्टैक का आकार स्थिर होता है और स्टैक गतिशील रूप से बढ़ या सिकुड़ नहीं सकता है।

अगला, हम जावा प्रोग्रामिंग भाषा में सरणियों का उपयोग करके स्टैक को लागू करेंगे।

class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack() = new int(MAX); boolean isEmpty() { return (top = (MAX-1)) { System.out.println('Stack Overflow'); return false; } else { myStack(++top) = item; System.out.println(item); return true; } } int pop() { if (top <0) { System.out.println('Stack Underflow'); return 0; } else { int item = myStack(top--); return item; } } } //Main class code class Main { public static void main(String args()) { Stack stack = new Stack(); System.out.println('Stack Push:'); stack.push(1); stack.push(3); stack.push(5); System.out.println('Stack Pop:'); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } }

आउटपुट:

स्टैक पुश:

1

३

५

स्टैक पॉप:

५

३

1

कार्यान्वयन तर्क C ++ कार्यान्वयन के समान है। आउटपुट में पुश करने की एलआईएफओ तकनीक दिखाई देती है और स्टैक से / के लिए तत्वों को बाहर निकालना है।

जैसा कि पहले ही कहा गया है कि सरणियों का उपयोग करते हुए स्टैक कार्यान्वयन सबसे सरल कार्यान्वयन है, लेकिन स्थैतिक प्रकृति का है क्योंकि हम स्टैक को गतिशील रूप से विकसित या सिकोड़ नहीं सकते हैं।

# 2) एक लिंक्ड सूची का उपयोग करना

अगला, हम C ++ और Java दोनों में एक लिंक्ड सूची का उपयोग करके स्टैक ऑपरेशंस को लागू करते हैं। सबसे पहले, हम C ++ कार्यान्वयन का प्रदर्शन करेंगे।

#include using namespace std; // class to represent a stack node class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode *root) { return !root; } void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; } int main() { StackNode* root = NULL; cout<<'Stack Push:'<

आउटपुट:

स्टैक पुश:

100

200 रु

300

शीर्ष तत्व 300 है

स्टैक पॉप:

300

200 रु

100

शीर्ष तत्व -1 है

अगला, हम एक लिंक की गई सूची का उपयोग करके स्टैक के जावा कार्यान्वयन को प्रस्तुत करते हैं।

class LinkedListStack { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int new_data) { StackNode newNode = new StackNode(new_data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } } class Main{ public static void main(String() args) { LinkedListStack stack = new LinkedListStack(); System.out.println('Stack Push:'); stack.push(100); stack.push(200); stack.push(300); System.out.println('Top element is ' + stack.peek()); System.out.println('Stack Pop:'); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println('Top element is ' + stack.peek()); } }

आउटपुट:

स्टैक पुश:

100

200 रु

300

शीर्ष तत्व 300 है

स्टैक पॉप:

300

200 रु

100

ढेर खाली है

कैसे sql इंजेक्शन के लिए परीक्षण करने के लिए

शीर्ष तत्व -2147483648 है

हमने अभी-अभी सी + + और जावा कार्यान्वयन को लिंक वाली सूचियों का उपयोग करके स्टैक के लिए देखा है। हम लिंक किए गए सूची के नोड के रूप में प्रत्येक स्टैक प्रविष्टि का प्रतिनिधित्व करते हैं। इस कार्यान्वयन का सबसे महत्वपूर्ण लाभ यह है कि यह गतिशील है। इसका मतलब है कि हम अपनी आवश्यकता के अनुसार स्टैक के आकार को बढ़ा या छोटा कर सकते हैं।

यह सरणियों का उपयोग करके स्टैक कार्यान्वयन के मामले के विपरीत है जिसमें हमें पहले से आकार घोषित करना होगा और इसे गतिशील रूप से नहीं बदल सकता है।

इस कार्यान्वयन के लिए चुनाव यह है कि जैसा कि हम हर जगह पॉइंटर्स का उपयोग करते हैं, यह सरणी कार्यान्वयन की तुलना में थोड़ी बहुत जगह लेता है।

ढेर के अनुप्रयोग

आइए हम स्टैक डेटा संरचना के कुछ अनुप्रयोगों पर चर्चा करें। स्टैक डेटा संरचना का उपयोग सॉफ्टवेयर प्रोग्रामिंग में अनुप्रयोगों की एक श्रेणी में मुख्य रूप से इसकी सादगी और कार्यान्वयन में आसानी के कारण किया जाता है।

हम नीचे दिए गए स्टैक के कुछ अनुप्रयोगों का संक्षेप में वर्णन करेंगे:

# 1) Infix To Postfix Expressions

किसी भी सामान्य अंकगणित की अभिव्यक्ति फॉर्म का है ऑपरैंड 1 ओपी ऑपरेंड 2 ।

ऑपरेटर ओपी की स्थिति के आधार पर, हमारे पास निम्न प्रकार के भाव हैं:

  • इन्फ़िक्स - इनफ़िक्स एक्सप्रेशन का सामान्य रूप है “ ऑपरैंड 1 ओपी ऑपरेंड 2 ”। यह अभिव्यक्ति का मूल रूप है और हम हर समय गणित में उपयोग करते हैं।
  • उपसर्ग - जब एक ऑपरेटर को ऑपरेंड से पहले रखा जाता है, तो यह एक उपसर्ग अभिव्यक्ति है। Infix अभिव्यक्ति का सामान्य रूप है “ ओपी ऑपरेंड 1 ऑपरेंड 2 ”।
  • पोस्टफ़िक्स - पोस्टफिक्स अभिव्यक्तियों में, ऑपरेटर द्वारा पहले ऑपरेटर लिखा जाता है। इसका रूप 'ऑपरेंड 1 ऑपरेंड 2 ओपी' है।

अभिव्यक्ति पर विचार करें “a + b * c ' । संकलक अभिव्यक्ति को बाएं से दाएं या दाएं से बाएं तक स्कैन करता है। ऑपरेटर की पूर्वता और अनुरूपता का ख्याल रखते हुए, यह पहले अभिव्यक्ति b * c का मूल्यांकन करने के लिए अभिव्यक्ति को स्कैन करेगा। अगला, इसे फिर से b * c के परिणाम को जोड़ने के लिए अभिव्यक्ति को स्कैन करना होगा।

जैसे-जैसे भाव अधिक से अधिक जटिल होते जाते हैं, बार-बार अभिव्यक्ति को स्कैन करते हुए इस तरह का दृष्टिकोण अक्षम हो जाता है।

इस अक्षमता को दूर करने के लिए, हम अभिव्यक्ति को उपसर्ग या उपसर्ग में परिवर्तित करते हैं, ताकि उन्हें एक स्टैक संरचना का उपयोग करके आसानी से मूल्यांकन किया जा सके।

# 2) अभिव्यक्ति पार्सिंग / मूल्यांकन

स्टैक का उपयोग करके, हम वास्तविक अभिव्यक्ति मूल्यांकन भी कर सकते हैं। इसमें, अभिव्यक्ति को बाएं से दाएं स्कैन किया जाता है, और ऑपरेंड को स्टैक पर धकेल दिया जाता है।

जब भी किसी ऑपरेटर का सामना किया जाता है, तो ऑपरेंड को पॉप आउट किया जाता है और ऑपरेशन किया जाता है। ऑपरेशन का परिणाम फिर से स्टैक में धकेल दिया जाता है। इस तरह से स्टैक का उपयोग करके अभिव्यक्ति का मूल्यांकन किया जाता है और अभिव्यक्ति का अंतिम परिणाम आमतौर पर स्टैक का वर्तमान शीर्ष होता है।

# 3) ट्री ट्रैवर्सल्स

ट्री डेटा संरचना को प्रत्येक नोड को कई तरीकों से देखने के लिए ट्रैवर्स किया जा सकता है और यह निर्भर करता है कि हमारे द्वारा रूट नोड कब विजिट किया गया है।

  • inOrder traversal
  • त्राटक Traversal
  • पोस्टऑर्डर ट्रैवरल

पेड़ को कुशलता से पार करने के लिए, हम स्टैक पर मध्यवर्ती नोड्स को पुश करने के लिए स्टैक डेटा संरचना का उपयोग करते हैं ताकि हम ट्रैवर्सल के क्रम को बनाए रखें।

# 4) एल्गोरिदम को छाँटना

स्टैक डेटा संरचनाओं का उपयोग करके क्विकसॉर्ट जैसे छंटनी एल्गोरिदम को अधिक कुशल बनाया जा सकता है।

# 5) हनोई के टावर

यह एक क्लासिक समस्या है जिसमें n की संख्या और तीन टावर शामिल हैं और इस समस्या में डिस्क को एक टावर से दूसरे टॉवर में ले जाना शामिल है जिसमें मध्यवर्ती के रूप में इस्तेमाल किया जाने वाला तीसरा टॉवर है।

स्टैक का उपयोग करके इस समस्या से कुशलता से निपटा जा सकता है क्योंकि हम डिस्क को स्टैक पर ले जाने के लिए धक्का देते हैं क्योंकि स्टैक मूल रूप से डिस्क को स्थानांतरित करने के लिए उपयोग किए जाने वाले टॉवर के रूप में कार्य करता है।

निष्कर्ष

स्टैक एक प्रोग्राम के रूप में सबसे सरल डेटा संरचना है और इसे लागू करना आसान है। इसमें LIFO (आखिरी में, पहले बाहर) दृष्टिकोण का उपयोग किया गया है जिसका अर्थ है कि अंतिम दर्ज किया गया तत्व वह है जिसे पहले हटा दिया गया है। ऐसा इसलिए है क्योंकि स्टैक केवल एक छोर को जोड़ने (पुश) और हटाने (पॉप) तत्वों का उपयोग करता है।

सॉफ्टवेयर प्रोग्रामिंग में स्टैक डेटा संरचना के कई उपयोग हैं। उनमें से प्रमुख अभिव्यक्ति मूल्यांकन है। अभिव्यक्ति मूल्यांकन में इन्फिक्स से पोस्टफ़िक्स या प्रीफ़िक्स में अभिव्यक्ति को परिवर्तित करना भी शामिल है। इसमें अंतिम परिणाम का उत्पादन करने के लिए अभिव्यक्ति का मूल्यांकन करना भी शामिल है।

इस ट्यूटोरियल में, हमने स्टैक के चित्रण और कार्यान्वयन और इसके विभिन्न कार्यों को देखा है।

हमारे आगामी ट्यूटोरियल में, हम कतार डेटा संरचना के बारे में विस्तार से जानेंगे।

=> विशेषज्ञों से पूरा सी ++ कोर्स के लिए यहां जाएं।

अनुशंसित पाठ

^