Python의 최소 스택

여기에서 우리는 푸시, 팝, 탑을 수행하고 최소 요소를 일정한 시간에 검색할 수 있는 스택을 만드는 방법을 볼 것입니다. 따라서 함수는 push(x), pop(), top() 및 getMin()이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 최소 요소로 스택을 무한대로 초기화
• 푸시 작업용 push(x)
  • 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