Python Stack: LIFO डेटा स्ट्रक्चर लागू करना

जब भी आप किसी गलती को पूर्ववत करने के लिए Ctrl+Z दबाते हैं, अपने ब्राउज़र में बैक बटन पर क्लिक करते हैं, या किसी recursive फ़ंक्शन को उसके परिणाम खोलते देखते हैं, तो आप एक stack पर निर्भर होते हैं। क्योंकि वे आपके दैनिक सॉफ़्टवेयर में गहराई से समाहित हैं, आप अक्सर बिना जाने ही Stacks के साथ इंटरैक्ट करते हैं।

इस लेख में, हम देखेंगे कि stack क्या है, stacks के पीछे की मूल तर्कशक्ति, Python की built-in लाइब्रेरीज़ का उपयोग करते हुए विभिन्न implementation रणनीतियों की तुलना, और उन्हें algorithmic समस्याएँ सुलझाने में कैसे लागू करें।

मैं सुझाता हूँ कि आप हमारा on Writing Efficient Python Code कोर्स लें ताकि आप अपने डेटा स्ट्रक्चर ज्ञान को performance best practices से जोड़ सकें, और एक त्वरित संदर्भ के लिए Python Basics Cheat Sheet को handy रखें। 

Python में Stack क्या है?

कोड देखने से पहले, उस वैचारिक आधार को समझना महत्वपूर्ण है जो Python stack को इतना शक्तिशाली टूल बनाता है। आइए stacks के पीछे के मूल सिद्धांत पर नज़र डालें और देखें कि वे अन्य सामान्य डेटा स्ट्रक्चर्स से कैसे भिन्न हैं।

LIFO डेटा स्ट्रक्चर

Stack एक linear डेटा स्ट्रक्चर है जो Last-In-First-Out (LIFO) सिद्धांत का पालन करता है। इसका मतलब है कि सबसे हाल में जोड़ा गया तत्व सबसे पहले हटाया जाता है। इसे कैंटीन में प्लेटों के ढेर जैसा समझें। आप नई प्लेटें ऊपर रखते हैं और हमेशा सबसे ऊपर की प्लेट पहले उठाते हैं। आप कभी भी बीच या नीचे से प्लेट नहीं निकालते। पहुँच पूरी तरह से ऊपर तक सीमित है।

यह एकल बाधा, केवल-ऊपर पहुँच, ही stacks को उनकी predictability और दक्षता देती है। हर तत्व एक ही सिरा से प्रवेश करता है और निकलता है, जिससे operations सरल और तेज़ रहते हैं।

ध्यान देने योग्य एक बात यह है कि Python में कुछ अन्य भाषाओं की तरह कोई समर्पित, primitive stack प्रकार नहीं आता। कोई stack कीवर्ड या built-in class नहीं है। इसके बजाय, Python ठोस built-in विकल्प देता है lists, collections.deque, और queue.LifoQueue जैसे, जो सभी stack की तरह व्यवहार कर सकते हैं। हम इन प्रत्येक implementations को इस लेख में आगे विस्तार से देखेंगे।

Stack बनाम अन्य डेटा स्ट्रक्चर

यह समझना कि stack क्या है, तब और स्पष्ट हो जाता है जब आप देखते हैं कि वह क्या नहीं है। जिन दो स्ट्रक्चर्स की अक्सर stacks से तुलना की जाती है, वे हैं queues और standard Python lists।

Stack बनाम queue

Queue First-In-First-Out (FIFO) सिद्धांत का पालन करती है, जो stack के विपरीत है। Queue में तत्व पीछे जोड़े जाते हैं और आगे से हटाए जाते हैं, जैसे टिकट काउंटर पर लगी लाइन। Stacks और queues दोनों linear हैं और दोनों ही तत्वों तक पहुँच को सीमित करते हैं, लेकिन वे यह काम विपरीत दिशाओं में करते हैं। 

गलत चुनाव चुपचाप किसी एल्गोरिथ्म की तर्कशक्ति बिगाड़ सकता है। उदाहरण के लिए, depth-first search में stack की जगह queue रखने से वह breadth-first search बन जाएगा और नतीजे पूरी तरह अलग होंगे।

Stack बनाम list

दूसरी ओर, एक standard Python list random access देती है। आप किसी भी index पर तत्व पढ़, insert या delete कर सकते हैं, जैसे my_list[3] या my_list.insert(2, value)। यह लचीलापन कई संदर्भों में उपयोगी है, लेकिन इसका यह भी मतलब है कि आपको स्ट्रक्चर के बीच में मौजूद तत्वों तक गलती से पहुँचने या उन्हें बदल देने से कुछ भी नहीं रोकता। 

जब आप ऐसे एल्गोरिथ्म लागू कर रहे हों जो सख्त LIFO क्रम पर निर्भर हों, जैसे backtracking, syntax parsing, या undo फ़ंक्शनलिटी, तो list का अनियंत्रित स्वभाव सूक्ष्म बग्स ला सकता है।

