队列
1.队列的性质
（1）队列是一种容器适配器，容器适配器即将特定容器类封装作为其底层容器类，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端删除元素。
（2） 队列作为容器适配器实现，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
（3）底层容器可以是标准容器类模板之一，如可用vector、list可以作为底层容器类，也可以是其他专门设计的容器类，。该底层容器应至少支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
（4）标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
2.队列类
（1）队列的构造
构造一个队列：
explicit queue (const container_type& ctnr = container_type());//构造一个队列
构造一个队列q1：
queue<int> q1;//构造一个空队列q1
（2）empty( )
判断队列是否为空
bool empty() const;
判断队列q1是否为空：
cout << q1.empty() << endl;
（3）push( )
向队尾插入一个元素
void push (const value_type& val);
向队尾插入4个元素，值分别为1，2，3，4
1. q1.push(1); 2. q1.push(2); 3. q1.push(3); 4. q1.push(4);
（4）pop( )
从队头删除一个元素
void pop();
删除队头元素
（5） size( )
求队列中元素的个数
size_type size() const;
求q1中元素个数：
cout << q1.size() << endl;
（6）front( )
返回队头元素
1. value_type& front(); 2. const value_type& front() const;
返回q1队头元素：
cout << q1.front() << endl;
（7）back( )
返回队尾元素
1. value_type& back(); 2. const value_type& back() const;
返回q1队尾元素：
cout << q1.back() << endl;
2.队列模拟实现
queue类的定义：
template <class T, class Container = deque<T> > class queue;
其中deque作为双端队列，queue如果没有指定底层容器为list等，那么会默认底层容器为deque。队列作为容器适配器， 不像string、vector、list等是完整的容器类，队列不是完整的容器类，而是提供特定接口的类，相当于在完整容器外面包装了一层，比如使用deque或list实现队列，就可以借助deque或list的操作来实现队列的操作。
队列的构造函数、拷贝构造函数、赋值运算符重载函数、析构函数不需要写，会调用deque自己的默认构造函数、拷贝构造函数、赋值运算符重载函数、析构函数。
017-queue.h
1. #pragma once 2. #include<iostream> 3. #include<deque> 4. using namespace std; 5. 6. namespace delia 7. { 8. template <class T, class Container = deque<T>> 9. class queue 10. { 11. public: 12. 13. //向队尾插入一个元素 14. void push(const T& x) 15. { 16. _con.push_back(x); 17. } 18. 19. //从队头删除一个元素 20. void pop() 21. { 22. _con.pop_front(); 23. } 24. 25. //返回队头元素 26. T front() 27. { 28. return _con.front(); 29. } 30. 31. //返回队尾元素 32. T back() 33. { 34. return _con.back(); 35. } 36. 37. //判断队列是否尾空 38. bool empty() 39. { 40. return _con.empty(); 41. } 42. 43. //求队列中元素的个数 44. size_t size() 45. { 46. return _con.size(); 47. } 48. 49. private: 50. Container _con; 51. }; 52. 53. void test_queue() 54. { 55. queue<int> q1; 56. q1.push(1); 57. q1.push(2); 58. q1.push(3); 59. q1.push(4); 60. 61. q1.pop();//删除队头元素1 62. 63. cout << q1.front() << endl;//打印q1队头元素 64. cout << q1.back() << endl;//打印q1队尾元素 65. cout << q1.empty() << endl;//判断q1是否为空 66. cout << q1.size() << endl;//求q1元素个数 67. } 68. }
017-test.cpp
1. #include "017-queue.h" 2. 3. int main() 4. { 5. delia::test_queue(); 6. return 0; 7. }
假如底层不想用deque实现，但是不能用vector实现，因为队列的删除操作就是删除vector顺序表第一个元素，那么后面所有的元素都需要向前挪，效率低。可以用list实现，队列的删除操作就是修改头节点的_next指向和第2个节点的_prev指向，效率高。因此只需要修改第3行和第8行，将deque改为list即可：
1. #pragma once 2. #include<iostream> 3. #include<list> 4. using namespace std; 5. 6. namespace delia 7. { 8. template <class T, class Container = list<T>> 9. class queue 10. { 11. public: 12. 13. //向队尾插入一个元素 14. void push(const T& x) 15. { 16. _con.push_back(x); 17. } 18. 19. //从队头删除一个元素 20. void pop() 21. { 22. _con.pop_front(); 23. } 24. 25. //返回队头元素 26. T front() 27. { 28. return _con.front(); 29. } 30. 31. //返回队尾元素 32. T back() 33. { 34. return _con.back(); 35. } 36. 37. //判断队列是否尾空 38. bool empty() 39. { 40. return _con.empty(); 41. } 42. 43. //求队列中元素的个数 44. size_t size() 45. { 46. return _con.size(); 47. } 48. 49. private: 50. Container _con; 51. }; 52. 53. void test_queue() 54. { 55. queue<int> q1; 56. q1.push(1); 57. q1.push(2); 58. q1.push(3); 59. q1.push(4); 60. 61. q1.pop();//删除队头元素1 62. 63. cout << q1.front() << endl;//打印q1队头元素 64. cout << q1.back() << endl;//打印q1队尾元素 65. cout << q1.empty() << endl;//判断q1是否为空 66. cout << q1.size() << endl;//求q1元素个数 67. } 68. }
