STL容器之stack：栈结构及典型应用举例

# 1. 简介

### 1.1 什么是STL容器

STL（Standard Template Library）即标准模板库，是C++中提供的一套标准模板类的集合，包括一些常用的数据结构和算法。STL容器是STL库中用来存储数据的一种封装数据结构，提供了各种不同类型的容器以满足不同的需求。

### 1.2 stack简介

在STL容器中，stack（栈）是一种后进先出（LIFO）的数据结构，只允许从容器的一端（顶端）进行插入（push）和删除（pop）操作。具有很高的效率，适用于很多实际应用场景。

### 1.3 栈结构的特点与用途

栈结构具有以下特点：先进入栈的元素将是最后删除的，后进入栈的元素将会最先删除。栈常用于需要后进先出的场景，如递归函数调用、表达式求值、以及需要后进先出的数据操作等。

# 2. stack的基本操作

栈（stack）是一种具有特定限制的线性数据结构，具有“先进后出”（FILO，First In Last Out）的特性。在STL中，stack是一种容器适配器，它基于其他底层容器（默认为deque）实现。

### push和pop操作

- **push操作**：将元素压入栈顶。在C++中，可以使用`push()`方法实现。

   #include <iostream>
   #include <stack>
   using namespace std;
   int main() {
     stack<int> myStack;
     myStack.push(5);
     myStack.push(10);
     return 0;
   }

- **pop操作**：将栈顶元素弹出。在C++中，可以使用`pop()`方法实现。

   #include <iostream>
   #include <stack>
   using namespace std;
   int main() {
     stack<int> myStack;
     myStack.push(5);
     myStack.push(10);
     myStack.pop();
     return 0;
   }

### top操作

- **top操作**：获取栈顶元素的值，不对栈进行修改。在C++中，可以使用`top()`方法来实现。

   #include <iostream>
   #include <stack>
   using namespace std;
   int main() {
     stack<int> myStack;
     myStack.push(5);
     myStack.push(10);
     cout << "Top element: " << myStack.top() << endl;
     return 0;
   }

### empty和size操作

- **empty操作**：判断栈是否为空，为空则返回true，否则返回false。在C++中，可以使用`empty()`方法实现。

   #include <iostream>
   #include <stack>
   using namespace std;
   int main() {
     stack<int> myStack;
     if (myStack.empty()) {
       cout << "Stack is empty." << endl;
     }
     return 0;
   }

- **size操作**：返回栈中元素的个数。在C++中，可以使用`size()`方法实现。

   #include <iostream>
   #include <stack>
   using namespace std;
   int main() {
     stack<int> myStack;
     myStack.push(5);
     myStack.push(10);
     cout << "Size of stack: " << myStack.size() << endl;
     return 0;
   }

### 栈的内部实现机制

在STL中，默认情况下，栈是由deque容器实现的。deque是一个双端队列，具有动态扩展的特性，因此很适合用来实现栈这种数据结构。当然，也可以通过指定其他容器（如vector）作为底层容器来实现不同的stack。

以上是stack的基本操作，包括压栈、弹栈、取栈顶元素、判断栈空、获取栈大小等操作。接下来，我们将介绍stack在实际应用中的典型场景。

# 3. stack的典型应用举例

栈是一种具有后进先出（Last In First Out, LIFO）特性的数据结构，因此在计算机科学和软件开发中有