队列
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. }