栈

0 Stack Basic 栈是什么？ 栈是一种受限的线性表：只允许在同一端（栈顶 top）进行插入和删除。 LIFO（Last In, First Out）：后进先出 两个核心操作：push（入栈）、pop（出栈） 辅助操作：peek/top（看栈顶不弹出）、isEmpty、size 栈 Stack 队列 Queue 顺序 LIFO 后进先出 FIFO 先进先出 操作端 同一端 两端（尾进头出） 典型算法 DFS、回溯、单调栈、表达式求值 BFS、拓扑排序、滑动窗口(单调队列) Python 实现 list collections.deque 实现方式： 数组实现（顺序栈）： 1stack = [] 2stack.append(x) # push, 摊还 O(1) 3x = stack.pop() # pop, O(1) 4x = stack[-1] # peek, O(1) 5if not stack: ... # isEmpty 6len(stack) # size 链表实现（链式栈）：头插法建链表，头结点即栈顶 1class Node: 2 def __init__(self, val, nxt=None): 3 self.val, self.next = val, nxt 4 5class LinkedStack: 6 def __init__(self): 7 self.head = None # 栈顶 8 self.n = 0 9 10 def push(self, val): 11 self.head = Node(val, self.head) # 新节点指向旧栈顶 12 self.n += 1 13 14 def pop(self): 15 val = self.head.val 16 self.head = self.head.next 17 self.n -= 1 18 return val 操作 数组栈 链表栈 push/pop 摊还 O(1) 严格 O(1) 空间 可能有预留空位 每个元素多一个指针 缓存友好 连续内存 节点分散 1 栈的设计与模拟 1.1 最小栈 | Medium 题目：设计支持 push / pop / top / getMin 的栈，所有操作 O(1) ...