写一个栈,实现出栈、入栈、求最小值,时间复杂度为O(1)

时间:2022-03-29 16:18:31
#-*-coding:utf-8-*-
'''
需求:写一个栈,实现出栈、入栈、求最小值,时间复杂度为O(1)
思路:通过两个栈实现,一个栈stack,一个辅助栈min_stack,记录stack中的最小值
栈stack,元素正常push和pop操作
栈min_stack:
入栈(push):
第一次push,元素正常放入栈中;
之后每一次push的元素data(即栈顶元素 min_stack[top])都和栈顶元素的前一个元素(即 min_stack[top-1])进行比较
data < min_stack[top-1],则将data置为min_stack的栈顶
data >= min_stack[top-1],则将min_stack[top-1]置为min_stack的栈顶
出栈(pop):
辅助栈min_stack 在stack有pop的时候一并pop操作
如此,min_stack栈中的栈顶位置始终保存这stack栈中的最小值
''' class Stack(object):
def __init__(self, size=8):
self.size = size
self.stack = []
self.min_stack = []
self.top = -1 def set_size(self, size):
if self.top >= size:
raise Exception("StackWillOverFlow")
self.size = size def isFull(self):
return True if self.top == self.size - 1 else False def isNull(self):
return True if self.top == -1 else False def push(self, data):
if self.isFull():
raise Exception("Stack over flow")
return
self.top += 1
self.stack.append(data)
#将栈的第一个元素赋给min_stack
if self.top == 0:
self.min_stack.append(data)
#当stack push第二个元素后开始比较,使得 min_stack[top] 始终为当前栈中的最小元素
if self.top > 0:
if data < self.min_stack[self.top-1]:
self.min_stack.append(data)
else:
self.min_stack.append(self.min_stack[self.top-1]) def pop(self):
if self.isNull():
raise Exception("Stack is Empty")
return
self.top -= 1
#stack pop的时候min_stack一并pop
self.min_stack.pop()
return self.stack.pop() def get_top(self):
if self.isNull():
raise Exception("Stack is Empty")
return
return self.stack[self.top] def show(self):
print self.stack # min_stack栈的栈顶元素记录着当前栈的最小值
def get_min(self):
if self.isNull():
raise Exception("Stack is Empty")
return
return self.min_stack[self.top] #test
def Test():
a = Stack(10)
a.push(11)
a.push(12)
a.push(13)
a.push(10)
a.push(9)
a.push(8)
a.push(15)
a.push(16) a.show()
print a.get_min() a.pop()
a.show()
print a.get_min() a.pop()
a.show()
print a.get_min() a.pop()
a.show()
print a.get_min() a.pop()
a.show()
print a.get_min() a.push(20)
a.show()
print a.get_min() a.push(1)
a.show()
print a.get_min() if __name__ == '__main__':
Test()