编程题目 定义栈的数据类型,请在类型中实现一个能够得到栈最小元素的minx函数。

首先自己用 节点 实现了 栈 这种数据类型

为了实现题目了要求,我使用的两个栈。

一个栈 用来 push pop 用户的数据, 另外一个栈用来存放 最小元素(涉及元素比较)

代码如下:

 #!/usr/bin/env python3

 class Node(object):
def __init__(self, elem, next_=None):
self.elem = elem
self.next = next_ class LStack(object):
def __init__(self):
self.top = None def is_empty(self):
return self.top is None def push(self, elem):
self.top = Node(elem, self.top) def pop(self):
if self.is_empty():
raise ValueError("Stack is Empty")
e = self.top.elem
self.top = self.top.next
return e def peek(self):
if self.is_empty():
raise ValueError("Stack is Empty")
return self.top.elem class Stack_Find_Min(object):
def __init__(self):
self.s1 = LStack()
self.s2 = LStack()
self.minvalue = 0 def is_empty(self):
return self.s1.is_empty() def push(self, elem):
self.s1.push(elem)
if self.s2.is_empty():
self.s2.push(elem)
self.minvalue = elem
elif elem < self.minvalue:
self.s2.push(elem)
self.minvalue = elem def pop(self):
if self.s1.is_empty():
raise ValueError("Stack is Empty")
e = self.s1.pop()
if e == self.minvalue:
self.s2.pop()
self.minvalue = self.s2.peek()
return e def peek(self):
return self.s1.peek() def minx(self):
return self.s2.peek() if __name__=="__main__":
sm = Stack_Find_Min()
for i in [3,2,7,9,4,6,8,1]:
sm.push(i)
print("minx:",sm.minx())
print("pop:",sm.pop())
print("minx:",sm.minx())
上一篇:Vi文本编辑


下一篇:实现栈最小元素的min函数