यही वजह है कि stack का restricted access पैटर्न एक फीचर है, सीमा नहीं। केवल शीर्ष तत्व के साथ इंटरैक्शन की अनुमति देकर, Python stack डिजाइन के स्तर पर सहीपन सुनिश्चित करता है। आप गलती से गलत सिरे से dequeue नहीं कर सकते या स्ट्रक्चर में गहराई में दबे किसी तत्व को ओवरराइट नहीं कर सकते। 

एल्गोरिथ्म डिजाइन में, ऐसी बाधाएँ ही आपकी तर्कशक्ति को साफ़ और कोड को पूर्वानुमेय रखती हैं।

Core Stack Operations और Time Complexity

अब जब हमें पता है कि Python stack क्या है और यह अन्य स्ट्रक्चर्स से कैसे अलग है, तो आइए उन मौलिक operations पर नज़र डालें जिन्हें हर stack सपोर्ट करता है और देखें कि वे कितनी कुशलता से चलती हैं।

मानक stack operations

हर stack implementation कुछ मानक operations के छोटे से सेट पर आधारित होती है, चाहे प्रोग्रामिंग भाषा कोई भी हो। हर बार जब आप stack के साथ काम करेंगे, तो इन्हीं building blocks का उपयोग करेंगे।

Push stack के शीर्ष पर एक तत्व जोड़ता है। अगर stack में [A, B] है और आप C push करते हैं, तो stack [A, B, C] बन जाता है, जहाँ C अब सबसे ऊपर है।

Pop वर्तमान में शीर्ष पर मौजूद तत्व को हटाता है और लौटाता है। ऊपर के उदाहरण को जारी रखते हुए, [A, B, C] से pop करने पर C लौटता है और stack [A, B] रह जाता है।

Peek (कभी-कभी top) आपको शीर्ष तत्व को हटाए बिना देखने देता है। यह तब उपयोगी है जब आपकी तर्कशक्ति को यह तय करने से पहले वर्तमान top मान को जाँचना हो कि pop करना है या नहीं—यह पैटर्न expression parsing और balanced parentheses समस्याओं में अक्सर आता है।

इन तीन core operations के अलावा, दो helper methods सुरक्षित और त्रुटि-मुक्त stack कोड लिखने के लिए महत्वपूर्ण हैं:

• is_empty() जाँचता है कि stack में कोई तत्व है या नहीं। खाली stack पर pop या peek कॉल करना runtime errors का एक सामान्य स्रोत है, इसलिए पहले emptiness जाँचना एक defensive programming आदत है जो आपको शुरू में ही बना लेनी चाहिए।

• size() stack में वर्तमान तत्वों की संख्या लौटाता है। यह तब मददगार है जब आपको यह ट्रैक करना हो कि recursion कितनी गहराई तक गया है या कितनी वस्तुएँ अभी प्रोसेस होनी बाकी हैं।

अंत में, एक शब्दावली परिभाषित करना उचित होगा जो आप पाठ्यपुस्तकों और इंटरव्यू में पाएँगे: Stack Underflow। यह वह error स्थिति है जब आप खाली stack से pop या peek करने का प्रयास करते हैं। हटाने या देखने के लिए कुछ नहीं होता, इसलिए operation अमान्य है। 

इससे उत्पन्न होने वाला सटीक exception या व्यवहार implementation पर निर्भर करता है। हम अगला सेक्शन देखते समय list, deque, और LifoQueue में Python इसे वास्तविक रूप में कैसे संभालता है, देखेंगे।

Complexity का विश्लेषण

एल्गोरिथ्म में stacks के व्यापक उपयोग का एक बड़ा कारण उनकी दक्षता है। आइए प्रत्येक operation की समय और स्थान जटिलता को तोड़कर समझें।

Push O(1) है। एक कुशल stack implementation में, शीर्ष पर एक तत्व जोड़ना constant-time operation होता है। stack को किसी मौजूदा तत्व को शिफ्ट या पुनर्व्यवस्थित करने की आवश्यकता नहीं होती। यह बस नया आइटम अंत में रख देता है। यह collections.deque और amortized मामले में Python की built-in list दोनों के लिए सही है।

Pop O(1) है। शीर्ष तत्व को हटाना भी उतना ही तेज़ है। stack सीधे अंतिम स्थिति तक पहुँचता है, मान लौटाता है, और अपने internal size tracker को घटाता है। फिर से, अन्य तत्वों को शिफ्ट करने की आवश्यकता नहीं होती।

Peek O(1) है। शीर्ष तत्व को हटाए बिना देखना एक सीधा index lookup है, इसलिए यह भी constant-time है।

