Data Structures
पाठ · #3 / 11

स्टैक (Stacks)

LIFO — सबसे नया अंदर, सबसे नया बाहर

Stack · LIFO

size0 top∅
empty stack — push to begin
init

Mini-game · balanced brackets (powered by a stack)

Type an expression. Brackets must open and close in mirror order — ({[…]}) is fine, ([)] is not. The parser uses a stack: every opener pushes the expected closer; every closer must match the value on top. Watch how each character is classified, and how the stack grows and shrinks below.

try
  • opener → push
  • closer matches top
  • mismatch / underflow
  • ignored char
…

खुद आज़माएँ: टोकनों को टॉवर पर push कीजिए; फिर pop कर हटाइए। उसके नीचे: कोई भी कोष्ठक (bracket) वाली स्ट्रिंग parens गेम में डालिए — स्टैक ही उसका पार्सर है।

यह क्यों मायने रखता है

स्टैक हर जगह हैं: फ़ंक्शन कॉल, undo/redo, अभिव्यक्ति (expression) पार्सिंग, backtracking एल्गोरिथ्म। स्टैक को समझना यानी यह समझना कि प्रोग्राम कैसे चलते हैं और उन समस्याओं को कैसे हल किया जाए जिनमें कुछ 'याद रखना' और 'वापस लौटाना' ज़रूरी होता है।

मूल विचार

किसी कैफ़ेटेरिया में रखी प्लेटों की ढेरी को सोचिए। आप सिर्फ़ ऊपर से ही जोड़ या हटा सकते हैं। सबसे आख़िर में रखी प्लेट सबसे पहले उठती है।

सबसे बाद में अंदर, सबसे पहले बाहर (Last In, First Out — LIFO)।

यह सीधी-सी पाबंदी ग़ज़ब की ताक़तवर है:

सारे ऑपरेशन O(1) हैं — आप कभी सिर्फ़ ऊपरी सिरे को ही छूते हैं।

मुख्य बातें

और गहराई में

कॉल स्टैक ही वह वजह है जिससे रिकर्सिव फ़ंक्शन काम करते हैं — हर कॉल के स्थानीय चर (local variables) स्टैक पर push होते हैं और लौटने पर pop हो जाते हैं। जब रिकर्शन बहुत गहरा चला जाता है तो स्टैक ओवरफ़्लो होता है। स्टैक infix से postfix संकेतन में बदलने (shunting-yard एल्गोरिथ्म) और postfix अभिव्यक्तियों को एक ही पास में हल करने की भी कुंजी हैं।

असल दुनिया में

गणितीय ब्यौरा

Time Complexity
Push: O(1)
Pop: O(1)
Peek: O(1)
Search: O(n)
Space
n तत्वों के लिए O(n)

क्रियान्वयन (Implementation)

स्टैक ऑपरेशन

let mut stack = Vec::new();

stack.push(1);  // Push onto top
stack.push(2);
stack.push(3);  // Stack: [1, 2, 3] (3 is top)

let top = stack.pop();  // Returns Some(3)
let peek = stack.last(); // Returns Some(&2)

चिर-परिचित उपयोग

अभ्यास

तीन चिर-परिचित स्टैक सवाल — हर एक LIFO अनुशासन को इस्तेमाल करने का अलग तरीक़ा है:

→ सभी अभ्यास सवाल देखें