文本是《数据结构（共13篇）》专题的第 4 篇。阅读本文前，建议先阅读前面的文章：
1.Python数组详解与封装：从基础到动态数组实现2.链表详解教程：从基础概念到Python实现 | 动态数据结构完整指南3.数组队列与循环队列详解：原理、时间复杂度与 Python 实现
一、概念描述
栈是一种线性的数据结构
相比数组栈操作的是数组的子集
只能从一端添加元素也只能从一端取出元素(这一端称为栈顶)
栈在计算机世界里对于程序逻辑有非常重要的作用
二、Stack
1、入栈
2、出栈
通过对比可以看出栈是一种后进先出的数据结构；也就是Last In First Out，缩写为LIFO。
三、栈相关的应用场景
1、无处不在的Undo操作（撤销）
2、程序调用所使用的系统栈
def main():
fun_a()
def fun_a():
print("fun_a()开始执行")
fun_b()
print("fun_a()执行完毕")
def fun_b():
print("fun_b()开始执行")
fun_c()
print("fun_b()执行完毕")
def fun_c():
print("fun_c()开始执行")
print("fun_c()")
print("fun_c()执行完毕")
if __name__ == "__main__":
main()
测试代码执行过程图示
通过以上图示可以看出，系统栈对于程序的子过程调用非常重要，它可以记录上一次调用的点，当程序执行完成一个子过程后通过这个记录可以快速的找到上一次未完成的操作继续执行；深入研究这个逻辑的话可以帮助我们更好的理解递归的操作。
四、栈的基本实现
4.1 栈的基本方法
def push(e): # 入栈
pass
def pop(): # 出栈
pass
def peek(): # 查看栈顶元素
pass
def get_size(): # 查看栈一共有多少元素
pass
def is_empty(): # 查看栈是否为空
pass
其实从用户的角度去看，支持这些操作就可以满足日常的需求，具体的底层实现，用户是不会去关心的，实现底层有多种方式。
4.2 栈的底层实现（数组实现）
from abc import ABC, abstractmethod
# 定义Stack接口
class Stack(ABC):
"""栈的抽象基类"""
@abstractmethod
def get_size(self):
"""获取栈的长度"""
pass
@abstractmethod
def is_empty(self):
"""查看栈是否为空"""
pass
@abstractmethod
def push(self, e):
"""入栈"""
pass
@abstractmethod
def pop(self):
"""出栈"""
pass
@abstractmethod
def peek(self):
"""查看栈顶元素"""
pass
# Stack实现类
class ArrayStack(Stack):
"""基于数组实现的栈"""
def __init__(self, capacity=10):
"""ArrayStack构造器"""
self.array = Array(capacity)
def get_size(self):
"""获取栈中元素的个数"""
return self.array.get_size()
def is_empty(self):
"""判断栈是否为空"""
return self.array.is_empty()
def push(self, e):
"""向栈中添加一个元素"""
self.array.add_last(e)
def pop(self):
"""出栈"""
return self.array.remove_last()
def peek(self):
"""查看栈顶元素"""
return self.array.get_last()
def get_capacity(self):
"""获取栈的容量"""
return self.array.get_capacity()
def __str__(self):
"""重写toString方法"""
res = "Stack: ["
for i in range(self.array.get_size()):
res += str(self.array.get(i))
if i != self.array.get_size() - 1:
res += ", "
res += "] top"
return res
# 测试Stack
def main():
array_stack = ArrayStack()
for i in range(5):
array_stack.push(i)
print(array_stack)
array_stack.pop()
print(array_stack)
if __name__ == "__main__":
main()
五、栈的另一个应用(括号匹配练习)
5.1 问题描述
假设一个算术表达式中可以包含三种括号：圆括号"("和")"，方括号"["和"]"和花括号"{"和"}"，且这三种括号可按任意的次序嵌套使用（如：…[…{… …[…]…]…[…]…(…)…)。编写判别给定表达式中所含括号是否正确配对出现的算法。输出结果True或者False。
5.2 代码实现
# 括号匹配
class Solution:
def is_valid(self, s):
stack = []
for c in s:
if c in '([{':
stack.append(c)
else:
if not stack:
return False
pop_char = stack.pop()
if c == ')' and pop_char != '(':
return False
if c == ']' and pop_char != '[':
return False
if c == '}' and pop_char != '{':
return False
return len(stack) == 0
def main():
solution = Solution()
print(solution.is_valid("()[]{}"))
print(solution.is_valid("([)]"))
if __name__ == "__main__":
main()
5.3 原理解析
1️⃣ 首先需要一个空的栈来接收传来的字符
2️⃣ 依次检查传来的字符是否为括号的左半部分，如果是则放入栈中
3️⃣ 拿到字符串中括号的右半部分与栈中的已有的字符进行判断，如果是左右对称的则将栈中的字符弹出；等到栈中所有的字符都匹配完成会返回结果，此实例的结果为true
4️⃣ 这个实例将无法得到匹配，结果为false
5.4 括号匹配总结
栈顶元素反映了在嵌套的层次关系中，最近的需要匹配的元素。
您已阅读完《数据结构（共13篇）》专题的第 4 篇。请继续阅读该专题下面的文章：
5.二分搜索树详解｜定义、原理、代码实现与操作解析6.Python集合Set实现详解：二分搜索树vs链表性能对比 | 数据结构教程7.映射（Map）数据结构详解：链表与二分搜索树实现（含 Python 代码与性能对比）8.优先队列与堆（Heap）详解：概念、实现、Heapify 与应用9.线段树详解：原理、构建、区间查询与更新（Python 实现）10.Trie字典树详解 – 基础原理与代码实现11.并查集详解与实现优化：从Quick Find到路径压缩的完整进化过程12.AVL平衡二叉树详解及实现（Python版）13.红黑树与2-3树详解：性质、等价性与Python实现
《光影对决》11月9日开测 重燃MOBA热血淘宝取消订单钱多久退？运费险取消订单退吗？