Search O(n) है। यहीं पर stacks अपने जानबूझकर किए गए trade-off को उजागर करते हैं। यदि आपको पता लगाना है कि कोई विशिष्ट मान stack में कहीं मौजूद है या नहीं, तो आपके पास शीर्ष से नीचे तक सभी n तत्वों को स्कैन करने के अलावा कोई विकल्प नहीं है। 

Stacks मनमाने lookups के लिए डिज़ाइन नहीं किए गए हैं। वे तेज़, पूर्वानुमेय push और pop के बदले खोज क्षमता का त्याग करते हैं। यदि आपके उपयोग मामले में बार-बार खोज की आवश्यकता होती है, तो set या dictionary जैसा कोई अन्य डेटा स्ट्रक्चर बेहतर रहेगा।

Space complexity O(n) है। n तत्वों वाला stack, n के अनुपात में मेमोरी लेता है। तत्वों को स्टोर करने के लिए आवश्यक चीज़ों के अलावा कोई छुपा overhead नहीं होता, बस संरचना की internal bookkeeping के लिए एक छोटा constant होता है।

यह रहा एक त्वरित सारांश:

मुख्य निष्कर्ष यह है कि Python stack को एक सिरे पर तेज़ insertion और removal के लिए optimize किया गया है। जब तक आप इसे उसी काम के लिए उपयोग करते हैं जिसके लिए इसे बनाया गया है—यानी क्रमबद्ध, LIFO पहुँच प्रबंधन—यह उत्कृष्ट प्रदर्शन देता है। जैसे ही आप अपने आप को stack में नियमित रूप से खोज करते पाते हैं, यह संकेत है कि आपको डेटा स्ट्रक्चर के चुनाव पर फिर से विचार करना चाहिए।

Python Stack Implementations

अब जबकि सिद्धांत और complexity विश्लेषण पीछे रह गए हैं, समय है वास्तविक कोड लिखने का। Python stack लागू करने के तीन प्राथमिक तरीके देता है, प्रत्येक की अपनी ताकतें और trade-offs हैं। आइए तीनों से गुजरते हैं और देखें कि किस स्थिति में कौन सा विकल्प उपयुक्त है।

Built-in list के साथ Python stack

Python stack बनाने का सबसे सीधा तरीका built-in list है। क्योंकि lists dynamic arrays हैं जो अंत से तत्व जोड़ने और हटाने का समर्थन करती हैं, वे स्वाभाविक रूप से stack व्यवहार से मेल खाती हैं। 

.append() push के रूप में काम करता है, और argument के बिना .pop() अंतिम तत्व को हटाकर लौटाता है। आइए नीचे एक कोड उदाहरण देखें:

# Creating a stack using a Python list
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack)

# Pop the top element
top = stack.pop()
print(top)
print(stack)

# Peek at the top element
print(stack[-1])

[10, 20, 30]
30
[10, 20]
20

यह ठीक काम करता है, लेकिन आपको खाली stack के मामले को सावधानी से संभालना होगा। Python में, .pop() और stack[-1] दोनों list खाली होने पर IndexError उठाते हैं। यही तरह Python पहले परिभाषित Stack Underflow स्थिति को दर्शाता है। 

सर्वोत्तम अभ्यास यह है कि इन कॉल्स को try/except ब्लॉक में लपेटें या शीर्ष तक पहुँचने से पहले emptiness जाँचें, जैसे निम्न उदाहरण में:

# Handling Stack Underflow with try/except
stack = []

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty stack")

try:
    top = stack[-1]
except IndexError:
    print("Stack Underflow: cannot peek at an empty stack")

# Alternatively, check before accessing
if stack:
    top = stack.pop()
else:
    print("Stack is empty")

Stack Underflow: cannot pop from an empty stack
Stack Underflow: cannot peek at an empty stack
Stack is empty

एक performance बारीकी समझना उचित है। Python lists dynamic arrays पर आधारित हैं। जब आप .append() कॉल करते हैं, तो ऑपरेशन सामान्यतः तात्कालिक O(1) होता है। हालाँकि, जब internal array pre-allocated space से बाहर हो जाता है, तो Python को नया, बड़ा मेमोरी ब्लॉक आवंटित करना पड़ता है और सभी मौजूदा तत्वों को उसमें कॉपी करना पड़ता है। 

यह कभी-कभार होने वाला reallocation .append() को सख्त O(1) के बजाय amortized O(1) बनाता है। व्यवहार में यह देरी दुर्लभ और क्षणिक होती है, लेकिन latency-sensitive या real-time अनुप्रयोगों में यह unpredictability मायने रख सकती है।

इस चेतावनी के बावजूद, list पर .append() और .pop() अधिकांश सरल stack कार्यों के लिए पसंदीदा तरीका हैं। बिना import के काम, परिचित सिंटैक्स, और व्यापक डेवलपर परिचय के कारण यह scripting, प्रोटोटाइपिंग, और इंटरव्यू समस्याओं के लिए अच्छा डिफ़ॉल्ट विकल्प है जहाँ सादगी मायने रखती है।

