引言

在 C++ 编程中，标准模板库（STL）是一个强大的工具集，为开发者提供了各种高效的数据结构和算法。其中，stack 作为 STL 容器适配器，在许多场景下发挥着重要作用。它遵循后进先出（LIFO，Last In First Out）的原则，这种特性使得它在诸如表达式求值、深度优先搜索（DFS）算法等场景中有着广泛应用。本文将深入探讨 STL 容器中的 stack，涵盖其定义、特性、常用操作以及实际应用案例。

一、stack 的定义与特性

（一）定义

stack 并非独立的容器，而是一个容器适配器，它基于其他序列容器（如 deque、vector、list）来实现栈的功能。默认情况下，stack 使用 deque 作为其底层容器。通过这种方式，stack 可以利用底层容器的已有功能，并对其接口进行封装，以提供栈特有的操作。

在代码中，我们可以这样定义一个 stack：

cpp

#include <stack>
std::stack<int> myStack; 

上述代码定义了一个存储 int 类型数据的 stack。

（二）特性

1. 后进先出（LIFO）：这是 stack 最核心的特性。就像一摞盘子，最后放上去的盘子会最先被拿下来。新元素被压入栈顶，而从栈中取出元素时，总是从栈顶取出。
2. 操作受限：stack 仅提供了与栈操作相关的有限接口，如压入元素（push）、弹出元素（pop）、访问栈顶元素（top）以及查询栈的大小（size）和判断栈是否为空（empty）。这种受限的接口设计使得 stack 的使用场景更加明确，同时也保证了其操作的简单性和高效性。

二、stack 的常用操作

（一）元素操作

1. push()：用于将一个元素压入栈顶。例如：

cpp

myStack.push(10); 
myStack.push(20); 

此时，myStack 栈顶元素为 20，栈中元素依次为 20、10（栈底）。2. pop()：弹出栈顶元素，但不返回该元素。注意，在调用 pop() 之前，需要先检查栈是否为空，否则可能导致未定义行为。例如：

cpp

if (!myStack.empty()) {
    myStack.pop(); 
}

执行上述代码后，myStack 栈顶元素变为 10。3. top()：返回栈顶元素的引用。同样，在调用 top() 之前，要确保栈不为空。例如：

cpp

if (!myStack.empty()) {
    int topElement = myStack.top(); 
    std::cout << "Top element: " << topElement << std::endl; 
}

（二）状态查询

1. empty()：判断栈是否为空，返回一个布尔值。如果栈为空则返回 true，否则返回 false。例如：

cpp

bool isEmpty = myStack.empty(); 

1. size()：返回栈中元素的数量。例如：

cpp

size_t stackSize = myStack.size(); 

三、stack 的底层实现与性能分析

（一）底层实现

如前文所述，stack 默认使用 deque 作为底层容器。deque（双端队列）具有在两端高效插入和删除元素的特点，这与 stack 的操作需求相契合。stack 通过封装 deque 的接口，仅暴露栈相关的操作，使得用户可以像使用一个纯粹的栈一样方便。

当选择其他容器作为 stack 的底层实现时，只需在定义 stack 时指定即可。例如，使用 vector 作为底层容器：

cpp

std::stack<int, std::vector<int>> myStackWithVector; 

（二）性能分析

1. push () 和 pop ()：由于底层容器（如 deque）在栈顶操作的高效性，push() 和 pop() 操作的时间复杂度为 \(O(1)\)。这意味着无论栈中有多少元素，压入和弹出一个元素所需的时间基本相同。
2. top()：访问栈顶元素同样具有 \(O(1)\) 的时间复杂度，因为它直接返回栈顶元素的引用，不需要遍历栈中的其他元素。
3. empty () 和 size ()：empty() 操作只需检查底层容器的大小是否为零，时间复杂度为 \(O(1)\)。size() 操作通常也具有 \(O(1)\) 的时间复杂度，因为底层容器（如 deque、vector）都能高效地返回元素数量。

四、stack 的实际应用案例

（一）表达式求值

在数学表达式求值中，stack 常用于处理运算符优先级。例如，对于中缀表达式 (3 + 4) * 2，可以使用两个栈，一个用于存储操作数，另一个用于存储运算符。通过扫描表达式，将操作数压入操作数栈，将运算符根据其优先级压入运算符栈。当遇到优先级更高的运算符时，先处理栈顶运算符及其对应的操作数。这种方法能够有效地处理表达式中的括号和运算符优先级，最终得出表达式的结果。

（二）深度优先搜索（DFS）算法

在图的遍历算法中，DFS 可以使用 stack 来实现。从起始节点开始，将其压入栈中。然后，不断从栈顶取出节点进行访问，并将其未访问过的邻接节点压入栈中。通过这种方式，优先沿着一条路径尽可能深地探索，直到无法继续或达到目标节点。这种基于 stack 的 DFS 实现简洁高效，能够快速遍历图中的节点。

（三）括号匹配检查

在编译器的语法分析或文本处理中，经常需要检查括号是否匹配。例如，对于字符串 {[()]}, 可以使用 stack 来实现。遍历字符串，当遇到左括号时，将其压入栈中；当遇到右括号时，从栈顶弹出一个左括号进行匹配。如果在遍历结束后栈为空，说明括号匹配正确；否则，括号不匹配。这种方法可以有效地处理多种类型括号的匹配问题。

五、总结

STL 容器中的 stack 作为一种重要的数据结构，以其简洁的接口和高效的操作，在众多领域有着广泛的应用。通过深入理解 stack 的定义、特性、常用操作以及性能特点，开发者能够更加灵活地运用它来解决实际问题。无论是在算法设计、编译器开发还是其他编程领域，stack 都能发挥其独特的优势。希望本文的内容能帮助读者更好地掌握 stack 的使用，在日常编程中充分利用这一强大工具。