1. Stack

1.1 基础概念

在计算机科学领域，stack（栈）是一种极为重要的数据结构，遵循 “先进后出（First In Last Out，FIFO）” 原则。形象地说，它就像一个只有一端开口的容器，你从开口处放入物品，最后放入的物品总是最先被取出。在 C++ 的 STL 中，stack 被实现为一个容器适配器。所谓容器适配器，是对其他容器进行包装，修改其接口，使其呈现出特定数据结构的行为。stack 默认以 deque（双端队列）作为底层容器，当然也可以指定其他符合要求的容器。

欲使用 Stack，必须包含头文件

#include <stack>
int main() {
    std::stack<int> s;
}

上述代码声明了一个能存储整数的 stack 对象s。

1.2 支持的操作

1.2.1 push()

用于将元素添加到栈顶。例如：

std::stack<int> s;
s.push(10);
s.push(20);

1.2.2 pop()

移除栈顶元素。要注意，此操作不会返回被移除的元素。例如：

std::stack<int> s;
s.push(10);
s.push(20);
s.pop();

执行后，s的栈顶元素变为 10，元素 20 已被移除。

1.2.3 top()

返回栈顶元素的引用，但不移除它。使用前需确保栈非空，否则行为未定义。示例如下：

std::stack<int> s;
s.push(10);
int topElement = s.top(); // topElement为10

1.2.4 size()

返回栈中元素的数量。

std::stack<int> s;
s.push(10);
s.push(20);
size_t stackSize = s.size(); // stackSize为2

1.2.5 empty()

检查栈是否为空，为空返回true，否则返回false。

std::stack<int> s;
bool isEmpty = s.empty(); // isEmpty为true
s.push(10);
isEmpty = s.empty(); // isEmpty为false

1.2.6 emplace()

在栈顶直接构造元素，而非先构造再复制或移动。相比push，若构造对象开销大，emplace能提升性能。例如：

std::stack<std::string> s;
s.emplace("hello"); // 直接在栈顶构造字符串对象

1.3 stack的底层数据结构

如前文所述，STL 中的 stack 默认底层结构是 deque。查看 stack 定义：

template<class _Ty, class _Container = deque<_Ty> >
class stack {
    ...
}

这里，_Ty是存储元素的类型，_Container是底层容器类型，默认是deque<_Ty>。

选择 deque 作为默认底层容器，原因如下：

操作效率：deque 在两端进行插入和删除操作的时间复杂度为 O (1)，stack 操作主要在一端（栈顶）进行，deque 能高效支持。比如push和pop操作，deque 的push_back和pop_back能很好适配，无需大量元素移动。
内存管理：deque 内存分配灵活，可动态增长和收缩，适合 stack 元素数量不定的场景。与 vector 相比，vector 扩容时可能需重新分配内存、复制元素，开销大；deque 则避免了此问题。
功能适配：stack 只需在一端操作，无需随机访问等功能，deque 虽不擅长随机访问，但对 stack 功能需求支持良好。且 stack 不允许遍历，deque 的遍历性能劣势在 stack 场景中无关紧要。

除 deque 外，理论上只要满足back()、push_back()和pop_back()操作的容器，都可作为 stack 底层容器，如 vector 和 list。不过实际应用中，vector 作 stack 底层，插入删除元素时，因可能需移动大量元素，效率不如 deque；list 虽能满足操作要求，但内存开销相对较大，存储每个元素需额外指针空间。

1.4 以 List 作为 Stack 的底层数据结构示例

下面看看如何用 list 作为 stack 的底层结构：

#include <stack>
#include <list>
#include <iostream>

int main() {
    std::stack<int, std::list<int>> s;
    s.push(1);
    s.push(2);

    std::wcout << s.size() << std::endl; // 输出2
    std::wcout << s.top() << std::endl; // 输出2

    s.pop();
    std::wcout << s.top() << std::endl; // 输出1

    return 0;
}

上述代码中，声明了一个以std::list<int>为底层容器的std::stack<int>对象s。接着，通过push添加元素，利用size获取元素数量，用top访问栈顶元素，最后用pop移除栈顶元素。

使用 list 作底层容器，在某些场景有优势，如频繁插入删除且元素数量不确定时，list 动态内存管理和无需连续内存的特性可避免内存碎片化和频繁内存分配问题。但因 list 元素非连续存储，访问效率低于 vector 和 deque，在需高效访问元素的场景中不太适用。

1.5 stack的应用场景

函数调用栈：在程序运行中，函数调用通过栈实现。每次调用函数，其局部变量、参数、返回地址等信息压入栈，函数返回时，这些信息从栈顶弹出。例如递归函数执行，递归调用时函数状态入栈，返回时出栈恢复状态。
表达式求值：在计算算术表达式（如后缀表达式求值）时，stack 用处很大。遇到操作数入栈，遇到操作符时，从栈中弹出相应操作数计算，结果再入栈。比如计算3 + 4 * 2，扫描到3和4入栈，扫描到*，弹出4和3计算得12入栈，扫描到+，弹出12和2计算得最终结果。
括号匹配：在检查代码中括号（如()、[]、{}）是否匹配时，stack 很有用。遇到左括号入栈，遇到右括号时，从栈顶弹出对应左括号匹配，若匹配失败或栈空时遇到右括号，则括号不匹配。例如检查{[()()]}，依次扫描，左括号入栈，右括号弹出匹配，最终栈空则匹配成功。
深度优先搜索（DFS）：在图或树的深度优先搜索算法中，stack 可模拟递归调用栈。从起始节点开始，将其入栈并标记访问，然后不断从栈顶取节点，访问其未访问邻居并压入栈，直到栈空。如在一个简单无向图中从某节点开始 DFS，可借助 stack 按深度优先顺序遍历图中节点。