collections.deque के साथ Python stack

यदि आपको occasional reallocation lag के बिना लगातार O(1) प्रदर्शन चाहिए, तो collections.deque अनुशंसित अपग्रेड है। नाम का अर्थ "double-ended queue" है, लेकिन यह high-performance Python stack के रूप में बिल्कुल उपयुक्त है। हमारा पहले वाला उदाहरण deque सिंटैक्स के साथ इस तरह दिखता है:

from collections import deque

# Creating a stack using deque
stack = deque()

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) 

# Pop the top element
top = stack.pop()
print(top)
print(stack)
 
# Peek at the top element
print(stack[-1])

deque([10, 20, 30])
30
deque([10, 20])
20

ध्यान दें कि इंटरफ़ेस list-आधारित तरीके के समान ही है। .append(), .pop(), और [-1] एक ही तरह काम करते हैं। खाली पहुँच पर IndexError का व्यवहार भी अपरिवर्तित है, इसलिए आपके error-handling कोड में कोई बदलाव आवश्यक नहीं:

from collections import deque

stack = deque()

try:
    stack.pop()
except IndexError:
    print("Stack Underflow: cannot pop from an empty deque stack")

Stack Underflow: cannot pop from an empty deque stack

महत्वपूर्ण अंतर अंदरूनी स्तर पर है। deque एक एकल array के बजाय fixed-size blocks की doubly-linked सूची के रूप में implement किया गया है। इसका मतलब है कि बढ़ते समय इसे कभी पूरे स्ट्रक्चर को reallocate और copy करने की ज़रूरत नहीं पड़ती। 

हर .append() और .pop() सच्चा, सुनिश्चित O(1) ऑपरेशन है—amortized नहीं, बल्कि सुसंगत। algorithm-heavy कार्यों में जहाँ आप हज़ारों या लाखों बार push और pop करते हैं, यह consistency मायने रखती है।

queue.LifoQueue के साथ Python stack

Python की standard लाइब्रेरी में queue.LifoQueue भी शामिल है, जो विशेष रूप से multi-threaded प्रोग्रामों के लिए बनाया गया stack implementation है। नाम में "LIFO" यह पुष्टि करता है कि यह Last-In-First-Out क्रम का पालन करता है, लेकिन इंटरफ़ेस और व्यवहार पिछले दो तरीकों से काफी अलग हैं। आइए इसे कोड उदाहरण से देखें:

from queue import LifoQueue

# Creating a thread-safe stack
stack = LifoQueue()

# Push elements using .put()
stack.put(10)
stack.put(20)
stack.put(30)
print(stack.qsize())

# Pop the top element using .get()
top = stack.get()
print(top)
print(stack.qsize())

3
30
2

पहली चीज़ जो नोट करने योग्य है वह सिंटैक्स परिवर्तन है। Push .put() हो जाता है, और pop .get()। यह नामकरण queue मॉड्यूल के producer-consumer डिजाइन पैटर्न से आता है, जहाँ एक thread आइटम "put" करता है और दूसरा "get" करता है।

ध्यान रखने के लिए दो महत्वपूर्ण व्यवहारगत अंतर हैं। 

पहला, LifoQueue में कोई सुरक्षित peek method नहीं है। शीर्ष तत्व को हटाए बिना देखने का कोई built-in तरीका नहीं है। आप internal attributes तक पहुँच सकते हैं, लेकिन multi-threaded संदर्भ में ऐसा करना thread-safe class का उद्देश्य विफल करता है और race conditions का जोखिम लाता है।

दूसरा, LifoQueue तब IndexError नहीं उठाता जब आप खाली stack से get करने का प्रयास करते हैं। डिफ़ॉल्ट रूप से, .get() ब्लॉक करता है। यह कॉल करने वाले thread को रोक देता है और अनिश्चितकाल तक प्रतीक्षा करता है जब तक कि कोई दूसरा thread stack पर कोई आइटम put न कर दे। यदि आप non-blocking व्यवहार चाहते हैं, तो आप block=False पास कर सकते हैं, जो इसके बजाय queue.Empty exception उठाता है। आइए इसे एक उदाहरण से देखें:

from queue import LifoQueue, Empty

stack = LifoQueue()

# Non-blocking get raises Empty, not IndexError
try:
    stack.get(block=False)
except Empty:
    print("Stack is empty — no items to get")

Stack is empty — no items to get

क्योंकि LifoQueue को thread-safe बनाने वाला internal locking मैकेनिज़्म मौजूद है, इसकी operations में list या deque की तुलना में अधिक overhead होता है। यह single-threaded कोड के लिए इसे खराब विकल्प बनाता है। LifoQueue का उपयोग केवल तब करें जब आपके पास concurrency के साथ एक स्वाभाविक multi-threaded परिदृश्य हो, और अन्य हर स्थिति में deque या list अपनाएँ।

