前言:
C++ 标准模板库(STL)为我们提供了多种容器,其中 stack
(栈)和 queue
(队列)是非常常用的两种容器。
根据之前C语言实现的栈和队列,(如有遗忘,请回去看看【数据结构】— 栈和队列-CSDN博客)我们知道一些栈和队列的逻辑,现在就来学习C++STL中的栈和队列。
一、栈
首先,STL中的栈是基于容器适配器实现的,默认容器是deque。
使用栈需要包含头文件:
#include<stack>
1.1 栈的基本操作
先看一下,栈提供的接口函数
常用方法:
push()
: 将元素val
压入栈顶。pop()
: 移除栈顶元素。top()
: 返回栈顶元素(但不移除)。empty()
: 判断栈是否为空。size()
: 返回栈的元素数量。
1.2 栈的使用
现在简单使用一下stack:
void test_stack() {//创建一个栈——存储整形stack<int> s; //入栈s.push(1);s.push(2);s.push(3);//栈中元素cout << "元素个数: " << s.size() << endl;//栈顶元素cout << "栈顶元素: " << s.top() << endl;//出栈s.pop();//依次输出栈中的数据while (!s.empty()) {cout << s.top() << " ";s.pop();}cout << endl;return 0;
}
输出结果:
元素个数: 3
栈顶元素: 3
2 1
1.3 应用实例:点击消除
栈可以用来解决括号匹配这一类的问题。
括号匹配之前已经做过了,这里来用栈做这样的一道题:点击消除_牛客题霸_牛客网
题目描述:
这题思路比较简单,就是遍历字符串时,不断入栈,出栈(字符串中字符与栈顶元素相等);最后输出即可。
需要注意的是:这里使用数组来模拟栈,方便输出
当然也可以使用栈,不过输出时顺序是反的,需要进行处理。
#include <iostream>
using namespace std;int main() {string str;cin>>str;string ret;for(auto ch: str){if(ret.size()==0||ret[ret.size()-1]!=ch){ret.push_back(ch);}else {ret.pop_back();}}if(ret.empty()){cout<<'0';return 0;}cout<<ret;return 0;
}
二、队列
2.1 队列的基本操作
STL
中的队列(queue
)也是一种容器适配器,默认底层容器也是 deque
。
使用栈需要包含头文件:
#include<queue>
常用方法:
push()
: 将元素val
插入队尾。pop()
: 移除队头元素。front()
: 返回队头元素(不移除)。back()
: 返回队尾元素(不移除)。empty()
: 判断队列是否为空。size()
: 返回队列的元素数量。
2.2 队列的使用
简单使用一下队列:
void test_queue()
{//创建一个队列——存储整型queue<int> q;//入队列q.push(10);q.push(20);q.push(30);cout << "数据个数: " << q.size() << endl;cout << "队头元素: " << q.front() << endl;cout << "队尾元素: " << q.back() << endl;//出队列q.pop();cout << "队列中数据: ";while (!q.empty()) {cout << q.front() << " ";q.pop();}cout << endl;
}
输出结果:
数据个数: 3
队头元素: 10
队尾元素: 30
队列中数据: 20 30
2.3 应用实例:简单的任务调度
队列可以用于实现简单的任务调度。假设有一系列任务需要按顺序执行,我们可以使用队列来管理任务的执行顺序。
#include <iostream>
#include <queue>
#include <string>
using namespace std;int main() {queue<string> tasks;// 添加任务tasks.push("任务1: 下载文件");tasks.push("任务2: 解压文件");tasks.push("任务3: 处理数据");// 模拟任务调度while (!tasks.empty()) {cout << "正在执行 -> " << tasks.front() << endl;tasks.pop();}return 0;
}
输出结果:
rust复制代码正在执行 -> 任务1: 下载文件
正在执行 -> 任务2: 解压文件
正在执行 -> 任务3: 处理数据
三、双端队列(deque
)的栈和队列操作
deque
(双端队列)既可以当作栈,也可以当作队列使用。我们可以在双端队列的两端进行插入和删除操作,从而更灵活地实现栈和队列的功能。
对于双端队列,简单来说,就是可以像vector那样随机访问,也可以像链表那样随机位置插入;但是,效率很低,(个人感觉,就是为了给stack
和queue
作默认容器适配器来用的。
这里就不过多描述双端队列了,感兴趣可以去看一下源码学习学习。
总结
eque`(双端队列)既可以当作栈,也可以当作队列使用。我们可以在双端队列的两端进行插入和删除操作,从而更灵活地实现栈和队列的功能。
对于双端队列,简单来说,就是可以像vector那样随机访问,也可以像链表那样随机位置插入;但是,效率很低,(个人感觉,就是为了给stack
和queue
作默认容器适配器来用的。
这里就不过多描述双端队列了,感兴趣可以去看一下源码学习学习。
总结
在 C++ 中,stack
和 queue
是非常有用的数据结构,分别实现了后进先出和先进先出的操作模式。通过合理地使用栈和队列,我们可以简化很多问题的解决过程,比如括号匹配和任务调度。同时,双端队列(deque
)提供了更为灵活的插入和删除操作,可以根据需求同时作为栈和队列使用。
我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws