Ngăn xếp tối thiểu bằng Python

Ở đây chúng ta sẽ thấy cách tạo một ngăn xếp, có thể thực hiện đẩy, bật, lên trên và truy xuất phần tử min trong thời gian không đổi. Vì vậy, các hàm sẽ là push (x), pop (), top () và getMin ()

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Khởi tạo ngăn xếp theo phần tử min là vô cùng
• Đối với thao tác đẩy, push (x)
  • nếu x
  • đẩy x vào ngăn xếp
• Đối với hoạt động pop ()
  • t:=phần tử hàng đầu
  • xóa t khỏi ngăn xếp
  • nếu t là min, thì min:=phần tử trên cùng của ngăn xếp
• Đối với hoạt động hàng đầu, top ()
  • chỉ cần trả lại phần tử trên cùng
• cho hoạt động getMin getMin ()
  • trả về phần tử min

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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())

Đầu vào

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

Đầu ra

-3
0
-2