python栈实现和案例
栈是一种常用的数据结构，我们常说栈是先进后出的特点，正式这个特点，我们可以利用其记录很多状态，并返回到原来的状态。 本文以python实现， 然后在举例说明一些简单的应用。
栈的结构
常用方法
- Stack()创建一个空栈
- push() 把一个元素添加到栈顶
- pop() 删除栈最顶层的元素，并返回这个元素
- peek() 返回最顶层的元素，并不删除它
- isEmpty() 判断栈是否为空
- size() 返回栈中元素的个数
代码
class Stack:
"""栈的模拟实现"""
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
栈的几个实例
实现一个栈，带有出栈（pop），入栈（push），取最小元素（getMin）三个方法。要保证这三个方法的时间复杂度都是O(1)
利用栈进行括号匹配
问题1 的思路， 用一个最小值下标栈， 存储一直以来的最小值下标， 当不是最小值的数据出栈pass不理会; 如果是最小值， 最小值下标栈 也同时pop()最小值下标， 那么剩下的最小值下标栈 中栈顶 元素就是 相应的最小值下标。
#coding=utf-8
class NewStack:
"""储存最小值的栈"""
def __init__(self):
self.items = []
#存储下标
self.stack = Stack()
def isEmpty(self):
return len(self.items) == 0
def push(self, item):
#如果item 小于 原来最小的元素
if self.stack.size() == 0:
self.stack.push(0)
else:
if (item < self.items[self.stack.peek()]):
#存储小标 = （0， 1）2个元素 来第三个 3（-1）
self.stack.push(self.size())
else:
pass
self.items.append(item)
def pop(self):
#size = 4
# [10 12 9 14] [0, 2]
#出栈 如果出栈的元素小标是 下标栈中的栈顶元素 下标也出站
#如果不是不用管下标站
if (self.size() - 1) == self.stack.peek():
self.stack.pop()
else:
pass
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[len(self.items) - 1]
def getMin(self):
return self.items[self.stack.peek()]
def display(self):
print self.items
def size(self):
return len(self.items)
问题2括号匹配思路:
如果正括号出现就push入栈， 不是括号不管， 如果是反括号就出栈， 出栈的时候比较下标是否对应。最后如果正确匹配stack中size应该为0。pop异常(没有元素)也说明没有匹配。
def is_match(astring):
list1 = ["{", "(", "["];
list2 = ["}", ")", "]"];
is_right = True
try:
for x in astring:
if x in list1:
stack1.push(x)
elif x in list2:
top = stack1.pop()
if list1.index(top) != list2.index(x):
is_right = False
break
else:
pass
except:
is_right = False
if stack1.size() != 0:
is_right = False
return is_right
