設(shè)計一個棧，該棧可以進(jìn)行push、pop、top和在常數(shù)時間內(nèi)檢索最小值的操作

• push(x) – 壓一個數(shù)到棧頂
• pop() – 移除棧頂?shù)脑?#xff0c;不返回任何對象
• top() – 返回棧頂端的元素
• getMin() – 檢索棧中的最小值

方法1：引入minStack列表存放最小值，原生態(tài)的min()函數(shù)比較花費時間。

class MinStack(object):def __init__(self):self.stack = [] # 存放所有元素self.minStack = [] # 存放每一次壓入數(shù)據(jù)時，棧中的最小值# （如果壓入數(shù)據(jù)的值大于棧中的最小值就不需要重復(fù)壓入最小值，# 小于或者等于棧中最小值則需要壓入）def push(self, x):self.stack.append(x)if not self.minStack or self.minStack[-1] >= x:self.minStack.append(x)def pop(self): # 移除棧頂元素時，判斷是否移除棧中最小值if self.minStack[-1] == self.stack[-1]:del self.minStack[-1]self.stack.pop()def top(self): #獲取棧頂元素return self.stack[-1]def getMin(self): #獲取棧中的最小值return self.minStack[-1]def all(self): #列表棧中所有的元素return self.stack[:]stack = MinStack() stack.push(-2) stack.push(0) stack.push(-3) stack.push(5) stack.push(-4) print('棧中所有元素：',stack.all()) print('最小元素：',stack.getMin()) stack.pop() print('棧頂元素：',stack.top()) print('最小元素：',stack.getMin())

運行結(jié)果：

棧中所有元素： [-2, 0, -3, 5, -4]
最小元素： -4
棧頂元素： 5
最小元素： -3

方法2：用列表模擬棧，push、pop、top和getMin分別對應(yīng)list.append()、list.pop()、list[-1]和min()操作

class MinStack(object):def __init__(self):self.stack = []def push(self, x):self.stack.append(x)def pop(self):if self.stack :self.stack.pop()def top(self):if self.stack:return self.stack[-1]def getMin(self):if self.stack:return min(self.stack)stack = MinStack() stack.push(-2) stack.push(0) stack.push(-3) stack.push(5) stack.push(-4) print(stack.getMin()) stack.pop() print(stack.top()) print(stack.getMin())

運行結(jié)果：

-4
5
-3

參考博客：https://blog.csdn.net/qiubingcsdn/article/details/82561331

總結(jié)

以上是生活随笔為你收集整理的python实现栈，实现push(),pop(),top(),getMin()方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。