Python 数据结构之栈的实现
文章目录
栈的概念
栈（stack）又名堆栈，栈是一种线性数据结构，用先进后出或者是后进先出的方式存储数据，栈中数据的插入删除操作都是在栈的顶端进行，这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈的特点
元素后进先出（Last in First Out，LIFO）
栈的操作
- push(item)：进栈（向栈顶添加元素）
- pop()：出栈（删除栈顶元素）
- top()：查看栈顶元素
- empty()：判断栈是否为空
Python 实现栈
栈并不是 Python 的内建类型，在必要的时候可以使用列表来模拟基于数组的栈。如果将列表的末尾看作是栈的顶，列表方法 append() 就是将元素压入到栈中（进栈），而列表方法 pop() 会删除并返回栈顶的元素（出栈），列表索引的方式 arr[-1] 可以查看栈顶元素。具体代码实现如下：
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if self.empty():
return None
else:
return self.stack.pop()
def top(self):
if self.empty():
return None
else:
return self.stack[-1]
def empty(self):
return len(self.stack) == 0栈的简单应用：括号匹配问题
问题描述：
给定一个字符串，字符串中只包含小括号 ()、中括号 []、大括号 {}，求该字符串中的括号是否匹配。匹配规则：成对出现或者左右对称出现，例如：
()[]{}：匹配；{[()]}：匹配；({}]：不匹配；()]：不匹配；({)}：不匹配
通过栈来解决：
有字符串 ()[{}]，依次取每个括号，只要是左括号就进栈，只要是右括号就判断栈顶是否为对应的左括号，具体步骤如下：
- ① 遇到左小括号 (，执行进栈操作；
- ② 遇到右小括号 )，判断此时栈顶是否为左小括号 (，是则让左小括号 ( 出栈，此时栈为空;
- ③ 遇到左中括号 [，执行进栈操作；
- ④ 遇到左大括号 {，执行进栈操作；
- ⑤ 遇到右大括号 }，判断此时栈顶是否为左大括号 {，是则让左大括号 { 出栈，此时栈为空；
- ⑥ 遇到右中括号 ]，判断此时栈顶是否为左中括号 [，是则让左中括号 [ 出栈，此时栈为空；
- ⑦ 判断最终的栈是否为空，是则表示匹配，不是则表示不匹配。其中第 ② ⑤ ⑥ 步中，若判断为不是，则直接表示不匹配。
Python 代码实现：
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if self.empty():
return None
else:
return self.stack.pop()
def top(self):
if self.empty():
return None
else:
return self.stack[-1]
def empty(self):
return len(self.stack) == 0
def brackets_match(s):
match_dict = {'}': '{', ']': "[", ')': '('}
stack = Stack()
for ch in s:
if ch in ['(', '[', '{']: # 如果为左括号，则执行进栈操作
stack.push(ch)
else: # 如果为右括号
if stack.empty(): # 如果栈为空，则不匹配，即多了一个右括号，没有左括号匹配
return False
elif stack.top() == match_dict[ch]: # 如果栈顶的元素为对应的左括号，则让栈顶出栈
stack.pop()
else: # 如果栈顶元素不是对应的左括号，则不匹配
return False
if stack.empty(): # 最后的栈如果为空，则匹配，否则不匹配
return True
else:
return False
print(brackets_match('[{()}(){()}[]({}){}]'))
print(brackets_match('()[{}]'))
print(brackets_match('({)}'))
print(brackets_match('[]}'))输出结果：
True
True
False
False栈的简单应用：倒序输出一组元素
把元素存入栈，再顺序取出：
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if self.empty():
return None
else:
return self.stack.pop()
def top(self):
if self.empty():
return None
else:
return self.stack[-1]
def empty(self):
return len(self.stack) == 0
def reverse_list(s):
stack = Stack()
for ch in s:
stack.push(ch)
new_list = []
while not stack.empty():
new_list.append(stack.pop())
return new_list
print(reverse_list(['A', 'B', 'C', 'D', 'E']))输出结果：
['E', 'D', 'C', 'B', 'A']
