STL源码之queue深入学习

queue是一种先进先出(First In First Out，FIFO)的数据结构，它有两个出口。queue允许新增元素、移除元素、从最底端加入元素、取得最顶端元素。

1. queue概述
   （1）除了最底端可以加入、最顶端可以取出外，没有任何其他方法可以存取queue的其他元素。换言之，queue不允许有遍历行为。
   （2）将元素推入queue的操作称为push，将元素推出queue的操作称为pop
   
2. queue定义源码
   （1）deque是双向开头的数据结构，若以deque为底部结构并封闭其底端的出口和前端的入口，便形成了一个queue。
   （2）SGI STL以deque作为缺省情况下的queue底部结构。
   （3）由于queue是以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”的性质者，称为adapter。
   （4）因此，STL queue往往不被归类为container，而被归类为container adapter。
   
   C++

   template <class T, class Sequence = deque<T>> class queue { //以下的__STL_NULL_TMPL_ARGS会展开为<> friend bool operator== __STL_NULL_TMPL_ARGS(const queue& x, const queue& y); friend bool operator< __STL_NULL_TMPL_ARGS(cosnt queue& x, const queue& y); public: typedef typename Sequence::value_type value_type; typedef typename Sequence::size_type size_type; typedef typename Sequence::reference reference; typedef typename Sequence::const_reference const_reference; protected: Sequence c; //底层容器 public: //以下完全利用Sequence c 的操作，完成queue的操作 bool empty() cosnt { return c.empty(); } size_type size() const { return c.size(); } reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } //deuqe是两头可进出，queue是末端进，前端出 void push(const value_type& x) { c.push_back(x); } void pop() { c.pop_front(); } }; template <class T, class Sequence> bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) { return x.c == y.c; } template <class T, class Sequence> bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) { return x.c < y.c; }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

   template <class T, class Sequence = deque<T>> class queue { //以下的__STL_NULL_TMPL_ARGS会展开为<> friend bool operator== __STL_NULL_TMPL_ARGS(const queue& x, const queue& y); friend bool operator< __STL_NULL_TMPL_ARGS(cosnt queue& x, const queue& y); public: typedef typename Sequence::value_type value_type; typedef typename Sequence::size_type size_type; typedef typename Sequence::reference reference; typedef typename Sequence::const_reference const_reference; protected: Sequence c; //底层容器 public: //以下完全利用Sequence c 的操作，完成queue的操作 bool empty() cosnt { return c.empty(); } size_type size() const { return c.size(); } reference front() { return c.front(); } const_reference front() const { return c.front(); } reference back() { return c.back(); } const_reference back() const { return c.back(); } //deuqe是两头可进出，queue是末端进，前端出 void push(const value_type& x) { c.push_back(x); } void pop() { c.pop_front(); } };   template <class T, class Sequence> bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) { return x.c == y.c; } template <class T, class Sequence> bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) { return x.c < y.c; }

3. queue跟stack一样没有迭代器
   queue所有元素的进出都必须符合“先进先出”的条件，只有queue顶端的元素，才有机会被外界取出。queue不提供遍历功能，也不提供迭代器。
4. 也可以用list作为queue的底层容器
   （1）除了deque之外，list也是双向开口的数据结构。
   （2）上述queue源代码中使用的底层容器的函数有empty, size, front, back, push_front, push_back, pop_front, pop_back等等，list都具备。
   （3）因此若以list为底部结构并封闭其某些接口，一样能够轻易形成一个queue。
5. 实例(以list为底层容器)
   
   C++

   #include <iostream> #include <queue> #include <list> #include <algorithm> using namespace std; int main() { queue<int, list<int>>iqueue; iqueue.push(1); iqueue.push(3); iqueue.push(5); iqueue.push(7); cout << iqueue.size() << endl; //4 cout << iqueue.front() << endl; //1 iqueue.pop(); cout << iqueue.front() << endl; //3 iqueue.pop(); cout << iqueue.front() << endl; //5 iqueue.pop(); cout << iqueue.front() << endl; //7 cout << iqueue.size() << endl; //1 }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   #include <iostream> #include <queue> #include <list> #include <algorithm> using namespace std;   int main() { queue<int, list<int>>iqueue; iqueue.push(1); iqueue.push(3); iqueue.push(5); iqueue.push(7); cout << iqueue.size() << endl; //4 cout << iqueue.front() << endl; //1 iqueue.pop(); cout << iqueue.front() << endl; //3 iqueue.pop(); cout << iqueue.front() << endl; //5 iqueue.pop(); cout << iqueue.front() << endl; //7 cout << iqueue.size() << endl; //1 }