1.FIFO队列
std::queue就是普通意思上的FIFO队列在STL中的模版。
1.1主要的方法有：
(1)T front()：访问队列的对头元素，并不删除对头元素
(2)T back()：访问队列的末尾元素，并不删除末尾元素
(3)void pop()：删除对头元素。
(4)void push(T）：元素入队
1.2代码实例
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 int main()
5 {
6 std::queue<int> myqueue;
7 myqueue.push(11); //入队
8 myqueue.push(22);
9 myqueue.push(33);
10
11 cout<<"队列末尾元素："<<myqueue.back()<<endl;
12 cout<<"队列元素出队顺序如下：";
13 while(!myqueue.empty()) //判空
14 {
15 cout<<myqueue.front()<<" "; //访问队列头元素
16 myqueue.pop(); //队列头元素出对
17 }
18 return 0;
19 }
View Code
程序输出：
2.优先队列
std::priority_queue就是优先级队列在STL中的模版，在优先队列中，优先级高的元素先出队列，内部使用堆实现(大顶堆，同Top K问题)。
2.1 模版原型：priority_queue<T,Sequence,Compare>
T:存放容器的元素类型
Sequence:实现优先级队列的底层容器，默认是vector<T>
Compare:用于实现优先级的比较函数，默认是functional中的less<T>
2.2主要对方法有：
(1)T top()：访问队列的对头元素，并不删除对头元素
(2)void pop()：删除对头元素。
(3)void push(T）：元素入队
2.3使用默认参数的优先队列实例
1 #include <iostream>
2 #include <queue>
3 int main()
4 {
5 std::priority_queue<int> mypq;
6 mypq.push(30); //入队
7 mypq.push(100);
8 mypq.push(25);
9 mypq.push(40);
10 std::cout << "Popping out elements...";
11 while (!mypq.empty())
12 {
13 std::cout << ' ' << mypq.top(); //读取队列头元素
14 mypq.pop(); //对头元素出队列
15 }
16 std::cout << '\n';
17 return 0;
18 }
View Code
程序输出：
2.4使用自定义的比较函数的优先队列实例
标准库默认使用元素类型的<操作符来确定它们之间的优先级关系，大的优先级高，优先输出。我们只要重写<操作符就可以啦（可以像C语言的qsort()一样，可以写比较复杂的比较函数）。
下面的实例中，重写<操作符，使得数字小的数，优先级大。
1 #include <iostream>
2 #include <queue>
3 #include <vector>
4 #include <functional>
5 using namespace std;
6 struct Node
7 {
8 int f;
9 bool operator<(const Node& node)const
10 {
11 return f<node.f? false :true ; //小的数字，可以让它不小
12 }
13 };
14 class cmp
15 {
16 public:
17 bool operator()( const Node & n1, const Node & n2) const
18 {
19 return n1<n2; //Node类已经重写了<运算符
20 }
21 };
22 int main()
23 {
24 priority_queue< Node,vector<Node>,cmp > q;
25 Node n1,n2,n3,n4;
26
27 n1.f = 5; n2.f = 4;
28 n3.f = 2; n4.f = 10;
29
30 q.push(n1); q.push(n2);
31 q.push(n3); q.push(n4);
32 while(!q.empty())
33 {
34 cout<< q.top().f<<" ";
35 q.pop();
36 }
37 }
View Code
程序输出：
3.双端队列
双端队列就是一个两端都是结尾的队列。队列的每一端都可以插入数据项和移除数据项。deque是STL中双端队列模版。
3.1主要对方法有：
(1)void pop_front(）：从队列头部删除元素
(2)void pop_back(）：从队列删除元素
(3)void push_front(T）：从队列头部插入元素
(4)void push_back(T）：从队列尾部插入元素
(5)T front(）：读取队列头部元素
(6)T back(T）：读取队列尾部元素
3.2代码实例
1 #include <iostream>
2 #include <deque>
3
4 int main ()
5 {
6 std::deque<int> mydeque;
7 mydeque.push_back (1); //队列尾部插入
8 mydeque.push_back (2);
9 mydeque.push_back (3);
10 mydeque.push_front(4); //队列头部插入
11
12 std::cout << "Popping out the elements in mydeque:";
13 while (!mydeque.empty())
14 {
15 std::cout << ' ' << mydeque.front();
16 mydeque.pop_front(); //删除队列头部
17 }
18 std::cout << "\nThe final size of mydeque is " << int(mydeque.size()) << '\n';
19 return 0;
20 }
View Code
程序输出：