स्टैक क्या है?
डेटा संरचना डेटा को सहेजने और व्यवस्थित करने का तरीका है ताकि उसका अच्छा उपयोग हो सके। स्टैक एक रेखीय डेटा संरचना है जिसमें जोड़ना और हटाना दोनों केवल एक सिरे पर होते हैं, जिसे टॉप कहते हैं।
इसलिए आख़िर में जुड़ा आइटम सबसे पहले हटता है। इस नियम को LIFO (Last In, First Out) कहते हैं।
रोज़ के स्टैक: थालियों का ढेर, कलाई पर चूड़ियाँ, एक के ऊपर एक रखी किताबें।
स्टैक पर काम: push, pop, peek, isEmpty
- PUSH: टॉप पर आइटम जोड़ना।
- POP: टॉप का आइटम हटाकर लौटाना।
- PEEK (या TOP): बिना हटाए टॉप का आइटम पढ़ना।
- isEmpty: जाँचना कि स्टैक ख़ाली है या नहीं।
- size: आइटमों की संख्या।
ओवरफ़्लो और अंडरफ़्लो
अंडरफ़्लो: ख़ाली स्टैक से pop (या peek) करना। ओवरफ़्लो: भरे हुए स्टैक में push करना (केवल तय आकार वाले स्टैक में)। पायथन लिस्ट अपने-आप बढ़ती है, इसलिए हम मुख्यतः अंडरफ़्लो जाँचते हैं।
पायथन लिस्ट से स्टैक बनाना
लिस्ट के अंत को टॉप मानें। तब दोनों काम तेज़ होते हैं।
def isEmpty(stk):
return len(stk) == 0
def push(stk, item):
stk.append(item)
def pop(stk):
if isEmpty(stk):
return 'Underflow'
return stk.pop()
def peek(stk):
if isEmpty(stk):
return 'Underflow'
return stk[-1]
def display(stk):
for i in range(len(stk) - 1, -1, -1):
print(stk[i]) # पहले टॉप
s = []
push(s, 10); push(s, 20); push(s, 30)
print(pop(s)) # 30
print(peek(s)) # 20display ऊपर से नीचे छापता है, इसलिए लूप आख़िरी इंडेक्स से 0 तक उल्टा चलता है।
बोर्ड जैसा प्रश्न: शर्त वाले रिकॉर्ड push करना
कई प्रश्नों में कुछ ही आइटम push करके फिर सब pop करने होते हैं।
# 75 से ज़्यादा अंक वाले छात्रों के नाम push करो, फिर सब pop
D = {'Asha': 92, 'Ravi': 70, 'Zoya': 81, 'Om': 64}
st = []
def push_top(D):
for name in D:
if D[name] > 75:
st.append(name)
def pop_all():
while st:
print(st.pop(), end=' ')
print('\nStack empty')
push_top(D); pop_all() # Zoya Ashaध्यान दें: Asha पहले push हुई, इसलिए आख़िर में निकली।
स्टैक कहाँ काम आता है?
- एडिटर में Undo/Redo।
- ब्राउज़र का Back बटन।
- शब्द या लिस्ट उल्टी करना: हर अक्षर push, फिर सब pop।
- कोड या व्यंजक में कोष्ठक संतुलित हैं या नहीं, जाँचना।
- फ़ंक्शन कॉल: पायथन कॉल स्टैक रखता है; सबसे बाद में बुलाया फ़ंक्शन पहले पूरा होता है।
करके देखें: स्टैक से अपना नाम उल्टा कीजिए
5 पर्चियाँ लीजिए। हर पर्ची पर अपने नाम का एक अक्षर लिखकर एक-एक करके ढेर बनाइए। अब ऊपर से एक-एक उठाकर अक्षर पढ़िए। नाम उल्टा निकलेगा! फिर यही पायथन में लिखिए: हर अक्षर append से push, और लिस्ट ख़ाली होने तक pop। 3D के आख़िरी कदम में हर pop से पहले अनुमान जाँचिए।
मुख्य सूत्र और परिभाषाएँ
- LIFO: आख़िर में आया, पहले गया
- push → L.append(x) · pop → L.pop() · peek → L[-1] · isEmpty → len(L) == 0
- अंडरफ़्लो: ख़ाली स्टैक पर pop/peek · ओवरफ़्लो: भरे तय आकार के स्टैक पर push
हल किए गए उदाहरण
1. ख़ाली स्टैक से शुरू: push(5), push(8), pop(), push(3), push(9), pop(), pop()। क्या बचा और क्या निकला?
[5] → [5,8] → 8 निकला → [5] → [5,3] → [5,3,9] → 9 निकला → 3 निकला → [5]। निकलने का क्रम: 8, 9, 3। बचा: [5]।
2. स्टैक से स्ट्रिंग उल्टी करने वाला फ़ंक्शन लिखिए।
def rev(s): st = [] for ch in s: st.append(ch) out = '' while st: out += st.pop() return out print(rev('CODE')) # EDOC
3. क्या छपेगा? st = [1, 2, 3]; st.append(4); st.pop(); print(st[-1], len(st))
append के बाद [1,2,3,4]। pop ने 4 हटाया → [1,2,3]। st[-1] = 3, len = 3। आउटपुट: 3 3।
4. लिस्ट NUM की सम संख्याएँ स्टैक EVEN में push करके फिर सब pop करके छापिए।
NUM = [12, 7, 4, 9, 20] EVEN = [] for n in NUM: if n % 2 == 0: EVEN.append(n) while EVEN: print(EVEN.pop(), end=' ') # 20 4 12 print('Stack Empty')
5. हम अंत पर append()/pop() क्यों करते हैं, आगे insert(0, x)/pop(0) क्यों नहीं?
दोनों स्टैक बनाते हैं, पर अंत पर जोड़ना-हटाना तेज़ है। आगे करने पर पायथन को बाकी सारे आइटम एक जगह खिसकाने पड़ते हैं, जो बड़ी लिस्ट में धीमा है।
6. '(a+b)*(c-d))' में कोष्ठक संतुलित हैं या नहीं, जाँचने का फ़ंक्शन लिखिए।
def balanced(e): st = [] for ch in e: if ch == '(': st.append(ch) elif ch == ')': if not st: return False # अंडरफ़्लो: फ़ालतू ')' st.pop() return len(st) == 0 print(balanced('(a+b)*(c-d))')) # False
आम गलतियाँ
- pop(0) लिखना, जो टॉप नहीं, नीचे वाला आइटम हटाता है।
- ख़ाली है या नहीं जाँचे बिना pop करना (IndexError: pop from empty list)।
- सोचना कि peek आइटम हटाता है; वह केवल stk[-1] पढ़ता है।
- स्टैक इंडेक्स 0 से छापकर उसे टॉप से छापना कहना; टॉप आख़िरी इंडेक्स है।