首页 > 代码库 > C++ 学习笔记之 STL 队列
C++ 学习笔记之 STL 队列
一. 引言
在算法以及数据结构的实现中，很多地方我们都需要队列（遵循FIFO，先进先出原则）。
为了使用队列，我们可以自己用数组来实现队列，但自己写太麻烦不说，并且还很容易出错。
好在C++的STL（标准模板库）为我们实现了一个强大的队列,它包含在头文件<queue>中。
二. queue
a) 构造函数
下面用例子来展示queue的构造函数
deque<int> deck(3,100); list<int> mylist(2,100); queue<int> first;//默认构造 queue<int,list<int> > second(mylist);//以list为容器构造 queue<int> third(mylist);//以deque为容器构造，其中deque是queue的默认容器queue<int,deque<int> > forth(mylist);//用默认容器构造，deque是queue的默认容器
我们可以使用deque(双端队列容器)或者list（链表容器）来作为queue的基础容器（underlying container，即队列是在基础容器的基础上实现的）,其中deque是默认使用的，如果没有在参数中特殊指定，那么queue就使用deque作为基础容器。
b) 其他成员函数
- empty 测试容器是否为空，为空时返回true
- size 返回容器的大小
- front 返回队列的第一个元素,即最早被压进队列的元素
- back 返回队列的最后一个元素,即最晚被压进队列的元素
- push 把元素添加至队列尾
- pop 弹出队列首元素
- swap(C++11) 交换两个队列
- emplace(C++11) 在容器中直接构造元素，可以参考C++11新特性emplace操作
三. priority_queue（优先队列）
a) 构造函数
1 #include <cstdio> 2 #include <queue> 3 #include <cstdlib> 4 #include <iostream> 5 #include <ctime> 6 #include <functional> 7 using namespace std; 8 struct Node{ 9 int a ; 10 Node(int a):a(a){}11 };12 struct mycomparision{13 bool reverse;14 mycomparision(const bool &revparam=false){15 reverse = revparam;16 }17 bool operator () (const int & lhs, const int &rhs) const {18 if(reverse)return (lhs > rhs);//升序19 else return (lhs < rhs);//降序20 }21 };22 struct cmp{23 bool operator () (const Node a, const Node b) const{24 return a.a < b.a;//小于号代表降序输出25 }26 };27 int main(){28 int myints[] = {10,60,50,20};29 priority_queue<int> zero;30 priority_queue<Node,vector<Node>,cmp> first;//自定义结构体的优先队列，降序输出31 for(int c : myints){32 first.push(Node(c));33 }34 priority_queue<int,vector<int>,mycomparision> second(myints,myints+4,mycomparision(true));//与自定义的仿函数mycomparision结合实现自定义排序功能35 priority_queue<int,vector<int>,mycomparision> third(myints,myints+4,mycomparision());36 priority_queue<int,vector<int>,mycomparision> forth(myints,myints+4);//输出结果同third37 priority_queue<int,vector<int>,less<int>> fifth(myints,myints+4);//结果同third,less使队列优先输出小数，此为默认，即less<int>可以省略38 priority_queue<int,vector<int>,greater<int>> sixth(myints,myints+4);//使用functional库中的仿函数greater使队列优先输出小数39 while(!first.empty()){40 cout << first.top().a << " ";41 first.pop();42 }43 cout << endl;44 while(!second.empty()){45 cout << second.top() << " ";46 second.pop();47 }48 cout << endl;49 while(!third.empty()){50 cout << third.top() << " ";51 third.pop();52 }53 cout << endl;54 while(!forth.empty()){55 cout << forth.top() << " ";56 forth.pop();57 }58 cout << endl;59 while(!fifth.empty()){60 cout << fifth.top() << " ";61 fifth.pop();62 }63 cout << endl;64 while(!sixth.empty()){65 cout << sixth.top() << " ";66 sixth.pop();67 }68 return 0;69 }
优先队列内部维持了堆。利用堆来实现随机的
我们可以使用deque(双端队列容器)或者vector（向量容器）来作为priority_queue的基础容器,其中vector是默认使用的，如果没有在参数中特殊指定，那么queue就使用vector作为基础容器。
这里还要特别注意仿函数的使用。在头文件<functional>提供了一部分仿函数，我们可以利用这些仿函数来实现对基本数据类型的升序降序操作。但对于自定义的结构体类型，我们需要自己额外来实现仿函数来进行排序。有关仿函数的概念可以参考博客：【C++ STL】深入解析神秘的 --- 仿函数
b) 其他成员函数
priority_queue的成员函数与queue大体一致，其中需要注意的是：
- top取代了原来的front，每次取特定排序规则中的具有最值的元素
- 取消了back函数
以上是我自己查资料总结的队列的一些用法，如有不对之处还望各位斧正。
C++ 学习笔记之 STL 队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。