Python में सही stack implementation चुनना

तीन विकल्प उपलब्ध होने के साथ, यहाँ एक side-by-side तुलना है जो आपके निर्णय का मार्गदर्शन करेगी:

यह रहा मेरा निर्णय ढाँचा सर्वोत्तम implementation चुनने के लिए:

• list का उपयोग तब करें जब आपको बिना import के एक त्वरित stack चाहिए—जैसे स्क्रिप्ट्स, नोटबुक्स, और इंटरव्यू व्हाइटबोर्ड्स में। 

• collections.deque का उपयोग तब करें जब आप algorithmic कोड लिख रहे हों, बड़े datasets प्रोसेस कर रहे हों, या ऐसा कुछ बना रहे हों जहाँ प्रदर्शन मायने रखता हो। 

• queue.LifoQueue का उपयोग केवल तब करें जब आपके पास concurrent एक्सेस के साथ स्वाभाविक multi-threaded परिदृश्य हो।

आप ऐसे ट्यूटोरियल्स से भी रूबरू हो सकते हैं जो कस्टम linked list class का उपयोग करके शून्य से Python stack बनाते हैं, जहाँ प्रत्येक node एक मान और उसके नीचे वाले node के लिए एक pointer रखता है। मेरे विचार में, यह निश्चित रूप से एक मूल्यवान शैक्षिक अभ्यास है जो यह समझ गहरा कर सकता है कि stacks अंदरूनी रूप से कैसे काम करते हैं और मेमोरी रेफरेंसेज़ कैसे जुड़ते हैं। 

हालाँकि, production Python कोड में, linked list stack लगभग हमेशा deque से धीमा होता है क्योंकि व्यक्तिगत node objects बनाने का overhead होता है। वास्तविक दुनिया के Python काम के लिए, collections.deque गति, स्पष्टता और विश्वसनीयता का सर्वोत्तम संयोजन देता है।

Python Stack के उपयोग

Python stack को लागू करना समझना तस्वीर का केवल आधा हिस्सा है। Stacks का वास्तविक मूल्य तब स्पष्ट होता है जब आप देखते हैं कि वे उन समस्याओं को हल करते हैं जो LIFO क्रम के बिना कहीं अधिक जटिल होतीं। आइए तीन क्लासिक अनुप्रयोगों पर नज़र डालें जो कोडिंग इंटरव्यू, सॉफ़्टवेयर सिस्टम्स और एल्गोरिद्म डिजाइन में लगातार दिखाई देते हैं।

Balanced parentheses की जाँच

Balanced parentheses समस्या तकनीकी इंटरव्यू में सबसे अधिक पूछे जाने वाले stack प्रश्नों में से एक है। ब्रैकेट्स वाले किसी string, जैसे (), [], और {}, के लिए तय करना होता है कि क्या हर opening bracket का सही क्रम में एक corresponding closing bracket है।

यह तर्क stack पर पूरी तरह मैप होता है। जैसे ही आप string को बाएँ से दाएँ स्कैन करते हैं, हर opening bracket को stack पर push करें। जब कोई closing bracket मिले, तो stack के शीर्ष से pop करें और जाँचें कि वह मेल खाता है या नहीं।

यदि pop करते समय stack खाली हो, या popped bracket मेल न खाए, तो string असंतुलित है। पूरी string प्रोसेस कर लेने के बाद stack खाली होना चाहिए। कोई भी बचा हुआ opening bracket दर्शाता है कि कुछ बंद नहीं हुआ। आइए इसे क्रिया में देखें:

from collections import deque

def is_balanced(expression):
    stack = deque()
    matching = {')': '(', ']': '[', '}': '{'}

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack:
                return False  # closing bracket with nothing to match
            if stack.pop() != matching[char]:
                return False  # mismatched pair
    
    return len(stack) == 0  # stack should be empty if balanced

# Test cases
print(is_balanced("([])")) 
print(is_balanced("{[()]}"))
print(is_balanced("([)]"))
print(is_balanced("(("))
print(is_balanced(""))

True
True
False
False
True

आइए "{[()]}" को step-by-step trace करें और stack को क्रिया करते देखें:

अंत में stack खाली है, इसलिए अभिव्यक्ति balanced है।

यही तर्क इंटरव्यू समस्याओं से बहुत आगे तक फैला हुआ है। Compilers और interpreters इसी से syntax मान्य करते हैं, यह सुनिश्चित करते हुए कि सोर्स कोड में हर opening tag, bracket, या delimiter का एक उपयुक्त मेल हो। 

यदि आपने कभी Python में SyntaxError: unexpected EOF संदेश देखा है, तो आपने इस जाँच का एक रूप क्रिया में देखा है। HTML validators, JSON parsers, और यहाँ तक कि configuration file linters भी इसी stack-आधारित दृष्टिकोण के विभिन्न रूपों पर निर्भर करते हैं।

