python实现包含min函数的栈

本文实例讲述了python实现包含min函数的栈。分享给大家供大家参考,具体如下:

# coding=utf8
”’
题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。
在该栈中,调用min、push及pop的时间复杂度都是o(1)。
”’
class stack():
def __init__(self):
self.main_stack = []
# 辅助栈,每次次最小的元素压入辅助栈
self.assist_stack = []
# 记录栈中的最小元素
self._min = none
def min(self):
return self._min
def push(self, data):
self.main_stack.append(data)
if self._min is none:
self._min = data
else:
if data < self._min: self._min = data # 将最小的元素压入辅助栈 self.assist_stack.append(self._min) def pop(self): if len(self.main_stack) == 0: raise exception('no data') elif len(self.main_stack) == 1: self.assist_stack.pop() self._min = none return self.main_stack.pop() else: self.assist_stack.pop() self._min = self.assist_stack[-1] return self.main_stack.pop() if __name__ == '__main__': s = stack() s.push(3) s.push(4) s.push(2) s.push(1) print s.min() s.pop() s.pop() print s.min() s.pop() print s.min() s.pop() print s.min() s.pop()

更多关于python相关内容可查看本站专题:《python正则表达式用法总结》、《python数据结构与算法教程》、《python socket编程技巧总结》、《python函数使用技巧总结》、《python字符串操作技巧汇总》、《python入门与进阶经典教程》及《python文件与目录操作技巧汇总》

希望本文所述对大家python程序设计有所帮助。

Posted in 未分类