设计包含min函数的栈

2019-11-14 17:44:44

字体：大中小

来源：转载

供稿：网友

设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。

栈中元素设两个域，一个记录元素的值，一个记录栈的最小值。

class Stack(object):    def __init__(self):        self.list=[]        self.top=-1    def push(self,x):        if self.top>=0:            if x<self.list[-1][1]:                self.list.append((x,x))            else:                self.list.append((x,self.list[-1][1]))        else:            self.list.append((x,x))        self.top+=1    def pop(self):        if self.top>=0:            self.top-=1            return self.list.pop()[0]        else:            raise IndexError,'pop from empty stack'    def min(self):        if self.top>=0:            return self.list[self.top][1]        else:            raise IndexError,'stack is empty'

上一篇：初次撸Python，踩平些小坑～

下一篇：B树及2-3树的python实现