Depth-first search (DFS) लागू करना

Depth-first search ग्राफ़ traversal एल्गोरिद्म की बुनियादी तकनीकों में से एक है, और stack वह डेटा स्ट्रक्चर है जो इसे संचालित करता है। विचार सरल है: किसी node से शुरू करें, एक शाखा के साथ जितना संभव हो उतना गहराई तक जाएँ, फिर अगली कोशिश करने के लिए backtrack करें। Python stack की LIFO प्रकृति स्वाभाविक रूप से इस "पहले गहराई में जाओ" व्यवहार को संभव बनाती है।

अधिकांश प्रारंभिक पाठ्यक्रम DFS को recursion से सिखाते हैं, जहाँ call stack traversal क्रम को अप्रत्यक्ष रूप से प्रबंधित करता है। हालाँकि, recursive दृष्टिकोण की एक व्यावहारिक सीमा है: Python की डिफ़ॉल्ट recursion सीमा 1,000 फ्रेम है। 

बड़े या गहराई से nested ग्राफ़ के लिए, इससे RecursionError हो जाती है। explicit stack वाला iterative संस्करण इस समस्या से बचता है और आपको traversal पर पूर्ण नियंत्रण देता है।

आइए इसका एक कोड उदाहरण देखें। हम निम्न ग्राफ़ पर DFS करेंगे:

from collections import deque

def dfs_iterative(graph, start):
    visited = set()
    stack = deque()
    stack.append(start)
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            # Push neighbors onto the stack
            # Reverse to maintain left-to-right order after LIFO popping
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return traversal_order

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print(dfs_iterative(graph, 'A'))

['A', 'B', 'D', 'E', 'F', 'C']

आइए execution को trace करें और देखें कि stack traversal को कैसे नियंत्रित करता है:

ध्यान दें कि LIFO क्रम एल्गोरिथ्म को A → B → D और A → B → E → F शाखाओं का पूरा अन्वेषण करने के लिए बाध्य करता है, इससे पहले कि वह कभी C पर जाने के लिए backtrack करे। यही बात depth-first search को breadth-first search से अलग करती है, जो queue का उपयोग करती है और वर्तमान गहराई पर सभी पड़ोसियों की खोज करने के बाद ही आगे गहराई में जाती है। 

यह iterative DFS पैटर्न trees, directed ग्राफ़ और undirected ग्राफ़ सभी पर काम करता है। यह topological sorting, cycle detection, और maze व puzzle समस्याएँ हल करने जैसे उन्नत एल्गोरिद्म की नींव भी है।

Undo/redo operations प्रबंधित करना

यदि आपने कभी text editor, drawing application, या spreadsheet का उपयोग किया है, तो आपने बिना यह सोचे कि नीचे क्या चल रहा है, undo और redo पर भरोसा किया है। यह तंत्र सुरुचिपूर्ण है, और बिल्कुल दो stacks पर चलता है।

एक undo stack, उपयोगकर्ता द्वारा किए गए हर action या state को सहेजता है। जब उपयोगकर्ता undo ट्रिगर करता है, तो वर्तमान state undo stack से pop होकर redo stack पर push हो जाती है।

यदि उपयोगकर्ता फिर redo ट्रिगर करता है, तो state redo stack से pop होकर वापस undo stack पर push हो जाती है। यदि उपयोगकर्ता undo करने के बाद कोई बिल्कुल नया परिवर्तन करता है, तो redo stack साफ़ हो जाता है। आप किसी ऐसी चीज़ को redo नहीं कर सकते जिसे नए action ने ओवरराइट कर दिया हो। आइए इसे कोड उदाहरण से देखें:

from collections import deque

class TextEditor:
    def __init__(self):
        self.content = ""
        self.undo_stack = deque()
        self.redo_stack = deque()

    def type_text(self, text):
        """Record current state and apply new text."""
        self.undo_stack.append(self.content)
        self.content += text
        self.redo_stack.clear()  # new action invalidates redo history

    def undo(self):
        """Revert to the previous state."""
        if not self.undo_stack:
            print("Nothing to undo")
            return
        self.redo_stack.append(self.content)
        self.content = self.undo_stack.pop()

    def redo(self):
        """Re-apply the last undone action."""
        if not self.redo_stack:
            print("Nothing to redo")
            return
        self.undo_stack.append(self.content)
        self.content = self.redo_stack.pop()

    def show(self):
        print(f'Content: "{self.content}"')

# Demonstrate the undo/redo flow
editor = TextEditor()
editor.type_text("Hello")
editor.show()                

editor.type_text(" World")
editor.show()                

editor.type_text("!")
editor.show()              

editor.undo()
editor.show()           

editor.undo()
editor.show()           

editor.redo()
editor.show()

editor.type_text(" Python")
editor.show()         

editor.redo()  

Content: "Hello"
Content: "Hello World"
Content: "Hello World!"
Content: "Hello World"
Content: "Hello"
Content: "Hello World"
Content: "Hello World Python"
Nothing to redo

