以下将结合实例简单介绍(STL queue)
与(priority_queue)
的使用:
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。——百度百科
C++提供了符合这一性质的容器,可供直接定义使用。但使用之前,需包含#include<queue>
头文件,为了防止疏漏,不妨直接放上下面那段代码():
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<set>
#include<utility>
#include<stack>
#include<deque>
using namespace std;
队列的定义方式:
queue<string> queue_1; //直接构造
queue<string> queue_2 {queue_1}; //使用拷贝构造
具体使用(采用一个实例来说明):
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<set>
#include<utility>
#include<stack>
#include<deque>
using namespace std;
int main()
{
queue<int> queue_1;
for(int i=0; i<=9; i++)
queue_1.push(i); //在尾部添加元素
cout<< "first_item="<< queue_1.front() <<endl; //首位元素
cout<< "last_item="<< queue_1.back() <<endl; //末位元素
cout<< "max_size="<< queue_1.size() <<endl; //队列长度
queue_1.pop(); //从队首弹出一个元素
queue_1.emplace(10,2); //在尾部生成对象,这里指插入2个10
queue<int> queue_2 {queue_1}; //拷贝定义
queue<int> queue_3;
queue_1.swap(queue_3); //交换两个队列的内容,类型必须相同,大小可以不同
//最后我们输出看看现在队列内的元素情况
cout<<"queue_2:"<<endl;
while(!queue_2.empty()) //当不为空,返回true
{
cout<<queue_2.front()<<" ";
queue_2.pop();
}
cout<<"queue_3:"<<endl;
while(!queue_3.empty()) //当不为空,返回true
{
cout<<queue_3.front()<<" ";
queue_3.pop();
}
return 0;
}
我们得到的输出为(理论上):
first_item=0
last_item=9
max_size=10
queue_2:
1 2 3 4 5 6 7 8 9 10 10
queue_3:
1 2 3 4 5 6 7 8 9 10 10
为什么会得到这样的输出?
首先,使用push
函数向队列queue_1
中添加元素0-9,之后,使用pop
函数弹出队首元素0,又使用emplace
函数添加2个10进入队列,此时队列中元素依次为[1,2,3,4,5,6,7,8,9,10,10]
。由于queue_2采用拷贝定义,故其内元素与queue_1相同;使用swap
函数实现队列的交换,使得queue_3内元素与之前 queue_1相同,queue_1变为空队列。
注意:
emplace
函数、swap
函数与拷贝定义对编译器的要求较高,可以尽量避免使用这些函数。
接下来简要介绍优先队列priority_queue
的用法:
其本质是一个堆,同样需包含头文件#include <queue>
。定义时,默认为大顶堆,小顶堆需要单独说明:
//各部分含义:priority_queue<Type, Container, Functional>
priority_queue <int,vector<int>,greater<int> > q; //小顶堆
priority_queue <int,vector<int>,less<int> >q; //大顶堆
//大顶堆也可直接这样定义:
priority_queue<int> q;
若其内元素为
pair<int, int>
类型,则先比较第一个元素,后比较第二个元素
其使用方法与上述队列基本操作相同,在此不赘述。
参考网址: