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 }
程序输出：
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 }
程序输出：
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 }
程序输出：
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 }
程序输出：