दोनों stacks के बीच states का प्रवाह एक स्पष्ट पैटर्न का पालन करता है:

यह दो-stack पैटर्न केवल text editors तक सीमित नहीं है। यह जहाँ भी उपयोगकर्ताओं को परिवर्तनों की श्रृंखला में पीछे और आगे जाने की क्षमता चाहिए (जो लगभग हर जगह है) वहाँ दिखाई देता है:

• Image editing सॉफ़्टवेयर
• Database transaction rollbacks
• Game state management

मूल सिद्धांत हमेशा एक जैसा है। एक Python stack इतिहास ट्रैक करता है, दूसरा भविष्य, और LIFO क्रम यह सुनिश्चित करता है कि आप हमेशा सबसे हाल की state पर पहले लौटें।

Python Stack के उन्नत सिद्धांत

Stacks हर Python प्रोग्राम के सतह के नीचे भी महत्वपूर्ण भूमिका निभाते हैं, और वे ऐसी optimization तकनीकों को शक्ति देते हैं जो कुछ समस्याओं की time complexity को नाटकीय रूप से कम कर सकती हैं। आइए इन दोनों उन्नत आयामों पर नज़र डालें।

Call stack को समझना

जब भी आप Python में कोई फ़ंक्शन कॉल करते हैं, पर्दे के पीछे कुछ होता है जिस पर आपका प्रत्यक्ष नियंत्रण नहीं होता। Python एक internal डेटा स्ट्रक्चर, जिसे call stack कहा जाता है, पर एक नया frame push करता है। यह frame फ़ंक्शन के local variables, parameters, और उस कोड लाइन का pointer रखता है जिसने कॉल शुरू की थी। 

जब फ़ंक्शन का निष्पादन पूरा होता है, तो उसका frame call stack से pop हो जाता है, और नियंत्रण कॉलर के पास लौटता है।

आप वास्तव में एक सरल उदाहरण से इस व्यवहार को देख सकते हैं:

def function_c():
    print("Inside function_c")
    # At this point, the call stack holds:
    # [main → function_a → function_b → function_c]  (top)

def function_b():
    print("Inside function_b")
    function_c()

def function_a():
    print("Inside function_a")
    function_b()

function_a()

Inside function_a
Inside function_b
Inside function_c

जब function_c चल रहा होता है, तो call stack पर चार frames एक-दूसरे के ऊपर रखे होते हैं। जैसे-जैसे प्रत्येक फ़ंक्शन पूरा होता है, उसका frame LIFO क्रम में pop होता है। सबसे पहले function_c समाप्त होता है, फिर function_b, फिर function_a, और अंत में main module scope।

यही तंत्र recursion को संभव बनाता है। प्रत्येक recursive कॉल अपना अलग local variables वाला नया frame push करती है, और जैसे-जैसे frames pop होते हैं, परिणाम खुलते हैं। आइए एक उदाहरण देखें:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

# Call stack at deepest point:
# factorial(1)  ← top (returns 1)
# factorial(2)  ← waiting for factorial(1)
# factorial(3)  ← waiting for factorial(2)
# factorial(4)  ← waiting for factorial(3)
# factorial(5)  ← waiting for factorial(4)

120

समस्या तब आती है जब recursion बहुत गहरी हो जाती है। Python call stack को संपूर्ण मेमोरी खा जाने से बचाने के लिए 1,000 frames की डिफ़ॉल्ट recursion सीमा तय करता है। यदि आपका recursive फ़ंक्शन इस सीमा को पार कर जाता है, तो Python RecursionError उठाता है। आइए एक उदाहरण देखें:

def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

RecursionError: maximum recursion depth exceeded

आप sys मॉड्यूल का उपयोग करके इस सीमा की जाँच और संशोधन कर सकते हैं, हालाँकि इसे बढ़ाते समय सावधानी बरतनी चाहिए:

import sys

print(sys.getrecursionlimit())  
sys.setrecursionlimit(5000)     # Increase with caution

5000

महत्वपूर्ण अंतर यह ध्यान में रखना है कि call stack एक system-level स्ट्रक्चर है जिसे Python interpreter स्वयं प्रबंधित करता है। आप इसे सीधे push या pop नहीं कर सकते। पहले के सेक्शन्स में बनाए गए list, deque, और LifoQueue stacks user-defined डेटा स्ट्रक्चर हैं जो आपके प्रोग्राम की heap memory में रहते हैं। उनका उद्देश्य अलग है, लेकिन सभी एक ही LIFO सिद्धांत का पालन करते हैं।

Monotonic stacks का उपयोग

