关于 C++ 中 stack 和 queue 的笔记

简介：
本笔记详细介绍了C++中stack和queue容器的应用与实现，包括它们的功能、用法以及在不同场景下的应用示例。适合初学者快速掌握。 ### C++ 中 Stack (栈) 与 Queue (队列) 的深入解析 #### 一、Stack (栈) 栈是一种线性数据结构，它遵循“后进先出”（Last In First Out, LIFO）的原则。在解决具有递归性质的问题如表达式求值和括号匹配时，栈的应用非常广泛。 ##### 1. 栈的作用 由于其简单易用的特点，在多种算法设计中栈扮演着重要角色，例如单调栈等。此外，它还常用于处理函数调用过程中的参数传递问题。 ##### 2. 栈的定义 在 C++ 中，可以通过 `` 库来定义栈： ```cpp #include using namespace std; int main() { stack s; // 定义一个整型栈 stack d; // 定义一个双精度浮点型栈 stack str; // 定义一个字符串栈 } ``` 对于数组类型的栈定义，虽然 C++ 标准库不直接支持，但可以通过其他方式实现类似的功能： ```cpp vector> s(n); // 创建 n 个整型栈 ``` ##### 3. 栈的常用成员函数 - `empty()`：检查栈是否为空。 - `pop()`：移除栈顶元素。 - `push(T)`：向栈顶添加一个新元素 T。 - `size()`：返回栈中元素的数量。 - `top()`：获取栈顶元素。 示例代码： ```cpp #include #include using namespace std; int main() { stack s; s.push(1); s.push(2); s.push(3); cout << 栈当前元素：1 2 3 << endl; cout << s.size()= << s.size() << endl; // 输出栈中元素数量 cout << s.empty()= << s.empty() << endl; // 检查栈是否为空 cout << s.top()= << s.top() << endl; // 获取栈顶元素 s.pop(); cout << s.pop()后，当前栈元素：1 2 << endl; cout << s.size()= << s.size() << endl; cout << s.empty()= << s.empty() << endl; cout << s.top()= << s.top() << endl; s.pop(); cout << s.pop()后，当前栈元素：1 << endl; cout << s.size()= << s.size() << endl; cout << s.empty()= << s.empty() << endl; cout << s.top()= << s.top() << endl; s.pop(); cout << s.pop()后，当前栈为空 << endl; cout << s.size()= << s.size()<` 库来定义队列： ```cpp #include using namespace std; int main() { queue q; // 定义一个整型队列 queue dq; // 定义一个双精度浮点型队列 queue qs; // 定义一个字符串队列 } ``` ##### 3. 队列的常用成员函数 - `empty()`：检查队列是否为空。 - `pop()`：移除队首元素。 - `push(T)`：向队尾添加一个新元素 T。 - `size()`：返回队列中元素的数量。 - `front()`：获取队首元素。 - `back()`：获取队尾元素。 示例代码： ```cpp #include #include using namespace std; int main() { queue q; q.push(1); q.push(2); q.push(3); cout << 队列当前元素：1 2 3 << endl; cout << q.size()= << q.size()<