स्टैक (Stack) एक रैखिक डेटा संरचना है जिसमें डेटा का प्रवेश और निष्कासन एक ही सिरे से होता है, जिसे शीर्ष (Top) कहा जाता है। स्टैक LIFO (Last In, First Out) सिद्धांत पर कार्य करता है, अर्थात जो तत्व सबसे अंत में जोड़ा जाता है वही सबसे पहले निकाला जाता है। इसे समझने के लिए हम भोजन की प्लेटों के ढेर (stack of plates) का उदाहरण ले सकते हैं - सबसे ऊपर रखी प्लेट ही सबसे पहले उठाई जाती है। स्टैक का उपयोग कई क्षेत्रों में होता है, जैसे फंक्शन कॉल का प्रबंधन (recursion में), उल्टा पठन (reversing), ब्रैकेट संतुलन की जाँच, एडिटर में undo/redo ऑपरेशन आदि।
स्टैक में सभी मुख्य ऑपरेशन स्थिरांक समय (O(1)) में संपन्न होते हैं, क्योंकि हम केवल शीर्ष तत्व के साथ कार्य करते हैं। इस अध्याय में हम स्टैक की अवधारणा, उसके मुख्य ऑपरेशन, सूची का उपयोग करके स्टैक का कार्यान्वयन, और उसके अनुप्रयोगों को विस्तार से समझेंगे।
स्टैक को समझने के लिए कुछ मुख्य शब्दों को जानना आवश्यक है:
Push ऑपरेशन स्टैक के शीर्ष पर एक नया तत्व जोड़ता है। इससे पहले स्टैक भरा हुआ तो नहीं है, यह जाँचना आवश्यक है।
def push(stack, element):
stack.append(element)
print(element, "स्टैक में जुड़ा")
यहाँ हमने सूची की append() विधि का उपयोग किया है, जो तत्व को सूची के अंत में जोड़ती है, जो स्टैक का शीर्ष है।
Pop ऑपरेशन स्टैक के शीर्ष तत्व को निकालता है और उसे लौटाता है। यदि स्टैक खाली है तो यह underflow की स्थिति उत्पन्न करता है।
def pop(stack):
if is_empty(stack):
print("स्टैक खाली है (Underflow)")
return None
return stack.pop()
Peek ऑपरेशन शीर्ष तत्व को हटाए बिना उसकी जानकारी देता है:
def peek(stack):
if is_empty(stack):
print("स्टैक खाली है")
return None
return stack[-1]
def is_empty(stack):
return len(stack) == 0
def size(stack):
return len(stack)
def display(stack):
print("स्टैक (शीर्ष से नीचे):", stack[::-1])
पाइथन में स्टैक को सूची (list) की सहायता से सरलता से कार्यान्वित किया जा सकता है। सूची के अंत में जोड़ने के लिए append() और अंत से निकालने के लिए pop() का उपयोग किया जाता है। पूर्ण कार्यान्वयन निम्नलिखित है:
stack = []
def push(stack, element):
stack.append(element)
print(element, "पुश किया गया")
def pop(stack):
if not stack:
print("स्टैक खाली है - Underflow")
return None
return stack.pop()
def display(stack):
if not stack:
print("स्टैक खाली है")
else:
print("स्टैक के तत्व (नीचे से ऊपर):", stack)
push(stack, 10)
push(stack, 20)
push(stack, 30)
print(pop(stack)) # 30
print(pop(stack)) # 20
display(stack) # [10]
def is_balanced(expr):
stack = []
for ch in expr:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack:
return False
top = stack.pop()
if not matching(top, ch):
return False
return len(stack) == 0
स्टैक का उपयोग कंप्यूटर विज्ञान में अनेक स्थानों पर किया जाता है:
स्टैक की सहायता से पोस्टफिक्स अभिव्यक्ति का मूल्यांकन निम्नलिखित नियमों से किया जाता है:
उदाहरण: पोस्टफिक्स अभिव्यक्ति 23+5* का मूल्यांकन करें।
पढ़ें 2 → पुश(2), पढ़ें 3 → पुश(3)
पढ़ें + → 3+2=5, पुश(5)
पढ़ें 5 → पुश(5)
पढ़ें * → 5*5=25
उत्तर = 25
def eval_postfix(expr):
stack = []
for token in expr.split():
if token.isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(a / b)
return stack.pop()
| ऑपरेशन | कार्य | समय जटिलता |
|---|---|---|
| Push | तत्व जोड़ना | O(1) |
| Pop | तत्व निकालना | O(1) |
| Peek/Top | शीर्ष तत्व देखना | O(1) |
| isEmpty | स्टैक खाली है या नहीं | O(1) |
| Size | तत्वों की संख्या | O(1) |
| विशेषता | स्टैक | क्यू |
|---|---|---|
| सिद्धांत | LIFO | FIFO |
| सम्मिलन सिरा | शीर्ष | पीछे (Rear) |
| विलोपन सिरा | शीर्ष | सामने (Front) |
| उदाहरण | प्लेटों का ढेर | टिकट काउंटर की कतार |
b होता है और दूसरा a, अतः a - b (घटाव) में क्रम महत्वपूर्ण है। गलत क्रम से उत्तर ऋणात्मक हो सकता है।append), शुरुआत में नहीं (insert(0,...)), अन्यथा LIFO का क्रम टूट जाता है।stack.append(x) push के लिए और stack.pop() pop के लिए है - इस जोड़े को कभी न भूलें।स्टैक डेटा संरचनाओं की नींव में से एक है, जो LIFO सिद्धांत पर कार्य करती है। इसका शीर्ष-केंद्रित प्रवेश-निष्कासन इसे रिकर्शन, अभिव्यक्ति मूल्यांकन, ब्रैकेट संतुलन और undo/redo जैसे अनुप्रयोगों में अत्यंत उपयोगी बनाता है। पाइथन में सूची की append() और pop() विधियों से स्टैक को सरलता से कार्यान्वित किया जा सकता है। परीक्षा में अच्छे अंक लाने के लिए push/pop के चरणबद्ध निष्पादन, पोस्टफिक्स मूल्यांकन और underflow/overflow स्थितियों का अभ्यास आवश्यक है। स्टैक की अवधारणाओं की गहरी समझ आगे की पढ़ाई में क्यू और ट्री जैसी संरचनाओं के लिए भी आधार तैयार करती है।