栈 (Stack) 在计算机领域是一个被广泛应用的集合, 栈是线性集合, 访问都严格地限制在一段, 叫做顶(top). 举个例子, 栈就想一摞洗干净的盘子, 你每次取一个新盘子, 都是放在这一摞盘子的最上头, 当你往里面添加盘子的时候, 也是放在最上面, 处在底部的盘子, 你可能永远也用不到. 栈的最常见操作, 有如下两个:
- push(a) # 压入, 将 a 压入的栈中
- pop() # 弹出, 将栈的最后一个元素弹出
复制代码
可是使用 Python 的列表数据结构, 来模拟栈的操作, 使用 append 来模拟 push, 使用列表的 pop 来模拟栈的 pop, 但是这样做有一个弊端, 那就是列表原本自带的操作方法同样能够使用, 可能会造成混乱.
栈的实现 下面就通过借助 Python 的列表, 来自定义一个栈类:
- class Stack(object):
- """使用数组实现一个栈"""
- def __init__(self):
- self.data = []
- def push(self, num):
- """压栈操作"""
- self.data.append(num)
- def pop(self):
- """返回从栈中弹出的元素, 当栈为空的时候, 抛出 IndexError"""
- return self.data.pop()
- def peek(self):
- """查看当前栈顶的元素, 当栈为空的时候, 抛出 IndexError"""
- return self.data[-1]
- def __len__(self):
- """返回栈的长度, 调用 len(obj)时会自动调用 obj 对象的__len__方法"""
- return len(self.data)
- def isEmpty(self):
- """判断栈是否为空"""
- return True if len(self.data)==0 else False
- def clear(self):
- """清空栈"""
- self.data = []
- def __repr__(self):
- """当前对象的表现形式, 在终点直接键入对象时会调用"""
- return 'Stack_' + str(self.data)
- def __str__(self):
- """当前对象的字符串表示, 使用 print(obj)时会调用"""
- return 'Stack_' + str(self.data)
- 复制代码
- 以上代码实现了一个简单的基于列表的栈.
- 栈的应用 栈应用的一个很典型的例子, 就是检查括号是否匹配. 例如: 每一个开始的[后面, 都应该跟着一个位置正确的], 并且每一个(后面, 也应该跟着一个位置正确的结束的).
- (...)...(...)匹配
- (...)...(... 不匹配
- )...((...)不匹配 像第三个示例中, 虽然左右括号的数量是相等的, 但是也是不匹配的, 所以不能通过简单的检查数量来实现括号的检测. 一种非常有效的解决方式就是使用栈:
- 扫描整个字符串, 如果遇到一个开始的括号, 将它压入到栈中
- 如果遇到一个结束的括号, 检查栈顶的元素, 如果是结束的括号, 就将当前括号压入栈中, 如果是开始的括号, 检查与当前括号是否能配对, 不能配对则不匹配
- 如果遇到一个结束的括号, 并且当前栈为空的话, 那么也是不匹配的. 代码实现如下:
- def isBalance(text):
- """栈的应用, 检查括号是否平衡"""
- result_stack = Stack()
- for i in text:
- if i in ['{', '[', '(']:
- result_stack.push(i)
- elif i in ['}', ']', ')']:
- # 遇到结束括号的情况
- if result_stack.isEmpty():
- # 如果当前栈为空, 不匹配, 返回 False
- return False
- chFromStack = result_stack.pop()
- if not ((chFromStack == '{' and i == '}' )
- or (chFromStack == '[' and i == ']')
- or (chFromStack == '(' and i == ')')):
- # 如果不满足匹配条件, 则返回 False
- return False
- # 遍历结束后, 如果结果栈为空, 则代表括号匹配, 栈不为空, 括号不匹配
- return result_stack.isEmpty()
复制代码
来源: https://juejin.im/post/5b7c01c9e51d45388325208a