定义
栈（Stack）是一种后进先出（LIFO，Last In First Out）的线性表，一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。。栈的基本操作有：入栈（push）、出栈（pop）、查看栈顶元素（top）等。
栈的实现
栈的实现方式共有三种：
- 数组实现：使用一组连续的内存空间来存储栈中的元素，栈顶指针指向栈顶元素的下一个位置。入栈时，将新元素存储在栈顶指针的下一个位置；出栈时，将栈顶元素移动到栈顶指针的位置，并释放该空间。
- 链表实现：使用一组节点来存储栈中的元素，每个节点包含一个数据域和一个指向下一个节点的指针。入栈时，将新元素添加到链表尾部；出栈时，将栈顶元素从链表中移除，并更新栈顶指针。
- 递归实现：利用递归的方式实现栈的操作，如push和pop。这种实现方式较为简洁，但效率较低。
以下只展示链表实现
class Node:
def __init__(self,elem,next=None):
self.elem = elem
self.next = next
class Stack:
def __init__(self):
self.top = None
self._len = 0
@property
def len(self):
return self._len
def push(self,elem):
p = Node(elem)
if self.top is None:
self.top = p
else:
p.next = self.top
self.top= p
self._len += 1
def pop(self):
if self._len:
current_p = self.top
for i in range(self._len-1):
current_p = current_p.next
elem = current_p.next.elem
current_p.next = None
return elem
else:
print("Stack is empty")
def display(self):
stack = []
if self._len:
current_p = self.top
for i in range(self._len):
print(current_p.__dict__)
stack.append(current_p.elem)
current_p = current_p.next
print(f"stack:{stack}")
return stack
def is_empty(self):
return bool(self._len)
def __len__(self):
return self._len
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.display()
应用场景
历史记录的回退
1、浏览器浏览的回退
网络浏览器将最近浏览的网址存放在一个栈中。每当用户访问者访问一个新网站时，这个新网站的网址就被压入栈顶。这样，每当我们在浏览器单击“后退”按钮时（或者按键盘快捷键 CTRL+Z ，大部分撤销快捷键），就可以弹出当前最近一次访问的网址，以回到其先前访问的浏览状态。
2、文本编辑的撤销
文本编辑器通常会提供一个“撤销”机制以取消最近的编辑操作并返回到先前状态。这个撤销操作也是通过将文本的变化状态保存在一个栈中得以实现。
3、回溯（玩游戏，寻找路径，穷举搜索）
内存管理
一些高级语言的内存管理，JVM 的栈、Python 栈还用于内存管理、嵌套语言特性的运行时环境等
算法
汉诺塔、树形遍历、直方图问题，也用于图算法，如拓扑排序
语法处理：
参数和局部变量的空间是用堆栈在内部创建的。
编译器对大括号匹配的语法检查
对递归的支持
在编译器中像后缀或前缀一样的表达式
