【C++笔记】STL详解： stack 和 queue 的使用

前言在 C 的标准模板库 (STL) 中stack栈和 queue队列是非常重要且常用的数据结构。它们都属于“容器适配器”这意味着它们不是从零开始构建的而是封装了其他底层容器如 deque 或 list只提供特定的接口来限制元素的访问方式。一、stack1.1 stack的介绍栈是一种后进先出 (LIFO - Last-In-First-Out) 的数据结构。1. 头文件: #include stack2. 核心特性: 只能在一端栈顶进行插入和删除操作。如下图所示你可以把它想象成一摞盘子你只能把新盘子放在最上面也只能从最上面拿走盘子。1.2 stack的定义方式stack 的类模板声明template class T, class Container dequeT class stack;1. class T解释T 代表这个栈里要装的数据类型。例如当你写 std::stackint 时编译器就把这里的 T 全部替换成 int如果你写 std::stackstd::stringT 就是字符串类型。2.class Container dequeT解释① class Container这指明了栈底层具体是用什么数据结构来存数据的。就像之前说的stack 本身不直接管理内存它是一个“包工头”把具体存取数据的工作外包给了 Container。② dequeT (默认模板参数)如果在定义栈的时候你只提供存什么数据T而没指定怎么存Container编译器就会默认使用 std::dequeT双端队列作为底层的存储结构。3. class stack; (声明类名)解释 告诉编译器“定义一个叫 stack 的类”。代码示例演示1只指定了 T 为 int ,没有指定容器适配器#include iostream #include stack #include vector #include list int main() { // 场景 1最常见的用法 // 只指定了 T 为 int。 // 触发默认参数底层实际上是一个 std::dequeint std::stackint s1; s1.push(1); std::cout s1 栈顶: s1.top() std::endl; return 0; }代码示例演示2指定了 T 为 int ,并指定容器适配器为vector --- 数组栈#include iostream #include stack #include vector #include list int main() { // 场景 2替换底层容器为 vector // 指定 T 为 int并明确指出底层使用 std::vectorint // vector 在内存上是连续的有时候遍历或者缓存命中率更好 std::stackint, std::vectorint s2; s2.push(2); std::cout s2 栈顶: s2.top() std::endl; return 0; }代码示例演示3指定了 T 为 int ,并指定容器适配器为list --- 链式栈#include iostream #include stack #include vector #include list int main() { // 场景 3替换底层容器为 list // 指定 T 为 int底层使用 std::listint (双向链表) // 每次插入都是动态分配内存如果你的数据量变化极大且不想预先分配大块内存这很有用 std::stackint, std::listint s3; s3.push(3); std::cout s3 栈顶: s3.top() std::endl; return 0; }1.3 stack的常用方法1.3.1 push模板参数templateclass T函数原型void push (const T val);函数功能在stack的顶部插入一个新元素代码演示#include iostream // std::cout #include stack // std::stack int main () { std::stackint mystack; for (int i0; i5; i) mystack.push(i); std::cout Popping out elements...; while (!mystack.empty()) { std::cout mystack.top(); mystack.pop(); } std::cout \n; return 0; }打印结果为1.3.2 pop函数原型void pop();函数功能移除栈顶元素代码演示#include iostream // std::cout #include stack // std::stack int main () { std::stackint mystack; for (int i0; i5; i) mystack.push(i); std::cout Popping out elements...; while (!mystack.empty()) { std::cout mystack.top(); mystack.pop(); } std::cout \n; return 0; }打印结果为1.3.3 top模板参数templateclass T函数原型①T top();②const T top() const;函数功能返回stack 中顶部元素的引用代码示例// stack::top #include iostream // std::cout #include stack // std::stack int main () { std::stackint mystack; mystack.push(10); mystack.push(20); mystack.top() - 5; std::cout mystack.top() is now mystack.top() \n; return 0; }打印结果为1.3.4 empty函数原型bool empty() const;函数功能判断容器是否为空代码示例// stack::empty #include iostream // std::cout #include stack // std::stack int main () { std::stackint mystack; int sum (0); for (int i1;i10;i) mystack.push(i); while (!mystack.empty()) { sum mystack.top(); mystack.pop(); } std::cout total: sum \n; return 0; }打印结果1.3.5 size函数原型 size_type size() const;函数功能返回容器中元素的数量。代码示例// stack::size #include iostream // std::cout #include stack // std::stack int main() { std::stackint myints; std::cout 0. size: myints.size() \n; for (int i 0; i 5; i) myints.push(i); std::cout 1. size: myints.size() \n; myints.pop(); std::cout 2. size: myints.size() \n; return 0; }打印结果为1.3.6 swap函数原型void swap (stack x)函数功能交换两个stack的内容代码示例// stack::swap #include iostream // std::cout #include stack // std::stack int main() { std::stackint foo, bar; foo.push(10); foo.push(20); foo.push(30); bar.push(111); bar.push(222); foo.swap(bar); std::cout size of foo: foo.size() \n; std::cout size of bar: bar.size() \n; return 0; }打印结果为二、queue2.1queue的介绍队列是一种先进先出 (FIFO - First-In-First-Out) 的数据结构。1. 头文件: #include queue2. 核心特性: 在一端队尾插入元素在另一端队头移除元素。如下图所示它就像在超市排队结账排在最前面的人先结账离开新来的人排在队伍最后面2.2 queue的定义方式queue的类模板声明template class T, class Container dequeT class queue;1. class T解释T 代表这个栈里要装的数据类型。例如当你写 std::queueint 时编译器就把这里的 T 全部替换成 int如果你写 std::queuestd::stringT 就是字符串类型。2. class Container dequeT解释①class Container指明队列底层用什么容器来存数据。② dequeT如果你不特殊指定编译器默认给你分配 std::dequeT双端队列作为底层容器。温馨提示1. 在 stack 中只要底层容器支持在尾部操作push_back, pop_back, back就可以所以 vector 是可以作为栈的底层容器的。2.队列需要在尾部插入入队并且在头部删除出队。因此如果你想替换 queue 的底层容器这个被替换的容器必须同时支持以下操作push_back()在尾部添加元素pop_front()移除头部元素front()获取头部元素back()获取尾部元素3. 因为标准的 std::vector 不支持 pop_front()在数组头部删除元素会导致后面所有元素大搬家效率极低所以 std::vector 不能作为 queue 的底层容器4.如果你想定制queue的底层容器通常只能选择std::list双向链表或保持默认的std::deque双端队列。2.3 queue的常用方法2.3.1push函数模板templateclass T函数原型void push (const T val);函数功能在队列尾部插入元素代码示例// queue::push/pop #include iostream // std::cin, std::cout #include queue // std::queue int main () { std::queueint myqueue; int myint; std::cout Please enter some integers (enter 0 to end):\n; do { std::cin myint; myqueue.push (myint); } while (myint); std::cout myqueue contains: ; while (!myqueue.empty()) { std::cout myqueue.front(); myqueue.pop(); } std::cout \n; return 0; }打印结果2.3.2 pop函数原型void pop();函数功能移除队头元素代码示例// queue::push/pop #include iostream // std::cin, std::cout #include queue // std::queue int main () { std::queueint myqueue; int myint; std::cout Please enter some integers (enter 0 to end):\n; do { std::cin myint; myqueue.push (myint); } while (myint); std::cout myqueue contains: ; while (!myqueue.empty()) { std::cout myqueue.front(); myqueue.pop(); } std::cout \n; return 0; }打印结果2.3.3front模板参数templateclass T函数原型①T front();②const T front() const;函数功能返回队头元素代码示例// queue::front #include iostream // std::cout #include queue // std::queue int main () { std::queueint myqueue; myqueue.push(77); myqueue.push(16); myqueue.front() - myqueue.back(); // 77-1661 std::cout myqueue.front() is now myqueue.front() \n; return 0; }打印结果2.3.4back模板参数templateclass T函数原型①T back();②const T back() const;函数功能返回队尾元素代码示例// queue::back #include iostream // std::cout #include queue // std::queue int main () { std::queueint myqueue; myqueue.push(12); myqueue.push(75); // this is now the back myqueue.back() - myqueue.front(); std::cout myqueue.back() is now myqueue.back() \n; return 0; }打印结果2.3.5 empty函数原型bool empty() const;函数功能判断容器是否为空代码示例// queue::empty #include iostream // std::cout #include queue // std::queue int main() { std::queueint myqueue; int sum0; for (int i 1; i 10; i) myqueue.push(i); while (!myqueue.empty()) { sum myqueue.front(); myqueue.pop(); } std::cout total: sum \n; return 0; }打印结果2.3.6 size函数原型size_type size() const;函数功能返回队列中元素个数代码示例// queue::size #include iostream // std::cout #include queue // std::queue int main() { std::queueint myints; std::cout 0. size: myints.size() \n; for (int i 0; i 5; i) myints.push(i); std::cout 1. size: myints.size() \n; myints.pop(); std::cout 2. size: myints.size() \n; return 0; }打印结果既然看到这里了不妨关注点赞收藏感谢大家若有问题请指正。