OI-wiki 数据结构指南栈Stack的原理、数组模拟与 STL 实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读栈是 OI / ACM-ICPC 竞赛中最基础也最高频使用的线性数据结构之一其「后进先出LIFO」特性贯穿递归、括号匹配、表达式求值、DFS、单调栈、双栈模拟队列等大量经典算法。本文以 OI-wiki 的 栈stack 文档为主线系统讲解栈的定义与 LIFO 的准确含义、C 与 Python 两种语言的数组模拟实现、C STL 容器std::stack的模板定义与底层容器机制并结合本仓库的源码实例双栈模拟队列、平衡树祖先栈展示栈在真实竞赛代码中的落地用法。读完本文你将能够手写零依赖的栈、正确选用并驾驭 STL 栈并能看懂仓库中依赖栈实现的各类数据结构代码。什么是栈后进先出LIFO表栈是 OI 中常用的一种线性数据结构。请注意本文讨论的是数据结构意义上的栈而非程序运行时的系统栈 / 调用栈空间在 递归与 DFS 相关章节 中讨论的递归栈属于后者。栈的修改与访问都只发生在栈顶top一端新元素只能从栈顶压入也只有栈顶元素能被查看或弹出。因此栈的修改与访问严格按照后进先出last in first out原则进行栈通常也被称为后进先出表简称LIFO 表。LIFO 的准确含义看的是「当前容器内」一个常见的误区是把 LIFO 理解成“整个操作序列中最后进入的一定最先出去”。OI-wiki 在 stack.md 中专门给出了反例考虑如下操作序列push(1) pop(1) push(2) pop(2)如果从整体考虑1 最先入栈、最先出栈2 最后入栈、最后出栈反而表现得像一个“先进先出表”这显然是错误的理解。正确的表述是LIFO 表达的是当前在容器内最后进来的最先出去。也就是说判定一个数据结构是 LIFO 还是 FIFO应当考察的是某一时刻容器内现存元素的相对进出顺序而不是跨越整个时间轴的全部元素。这与队列的 FIFO先进先出见 队列恰好形成对偶关系。使用数组模拟栈在不需要 STL 或希望完全掌控内存布局的场合可以方便地用一维数组模拟栈核心思想是用一个下标指针同时表示栈中元素数量与栈顶位置。两种主流语言的实现如下完整代码来自 stack.md。C 实现int st[N]; // 这里使用 st[0] (即 *st) 代表栈中元素数量同时也是栈顶下标 // 压栈 st[*st] var1; // 取栈顶 int u st[*st]; // 弹栈注意越界问题*st 0 时不能继续弹出 if (*st) --*st; // 清空栈 *st 0;这段代码的精妙之处在于st[0]被复用作「元素个数 / 栈顶下标」st[*st] var1先让数量自增等价于栈顶下标上移一格再写入元素if (*st) --*st在弹栈前先判空避免对空栈执行非法下标的访问。Python 实现st [0] * N # 这里使用 st[0] 代表栈中元素数量同时也是栈顶下标 # 压栈 st[st[0] 1] var1 st[0] st[0] 1 # 取栈顶 u st[st[0]] # 弹栈注意越界问题st[0] 0 时不能继续弹出 if st[0]: st[0] st[0] - 1 # 清空栈 st[0] 0复杂度与注意事项压栈、取栈顶、弹栈、清空均为O(1)时间空间复杂度为 O(N)N 为数组容量。两个易错点一是弹栈前判空空栈继续--会导致下标越界或下溢二是压栈前检查容量st[0] N时不能再压入否则越界。这也是 竞赛常见错误文档 中反复强调的边界问题。C STL 中的栈std::stackC STL 提供了现成的容器std::stack使用前需要引入stack头文件。模板定义与底层容器机制std::stack在标准库中是一个容器适配器container adapter它并不自己持有数据而是封装一个底层容器来存储元素。其定义见 stack.md 与 container-adapter.md为// clang-format off template class T, class Container std::dequeT class stack;Tstack 中要存储的数据类型。Container用于存储元素的底层容器类型这个容器必须提供通常语义的下列函数back()push_back()pop_back()STL 容器std::vector、std::deque和std::list均满足这些要求如果不指定默认使用std::deque作为底层容器。由于栈只在一端操作std::deque恰好能在常数时间完成push_back/pop_back/back且内存增长策略比vector更稳健。三种定义方式std::stackTypeName s; // 使用默认底层容器 deque数据类型为 TypeName std::stackTypeName, Container s; // 使用 Container 作为底层容器 std::stackTypeName s2(s1); // 将 s1 复制一份用于构造 s2从仓库代码看指定自定义底层容器的写法并不罕见例如 SizeBalancedTreeMap.hpp 中的祖先节点路径栈。默认情况下直接使用std::stackTypeName即可。常用成员函数类别成员函数作用元素访问st.top()返回栈顶元素栈为空时调用会出错修改st.push(x)插入传入的参数到栈顶修改st.pop()弹出栈顶元素容量st.empty()返回是否为空容量st.size()返回元素数量上述成员函数均为O(1) 常数复杂度见 container-adapter.md这也是std::stack与手写数组模拟在性能上等价、却更安全易用的原因。赋值与复制示例std::stack还提供了一些运算符较为常用的是赋值运算符示例来自 stack.md// 新建两个栈 st1 和 st2 std::stackint st1, st2; // 为 st1 装入 1 st1.push(1); // 将 st1 赋值给 st2 st2 st1; // 输出 st2 的栈顶元素 cout st2.top() endl; // 输出: 1复制构造std::stackint s2(s1)的完整行为可参考 container-adapter.md 中的示例对 s1 弹出元素不会影响 s2二者在赋值 / 拷贝后互相独立。仓库实战双栈模拟队列栈只在一端进出但利用两个栈可以模拟一个先进先出的队列这是栈的经典应用之一仓库在 队列文档 中介绍了原理并在 docs/ds/code/queue/queue_2.cpp 给出了完整可运行的参考实现#include cstdio #include stack using namespace std; struct Queue { stackint f, s; bool empty() { return f.empty() s.empty(); } void push(int x) { f.push(x); } void pop() { if (s.empty()) for (; !f.empty(); f.pop()) s.push(f.top()); s.pop(); } int front() { if (s.empty()) for (; !f.empty(); f.pop()) s.push(f.top()); return s.top(); } int size() { return f.size() s.size(); } };其思想是栈f作队尾、栈s作队首。push 直接压入fpop / front 时若s为空则把f的元素逐一弹出再压入s顺序恰好颠倒s的栈顶即队首。可以证明每个元素只会进入 / 转移 / 弹出一次均摊复杂度 O(1)。这份源码同时示范了empty()、push()、pop()、top()、size()五个成员函数的组合用法。仓库实战平衡树中的祖先栈std::stack在竞赛数据结构中另一个高频场景是保存从根到当前节点的祖先路径。仓库中的 AvlTreeMap.hppAVL 树实现在erase等操作中多次使用std::stackNodePtr ancestors;见该文件第 314、374、435、492 行等暂存待回溯的祖先节点用于自底向上的旋转与平衡修正SizeBalancedTreeMap.hpp 同样用std::stackNodePtr path;与std::stackNodePtr stack;实现非递归的路径维护与遍历见该文件第 890、950 行。这正体现了“栈天然适合保存回溯路径”的 LIFO 特性——后访问的节点先回溯。使用 Python 的 list 模拟栈在 Python 中可以直接用内置列表list模拟栈因为list天然支持在尾部 O(1) 追加与弹出来自 stack.mdst [5, 1, 4] # 使用 append() 向栈顶添加元素 st.append(2) st.append(3) # st # [5, 1, 4, 2, 3] # 使用 pop 取出栈顶元素 st.pop() # st # [5, 1, 4, 2] # 使用 clear 清空栈 st.clear()append(x)等价于压栈pop()不带参数等价于弹栈并返回栈顶st[-1]等价于查看栈顶clear()等价于清空栈。相比「数组 计数指针」的手写方式list方式代码更简洁、不易越界适合快速实现与 Python 竞赛编程二者在逻辑上是完全等价的。进阶从栈到单调栈掌握基础栈后可以进一步学习其最重要的变体——单调栈monotonic-stack.md。单调栈即满足单调性递增或递减的栈插入元素时不断弹出破坏单调性的栈顶元素从而在 O(n) 时间内解决「下一个更大 / 更小元素」类问题并可用于离线解决 RMQ。此外表达式求值中缀转后缀、DFS、笛卡尔树 等主题也都建立在栈的 LIFO 语义之上。参考资料与延伸阅读本文主体OI-wiki 栈stackSTL 容器适配器总览栈 / 队列 / 优先队列的定义、复杂度与示例container-adapter.md与栈对偶的 FIFO 结构及双栈模拟队列文档见 queue.md源码见 queue_2.cpp栈的单调性变体OI-wiki 单调栈栈在自平衡树实现中的实际应用AVL 树 AvlTreeMap.hpp、Size Balanced Tree SizeBalancedTreeMap.hpp【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 数据结构指南：栈（Stack）的原理、数组模拟与 STL 实战
OI-wiki 数据结构指南栈Stack的原理、数组模拟与 STL 实战【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读栈是 OI / ACM-ICPC 竞赛中最基础也最高频使用的线性数据结构之一其「后进先出LIFO」特性贯穿递归、括号匹配、表达式求值、DFS、单调栈、双栈模拟队列等大量经典算法。本文以 OI-wiki 的 栈stack 文档为主线系统讲解栈的定义与 LIFO 的准确含义、C 与 Python 两种语言的数组模拟实现、C STL 容器std::stack的模板定义与底层容器机制并结合本仓库的源码实例双栈模拟队列、平衡树祖先栈展示栈在真实竞赛代码中的落地用法。读完本文你将能够手写零依赖的栈、正确选用并驾驭 STL 栈并能看懂仓库中依赖栈实现的各类数据结构代码。什么是栈后进先出LIFO表栈是 OI 中常用的一种线性数据结构。请注意本文讨论的是数据结构意义上的栈而非程序运行时的系统栈 / 调用栈空间在 递归与 DFS 相关章节 中讨论的递归栈属于后者。栈的修改与访问都只发生在栈顶top一端新元素只能从栈顶压入也只有栈顶元素能被查看或弹出。因此栈的修改与访问严格按照后进先出last in first out原则进行栈通常也被称为后进先出表简称LIFO 表。LIFO 的准确含义看的是「当前容器内」一个常见的误区是把 LIFO 理解成“整个操作序列中最后进入的一定最先出去”。OI-wiki 在 stack.md 中专门给出了反例考虑如下操作序列push(1) pop(1) push(2) pop(2)如果从整体考虑1 最先入栈、最先出栈2 最后入栈、最后出栈反而表现得像一个“先进先出表”这显然是错误的理解。正确的表述是LIFO 表达的是当前在容器内最后进来的最先出去。也就是说判定一个数据结构是 LIFO 还是 FIFO应当考察的是某一时刻容器内现存元素的相对进出顺序而不是跨越整个时间轴的全部元素。这与队列的 FIFO先进先出见 队列恰好形成对偶关系。使用数组模拟栈在不需要 STL 或希望完全掌控内存布局的场合可以方便地用一维数组模拟栈核心思想是用一个下标指针同时表示栈中元素数量与栈顶位置。两种主流语言的实现如下完整代码来自 stack.md。C 实现int st[N]; // 这里使用 st[0] (即 *st) 代表栈中元素数量同时也是栈顶下标 // 压栈 st[*st] var1; // 取栈顶 int u st[*st]; // 弹栈注意越界问题*st 0 时不能继续弹出 if (*st) --*st; // 清空栈 *st 0;这段代码的精妙之处在于st[0]被复用作「元素个数 / 栈顶下标」st[*st] var1先让数量自增等价于栈顶下标上移一格再写入元素if (*st) --*st在弹栈前先判空避免对空栈执行非法下标的访问。Python 实现st [0] * N # 这里使用 st[0] 代表栈中元素数量同时也是栈顶下标 # 压栈 st[st[0] 1] var1 st[0] st[0] 1 # 取栈顶 u st[st[0]] # 弹栈注意越界问题st[0] 0 时不能继续弹出 if st[0]: st[0] st[0] - 1 # 清空栈 st[0] 0复杂度与注意事项压栈、取栈顶、弹栈、清空均为O(1)时间空间复杂度为 O(N)N 为数组容量。两个易错点一是弹栈前判空空栈继续--会导致下标越界或下溢二是压栈前检查容量st[0] N时不能再压入否则越界。这也是 竞赛常见错误文档 中反复强调的边界问题。C STL 中的栈std::stackC STL 提供了现成的容器std::stack使用前需要引入stack头文件。模板定义与底层容器机制std::stack在标准库中是一个容器适配器container adapter它并不自己持有数据而是封装一个底层容器来存储元素。其定义见 stack.md 与 container-adapter.md为// clang-format off template class T, class Container std::dequeT class stack;Tstack 中要存储的数据类型。Container用于存储元素的底层容器类型这个容器必须提供通常语义的下列函数back()push_back()pop_back()STL 容器std::vector、std::deque和std::list均满足这些要求如果不指定默认使用std::deque作为底层容器。由于栈只在一端操作std::deque恰好能在常数时间完成push_back/pop_back/back且内存增长策略比vector更稳健。三种定义方式std::stackTypeName s; // 使用默认底层容器 deque数据类型为 TypeName std::stackTypeName, Container s; // 使用 Container 作为底层容器 std::stackTypeName s2(s1); // 将 s1 复制一份用于构造 s2从仓库代码看指定自定义底层容器的写法并不罕见例如 SizeBalancedTreeMap.hpp 中的祖先节点路径栈。默认情况下直接使用std::stackTypeName即可。常用成员函数类别成员函数作用元素访问st.top()返回栈顶元素栈为空时调用会出错修改st.push(x)插入传入的参数到栈顶修改st.pop()弹出栈顶元素容量st.empty()返回是否为空容量st.size()返回元素数量上述成员函数均为O(1) 常数复杂度见 container-adapter.md这也是std::stack与手写数组模拟在性能上等价、却更安全易用的原因。赋值与复制示例std::stack还提供了一些运算符较为常用的是赋值运算符示例来自 stack.md// 新建两个栈 st1 和 st2 std::stackint st1, st2; // 为 st1 装入 1 st1.push(1); // 将 st1 赋值给 st2 st2 st1; // 输出 st2 的栈顶元素 cout st2.top() endl; // 输出: 1复制构造std::stackint s2(s1)的完整行为可参考 container-adapter.md 中的示例对 s1 弹出元素不会影响 s2二者在赋值 / 拷贝后互相独立。仓库实战双栈模拟队列栈只在一端进出但利用两个栈可以模拟一个先进先出的队列这是栈的经典应用之一仓库在 队列文档 中介绍了原理并在 docs/ds/code/queue/queue_2.cpp 给出了完整可运行的参考实现#include cstdio #include stack using namespace std; struct Queue { stackint f, s; bool empty() { return f.empty() s.empty(); } void push(int x) { f.push(x); } void pop() { if (s.empty()) for (; !f.empty(); f.pop()) s.push(f.top()); s.pop(); } int front() { if (s.empty()) for (; !f.empty(); f.pop()) s.push(f.top()); return s.top(); } int size() { return f.size() s.size(); } };其思想是栈f作队尾、栈s作队首。push 直接压入fpop / front 时若s为空则把f的元素逐一弹出再压入s顺序恰好颠倒s的栈顶即队首。可以证明每个元素只会进入 / 转移 / 弹出一次均摊复杂度 O(1)。这份源码同时示范了empty()、push()、pop()、top()、size()五个成员函数的组合用法。仓库实战平衡树中的祖先栈std::stack在竞赛数据结构中另一个高频场景是保存从根到当前节点的祖先路径。仓库中的 AvlTreeMap.hppAVL 树实现在erase等操作中多次使用std::stackNodePtr ancestors;见该文件第 314、374、435、492 行等暂存待回溯的祖先节点用于自底向上的旋转与平衡修正SizeBalancedTreeMap.hpp 同样用std::stackNodePtr path;与std::stackNodePtr stack;实现非递归的路径维护与遍历见该文件第 890、950 行。这正体现了“栈天然适合保存回溯路径”的 LIFO 特性——后访问的节点先回溯。使用 Python 的 list 模拟栈在 Python 中可以直接用内置列表list模拟栈因为list天然支持在尾部 O(1) 追加与弹出来自 stack.mdst [5, 1, 4] # 使用 append() 向栈顶添加元素 st.append(2) st.append(3) # st # [5, 1, 4, 2, 3] # 使用 pop 取出栈顶元素 st.pop() # st # [5, 1, 4, 2] # 使用 clear 清空栈 st.clear()append(x)等价于压栈pop()不带参数等价于弹栈并返回栈顶st[-1]等价于查看栈顶clear()等价于清空栈。相比「数组 计数指针」的手写方式list方式代码更简洁、不易越界适合快速实现与 Python 竞赛编程二者在逻辑上是完全等价的。进阶从栈到单调栈掌握基础栈后可以进一步学习其最重要的变体——单调栈monotonic-stack.md。单调栈即满足单调性递增或递减的栈插入元素时不断弹出破坏单调性的栈顶元素从而在 O(n) 时间内解决「下一个更大 / 更小元素」类问题并可用于离线解决 RMQ。此外表达式求值中缀转后缀、DFS、笛卡尔树 等主题也都建立在栈的 LIFO 语义之上。参考资料与延伸阅读本文主体OI-wiki 栈stackSTL 容器适配器总览栈 / 队列 / 优先队列的定义、复杂度与示例container-adapter.md与栈对偶的 FIFO 结构及双栈模拟队列文档见 queue.md源码见 queue_2.cpp栈的单调性变体OI-wiki 单调栈栈在自平衡树实现中的实际应用AVL 树 AvlTreeMap.hpp、Size Balanced Tree SizeBalancedTreeMap.hpp【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考