Python实现包含min函数的栈

yipeiwu_com6年前Python基础

本文实例讲述了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程序设计有所帮助。

相关文章

python实现tail -f 功能

tailf与tail -f类似:当文件不增长时并不访问文件 tail -f:只跟踪文件内容 tail -F:文件内容与文件名都跟踪 这篇文章最初是因为reboot的群里,有人去面试,笔试...

Django的数据模型访问多对多键值的方法

这里先来借用一个书本(book)的数据模型作为例子: from django.db import models class Publisher(models.Model): n...

python里对list中的整数求平均并排序

问题 定义一个int型的一维数组,包含40个元素,用来存储每个学员的成绩,循环产生40个0~100之间的随机整数, (1)将它们存储到一维数组中,然后统计成绩低于平均分的学员的人数,并输...

Python lambda表达式filter、map、reduce函数用法解析

前言 lambda是表达式,用于创建匿名函数,可以和filter、map、reduce配合使用。 本文环境Python3.7。 一、lambda表达式 lambda 只包含一个语句,用...

Python利用heapq实现一个优先级队列的方法

Python利用heapq实现一个优先级队列的方法

实现一个优先级队列,每次pop的元素要是优先级高的元素,由于heapq.heapify(list)默认构建一个小顶堆,因此要将priority变为相反数再push,代码如下: imp...