栈
栈是一种后进先出（last-in, first-out）（LIFO）的数据结构。
允许添加元素的一端为栈顶（top），另一端为栈底（bottom）。
栈的空间复杂度为O(n)。
栈的操作以及时间复杂度
| 操作 | 含义 | 时间复杂度 |
|---|---|---|
| push | 进栈 | O(1) |
| pop | 出栈 | O(1) |
| peek | 取栈顶元素 | O(1) |
| is_empty | 判空 | O(1) |
栈的所有操作均可以在常数时间（O(1)）完成。
将列表用作栈
对于判空操作，可以有两种方式：
- len(stack) == 0
- try...except...尝试pop如果出错则为空
Python内置的数据结构，因为有cpython在底层c的加速和优化实现，len操作都会非常快。但理论上讲，如果是自定义的数据结构，有可能会尝试遍历整个结构，从而时间复杂度达到O(n)。
直接尝试pop从理论上讲也达到了O(1)级别，所以也许会更快。
前者更加具有简洁性和可读性，后者效率更高、性能更好。大多数情况下，日常使用中，栈这一结构的元素数量也许不会太多，比如1000条以内，优化个几纳秒（ns）的速度其实无关紧要。但有人觉得万一数量变多了呢，还有人觉得要追求极致的速度优化，况且后者更符合某种风格。这个就看实际情况，见仁见智了。
总之，日常使用时两者都可以。（我还是更推荐try-except）
日常用栈
# 建立栈
stack = []
# push
stack.append(1)
stack.append(2)
# pop
top = stack.pop()
# peek
peek_item = stack[-1]
# is_empty
is_empty = len(stack) == 0
也可以简单封装一下
class Stack:
def __init__(self):
self._data = []
def push(self, item):
self._data.append(item)
def pop(self):
return self._data.pop()
def peek(self):
return self._data[-1]
def is_empty(self):
try:
self._data.pop()
except IndexError:
return True
else:
return False
if __name__ == '__main__':
s = Stack()
s.push(1)
s.push(2)
top = s.pop()
print(f'top={top}')
peek_item = s.peek()
print(f'peek={peek_item}')
print(s.is_empty())
栈帧（Frame）与递归（Recursion）
几乎所有的编程语言都会有函数调用栈，Python称之为帧（Frame）。
每调用一个函数，就是在做push操作；函数执行完成，回到上一帧，即pop。
递归（Recursion）就是通过栈帧来实现的。
可以通过栈的数据结构，建立一个栈，自行实现递归操作。这作为学习和练习可能是个好案例，但实际当中用得很少，也似乎没有必要。
Python中的栈帧是在底层C语言中优化过的，尤其是在Python 3.11有了很大程度的提升。
以下所有均取自官方文档：
开销更低、更为惰性的 Python 帧
存放执行信息的 Python 帧会在 Python 调用一个 Python 函数时被自动创建。 下面是新帧的优化操作:
- 优化改进了帧创建进程。
- 通过大量重用 C 栈上的帧空间来避免内存分配。
- 将内部帧结构优化为仅包含关键信息。 在此之前的帧保存有额外的调试和内存管理信息。
现在旧式的帧对象仅在调试器或 Python 内省函数如 sys._getframe() 和 inspect.currentframe() 发出请求时才会被创建。 对于大多数用户代码，将不会创建任何帧对象。 因此，几乎所有 Python 函数调用都有显著的提速。 我们在 pyperformance 中测得了 3-7% 的提速。
内联的 Python 函数调用
在 Python 函数调用期间，Python 将调用一个评测 C 函数来解读该函数的代码。 这会有效地将纯 Python 递归限制在 C 栈的安全范围以内。
在 3.11 中，当 CPython 检测到 Python 代码调用了另一个 Python 函数时，它会设置一个新帧，并“跳转”到新帧内部的新代码。 这可以避免全部调用 C 解析函数。
大多数 Python 函数调用现在将不消耗任何 C 栈空间，这提升了它们的速度。 在简单的递归函数如斐波那契或阶乘函数中，我们测得了 1.7x 的提速。 这还意味着递归函数能够递归得更深（如果用户通过 sys.setrecursionlimit()提升了递归限制的话）。 我们在 pyperformance 中测得了 1-3% 的提升。
