पायथन में मिन स्टैक

यहां हम देखेंगे कि कैसे एक स्टैक बनाया जाए जो पुश, पॉप, टॉप, और न्यूनतम तत्व को स्थिर समय में प्राप्त कर सके। फंक्शन होंगे push(x), pop(), top() और getMin()।

हल करने के चरण

• स्टैक को अनंत के रूप में न्यूनतम तत्व से आरंभ करें
• पुश ऑपरेशन push(x) के लिए
  • यदि x < min, तो min := x अपडेट करें,
  • x को स्टैक में पुश करें
• पॉप ऑपरेशन pop() के लिए
  • t := शीर्ष तत्व
  • t को स्टैक से हटाएं
  • यदि t min है, तो min := स्टैक का शीर्ष तत्व
• टॉप ऑपरेशन top() के लिए
  • बस शीर्ष तत्व वापस करें
• getMin ऑपरेशन getMin() के लिए
  • न्यूनतम तत्व वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

class MinStack(object):
    min=float('inf')
    def __init__(self):
        self.min=float('inf')
        self.stack = []
    def push(self, x):
        if x<=self.min:
            self.stack.append(self.min)
            self.min = x
        self.stack.append(x)
    def pop(self):
        t = self.stack[-1]
        self.stack.pop()
        if self.min == t:
            self.min = self.stack[-1]
            self.stack.pop()
    def top(self):
        return self.stack[-1]
    def getMin(self):
        return self.min

m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())

इनपुट

m = MinStack() m.push(-2) m.push(0) m.push(-3) print(m.getMin()) m.pop() print(m.top()) print(m.getMin())

आउटपुट

-3 0 -2