Monotonic stack एक विशेष प्रकार है जिसमें तत्वों को non-decreasing या non-increasing क्रम में बनाए रखा जाता है (या कभी-कभी सख्ती से increasing/decreasing, समस्या के अनुसार)। हर बार जब आप नया तत्व push करते हैं, तो आप पहले वे सभी तत्व pop करते हैं जो ordering constraint का उल्लंघन करेंगे। यह एक पूरे वर्ग की optimization समस्याओं को linear समय में हल करने की कुंजी है।

क्लासिक उदाहरण है Next Greater Element समस्या: किसी पूर्णांकों की array दी गई हो, तो प्रत्येक तत्व के लिए दाएँ तरफ पहला बड़ा तत्व खोजें। nested loops के साथ brute-force दृष्टिकोण O(n²) में चलता है—हर तत्व के लिए आप उसके दाएँ की हर चीज़ स्कैन करते हैं। Monotonic stack इसे O(n) में हल करता है।

सूझ-बूझ यह है कि आप array को दाएँ से बाएँ traverse करते हैं, और एक decreasing stack बनाए रखते हैं। प्रत्येक तत्व के लिए, आप stack से वे सब कुछ pop कर देते हैं जो उससे छोटा या उसके बराबर हो। वे मान अब किसी भी भविष्य के बाएँ तत्व के लिए "अगला बड़ा तत्व" कभी नहीं हो सकते। 

pop करने के बाद stack के शीर्ष पर जो भी रहता है, वह वर्तमान तत्व के लिए उत्तर है। फिर आप वर्तमान तत्व को stack पर push करते हैं। आइए कोड उदाहरण देखें। ध्यान दें कि इस मामले में -1 का अर्थ है कि उस संख्या के दाएँ कोई बड़ा तत्व नहीं है:

from collections import deque

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # default: no greater element found
    stack = deque()     # monotonic decreasing stack (stores values)

    # Traverse from right to left
    for i in range(n - 1, -1, -1):
        # Pop elements that are not greater than current
        while stack and stack[-1] <= nums[i]:
            stack.pop()
        
        # If stack is not empty, top is the next greater element
        if stack:
            result[i] = stack[-1]
        
        # Push current element onto the stack
        stack.append(nums[i])

    return result

nums = [4, 5, 2, 25, 7, 18]
print(next_greater_element(nums))

[5, 25, 25, -1, 18, -1]

आइए execution को trace करें और देखें कि monotonic गुण कैसे बनाए रखा जाता है:

ध्यान दें कि हर तत्व बिल्कुल एक बार stack पर push होता है और पूरे traversal में अधिकतम एक बार pop होता है। यही कारण है कि inner time complexity O(n) रहती है यद्यपि अंदर while लूप है। सभी iterations में push और pop operations की संचयी संख्या कभी 2n से अधिक नहीं होती।

जैसा कि मैंने पहले कहा, कई समान समस्याएँ हैं जिन्हें monotonic stack पैटर्न O(n²) से O(n) तक तेज़ करता है। उनमें से कुछ हैं:

• Stock span समस्या: प्रत्येक दिन के मूल्य के लिए, पता करें कि उससे पहले कितने लगातार दिन ऐसे थे जिनका मूल्य कम या बराबर था।
• Histogram में सबसे बड़ा rectangle: बार चार्ट के नीचे फिट होने वाला अधिकतम आयताकार क्षेत्र खोजें (एक क्लासिक कठिन इंटरव्यू समस्या)।
• Daily temperatures: दैनिक तापमानों की array दी हो, तो पता करें कि गर्म दिन के लिए आपको कितने दिनों तक प्रतीक्षा करनी होगी।
• Trapping rainwater: विभिन्न ऊँचाई वाली पट्टियों के बीच कितना वर्षाजल फँसता है, इसकी गणना करें।

हर मामले में, core विचार एक जैसा है: monotonic constraint आपको उन तत्वों को हटाने देता है जो अब भविष्य के परिणामों को प्रभावित नहीं कर सकते, जिससे खोज स्थान quadratic से linear तक सिकुड़ जाता है।

निष्कर्ष

Stack उन पहले डेटा स्ट्रक्चर्स में से है जिन्हें हर प्रोग्रामर सीखता है और उन अंतिम में से भी है जिनके नए उपयोग मिलना बंद नहीं होते—विडंबना यह है कि यह उसकी Last-In-First-Out प्रकृति के विपरीत है। 

इस लेख में, हमने देखा कि यह LIFO constraint कैसे विभिन्न परिदृश्यों में सहायक हो सकता है—nested brackets को मान्य करने और depth-first search traversals चलाने से लेकर undo/redo state प्रबंधन और monotonic stacks के साथ array समस्याओं को optimize करने तक। 

अगर एक सिफारिश साथ ले जानी हो, तो वह यह है: जब तक कोई विशिष्ट कारण न हो, collections.deque को अपने go-to Python stack implementation के रूप में अपनाएँ। 

अगले चरण के रूप में, मैं सुझाता हूँ कि आप हमारा कोर्स लें Data Structures and Algorithms in Python पर।