Python实现包含min函数的栈
本文实例讲述了Python实现包含min函数的栈。分享给大家供大家参考,具体如下:
#coding=utf8 ''' 题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。 在该栈中,调用min、push及pop的时间复杂度都是O(1)。 ''' classStack(): def__init__(self): self.main_stack=[] #辅助栈,每次次最小的元素压入辅助栈 self.assist_stack=[] #记录栈中的最小元素 self._min=None defmin(self): returnself._min defpush(self,data): self.main_stack.append(data) ifself._minisNone: self._min=data else: ifdata<self._min: self._min=data #将最小的元素压入辅助栈 self.assist_stack.append(self._min) defpop(self): iflen(self.main_stack)==0: raiseException('nodata') eliflen(self.main_stack)==1: self.assist_stack.pop() self._min=None returnself.main_stack.pop() else: self.assist_stack.pop() self._min=self.assist_stack[-1] returnself.main_stack.pop() if__name__=='__main__': s=Stack() s.push(3) s.push(4) s.push(2) s.push(1) prints.min() s.pop() s.pop() prints.min() s.pop() prints.min() s.pop() prints.min() s.pop()
更多关于Python相关内容可查看本站专题:《Python正则表达式用法总结》、《Python数据结构与算法教程》、《PythonSocket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。