स्टैक
स्टैक एल्गोरिदम में उपयोग होने वाले सबसे लोकप्रिय डाटा स्ट्रक्चर्स में से एक है। जब आप स्टैक का इस्तेमाल करते हैं, तो जो तत्व आख़िर में जोड़े जाते हैं, वही सबसे पहले निकाले जाते हैं। यह बिल्कुल वैसे ही है जैसे प्लेटों का ढेर—सबसे ऊपर रखी प्लेट को तभी हटाया जा सकता है जब उसके ऊपर रखी सभी प्लेटें हटा दी गई हों।
स्टैक कई वास्तविक-जीवन की परिस्थितियों में काम आ सकता है। उदाहरण के लिए, किसी वेब ब्राउज़र में वेबसाइटें खोलते समय, bạn पिछली पेज पर जाने के लिए ‘बैक’ बटन दबा सकते हैं। उस वेब पेज का इतिहास एक स्टैक में रखा जा सकता है, और जब आप बैक बटन दबाते हैं, तो आप स्टैक के शीर्ष पर मौजूद पेज पर पहुँच जाते हैं। यदि आप दोबारा बैक बटन दबाते हैं, तो शीर्ष पेज हटा दिया जाता है और आप उसके ठीक नीचे वाले पेज पर जाते हैं।
पायथन जैसी प्रोग्रामिंग भाषा में स्टैक को लागू करने के कई तरीके हैं:
listका उपयोग करके – यहाँ स्टैक का शीर्ष एलिमेंट सूची (list) के अंतिम एलिमेंट की तरह व्यवहार करता है। आपappendसे नया तत्व जोड़ सकते हैं,popके ज़रिए हटा सकते हैं, और[-1]से शीर्ष एलिमेंट देख सकते हैं।
collectionsसेdequeका उपयोग करके – यह शुरुआत और अंत, दोनों ओर से तत्वों को जोड़ने और हटाने की सुविधा देता है।
queueसेLifoQueue– यह लास्ट-इन-फर्स्ट-आउट (LIFO) Queue है, जो स्टैक डाटा स्ट्रक्चर की मूल परिभाषा से मेल खाती है।
from queue import LifoQueue
stack = LifoQueue()
# एलिमेंट स्टैक में डालें (push)
stack.put(1)
stack.put(2)
stack.put(3)
# एलिमेंट स्टैक से निकालें (pop)
print(stack.get()) # 3 को प्रिंट करता है
print(stack.get()) # 2 को प्रिंट करता है
# शीर्ष एलिमेंट देखें (peek)
print(stack.queue[-1]) # 1 को प्रिंट करता है
print(stack.empty()) # जाँच करता है कि खाली है या नहीं -> False को प्रिंट करता है# एक साधारण list का उपयोग
stack = []
# एलिमेंट डालें (push)
stack.append(1)
stack.append(2)
stack.append(3)
# एलिमेंट हटाएँ (pop)
print(stack.pop()) # 3 को प्रिंट करता है
print(stack.pop()) # 2 को प्रिंट करता है
# शीर्ष एलिमेंट देखें (peek)
print(stack[-1]) # 1 को प्रिंट करता है
print(len(stack) == 0) # जाँचें कि खाली है या नहीं -> False को प्रिंट करेगाचुनौती: कोष्ठकों की सत्यता जाँचें
आपको एक गणितीय अभिव्यक्ति के कोष्ठक अनुक्रम (उदाहरण:
(()())) दिया गया है, और यह जाँचना है कि वह अनुक्रम वैध है या नहीं। एक कोष्ठक अनुक्रम वैध तब माना जाता है, जब हर खुलने वाले कोष्ठक का ठीक-ठीक बंद होने वाला कोष्ठक हो और ऐसा कोई कोष्ठक न हो जो अतिरिक्त रूप से खुला या बंद हो।इनपुट
इनपुट की एकमात्र पंक्ति में
b (1 ≤ |b| ≤ ) दिया गया है, जिसमें कोष्ठक अनुक्रम शामिल है।आउटपुट
यदि कोष्ठक अनुक्रम वैध है, तो प्रोग्राम
Yes प्रिंट करेगा, अन्यथा No।उदाहरण
इनपुट | आउटपुट |
()() | Yes |
())()( | No |
((()())()) | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB