• C++ 学习（18）STL - deque容器、stack容器、queue容器

    1、deque容器

    deque容器为双端数组，可以对头端和尾端进行插入删除操作。

    deque与vector区别：

    从两者内部实现比较：

    1. vector对于头部的插入删除效率低，数据量越大，效率越低；deque相对而言，对头部插入删除速度会比vector快
    2. vector访问元素时的速度比deque快

    简单理解：vector读数据快，deque写数据快。

    deque内部工作原理：

    deque内部有个中控器，维护每段缓冲区，缓冲区中存放真实数据；中控器维护的是每个缓冲区的地址，使得使用deque时像一年连续的内存空间。如下图所示：

    1.1、deque构造函数

    函数原型：

    • deque deqT;        //默认构造形式
    • deque(beg, end);      //构造函数将[beg, end)区间中的元素拷贝给当前deque
    • deque(n, elem);        //构造函数将n个elem拷贝给当前deque
    • deque(const deque& deq); //拷贝构造函数
    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. void print(const deque<int>& d)
    6. {
    7. 	for (deque<int>::const_iterator  it = d.begin(); it < d.end(); it++)
    8. 	{
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. int main()
    15. {
    16. 	// STL - deque - 构造函数
    17. 	/*函数原型：
    18. 		1、deque deqT;       	//默认构造形式
    19. 		2、deque(beg, end);     	//构造函数将[beg, end)区间中的元素拷贝给当前deque
    20. 		3、deque(n, elem);       	//构造函数将n个elem拷贝给当前deque
    21. 		4、deque(const deque& deq); //拷贝构造函数
    22. 	*/
    23. 	
    24. 	//1、deque deqT;
    25. 	deque<int> d1;
    26. 	for (int i = 0; i < 5; i++)
    27. 	{
    28. 		d1.push_back(i + 1);
    29. 	}
    30. 	print(d1);
    31.  
    32. 	//2、deque(beg, end);
    33. 	deque<int> d2(d1.begin(), d1.end());
    34. 	print(d2);
    35.  
    36. 	//3、deque(n, elem);
    37. 	deque<int> d3(5, 8);
    38. 	print(d3);
    39.  
    40. 	//4、deque(const deque& deq); 
    41. 	deque<int> d4(d1);
    42. 	print(d4);
    43.  
    44. 	system("pause");
    45.  
    46. 	return 0;
    47. }

    输出结果

    1 2 3 4 5
    1 2 3 4 5
    8 8 8 8 8
    1 2 3 4 5 

    1.2、deque赋值操作

    函数原型：

    • deque& operator=(const deque& deq);  //重载运算符=
    • assign(beg, end);   //将[beg, end)区间中的数据拷贝给当前deque
    • assign(n, elem);     //将n个elem拷贝赋值给本身
    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. void print(const deque<int>& d)
    6. {
    7. 	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
    8. 	{
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. int main()
    15. {
    16. 	// STL - deque - 赋值操作
    17. 	/*函数原型：
    18. 		1、deque& operator=(const deque& deq);  //重载运算符=
    19. 		2、assign(beg, end);   //将[beg, end)区间中的数据拷贝给当前deque
    20. 		3、assign(n, elem);     //将n个elem拷贝赋值给本身
    21. 	*/
    22.  
    23. 	deque<int> d;
    24. 	for (int i = 0; i < 5; i++)
    25. 	{
    26. 		d.push_front(i + 1);
    27. 	}
    28. 	print(d);
    29.  
    30. 	//1、deque& operator=(const deque& deq);
    31. 	deque<int> d1;
    32. 	d1 = d;
    33. 	print(d1);
    34.  
    35. 	//2、assign(beg, end); 
    36. 	deque<int>::iterator it = d1.begin();
    37. 	it++;
    38. 	deque<int> d2;
    39. 	d2.assign(it, d1.end());
    40. 	print(d2);
    41.  
    42. 	//3、assign(n, elem);
    43. 	deque<int> d3;
    44. 	d3.assign(5, 8);
    45. 	print(d3);
    46.  
    47. 	system("pause");
    48.  
    49. 	return 0;
    50. }

    输出结果

    5 4 3 2 1

    5 4 3 2 1
    4 3 2 1
    8 8 8 8 8

    1.3、deque大小操作

    函数原型：

    • deque.empty();          //判断容器是否为空
    • deque.size();             //返回容器中元素个数
    • deque.resize(num);  //重新指定容器的长度为num，若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
    • deque.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. void print(const deque<int>& d)
    6. {
    7. 	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
    8. 	{
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. int main()
    15. {
    16. 	// STL - deque - 大小操作
    17. 	/*函数原型：
    18. 		1、deque.empty();         	//判断容器是否为空
    19. 		2、deque.size();            //返回容器中元素个数
    20. 		3、deque.resize(num); 		//重新指定容器的长度为num，若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
    21. 		4、deque.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
    22. 	*/
    23.  
    24. 	deque<int> d;
    25. 	//1、deque.empty();  
    26. 	cout << "1、容器是否为空：" << (d.empty() ? "是" : "否") << endl;
    27.  
    28. 	for (int i = 0; i < 5; i++)
    29. 	{
    30. 		d.push_front(i + 1);
    31. 	}
    32. 	cout << "1、容器初始化元素：";
    33. 	print(d);
    34. 	cout << "1、容器是否为空：" << (d.empty() ? "是" : "否") << endl;
    35.  
    36. 	//2、deque.size();
    37. 	cout << "2、容器中元素个数：" << d.size() << endl;
    38.  
    39. 	//3、deque.resize(num);
    40. 	d.resize(8);
    41. 	cout << "3、容器长度变长后大小：" << d.size() << "，元素：";
    42. 	print(d);
    43.  
    44. 	d.resize(3);
    45. 	cout << "3、容器长度变短后大小：" << d.size() << "，元素：";
    46. 	print(d);
    47.  
    48. 	//4、deque.resize(num, elem);
    49. 	d.resize(9, 10);
    50. 	cout << "4、容器长度变长后大小：" << d.size() << "，元素：";
    51. 	print(d);
    52.  
    53. 	d.resize(5, 6);
    54. 	cout << "4、容器长度变短后大小：" << d.size() << "，元素：";
    55. 	print(d);
    56.  
    57. 	system("pause");
    58.  
    59. 	return 0;
    60. }

    输出结果

    1、容器是否为空：是
    1、容器初始化元素：5 4 3 2 1
    1、容器是否为空：否
    2、容器中元素个数：5
    3、容器长度变长后大小：8，元素：5 4 3 2 1 0 0 0
    3、容器长度变短后大小：3，元素：5 4 3
    4、容器长度变长后大小：9，元素：5 4 3 10 10 10 10 10 10
    4、容器长度变短后大小：5，元素：5 4 3 10 10

    1.4、deque插入和删除

    函数原型：

    两端操作：

    • push_back(elem);    //在容器尾部添加一个数据
    • push_front(elem);    //在容器头部插入一个数据
    • pop_back();             //删除容器最后一个数据
    • pop_front();             //删除容器第一个数据

    指定位置操作：

    • insert(pos, elem);        //在pos位置插入一个elem元素的拷贝，返回新数据的位置
    • insert(pos, n, elem);    //在pos位置插入n个elem数据，无返回值
    • insert(pos, beg, end); //在pos位置插入[beg, end)区间的数据，无返回值
    • erase(pos);                //删除pos位置的数据，返回下一个数据的位置
    • erase(beg, end);        //删除[beg, end)区间的数据，返回下一个数据的位置
    • clear();                        //清空容器中所有数据
    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. void print(const deque<int>& d)
    6. {
    7. 	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
    8. 	{
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. int main()
    15. {
    16. 	// STL - deque - 插入和删除
    17. 	/*函数原型：
    18. 	两端操作：
    19. 		1、push_back(elem);     //在容器尾部添加一个数据
    20. 		2、push_front(elem);    //在容器头部插入一个数据
    21. 		3、pop_back();          //删除容器最后一个数据
    22. 		4、pop_front();         //删除容器第一个数据
    24. 	指定位置操作：
    25. 		5、insert(pos, elem);     //在pos位置插入一个elem元素的拷贝，返回新数据的位置
    26. 		6、insert(pos, n, elem);  //在pos位置插入n个elem数据，无返回值
    27. 		7、insert(pos, beg, end); //在pos位置插入[beg, end)区间的数据，无返回值
    28. 		8、erase(pos);            //删除pos位置的数据，返回下一个数据的位置
    29. 		9、erase(beg, end);       //删除[beg, end)区间的数据，返回下一个数据的位置
    30. 		10、clear();              //清空容器中所有数据
    31. 	*/
    32.  
    33. 	deque<int> d;
    34. 	//1、push_back(elem);
    35. 	for (int i = 0; i < 3; i++)
    36. 	{
    37. 		d.push_back(i + 1);
    38. 	}
    39.  
    40. 	cout << "1、尾部添加3个数据，当前元素：";
    41. 	print(d);
    42.  
    43. 	//2、push_front(elem); 
    44. 	for (int i = 10; i < 15; i++)
    45. 	{
    46. 		d.push_front(i + 1);
    47. 	}
    48.  
    49. 	cout << "2、头部插入5个数据，当前元素：";
    50. 	print(d);
    51.  
    52. 	//3、pop_back(); 
    53. 	d.pop_back();
    54. 	cout << "3、尾部删除1个数据，当前元素：";
    55. 	print(d);
    56.  
    57. 	//4、pop_front(); 
    58. 	d.pop_front();
    59. 	cout << "4、头部删除1个数据，当前元素：";
    60. 	print(d);
    61.  
    62. 	//5、insert(pos, elem);  
    63. 	deque<int>::iterator pos = d.insert(d.begin(), 99);
    64. 	cout << "5、在第1位置添加数据，当前元素：";
    65. 	print(d);
    66.  
    67. 	//6、insert(pos, n, elem);
    68. 	d.insert(pos, 3, 88);
    69. 	cout << "6、在第1位置添加数据，当前元素：";
    70. 	print(d);
    71.  
    72. 	//7、insert(pos, beg, end)
    73. 	deque<int> d2;
    74. 	d2.push_back(1);
    75. 	d2.push_back(2);
    76.  
    77. 	pos = d.insert(d.begin(), d2.begin(), d2.end());
    78. 	cout << "7、在第1位置添加数据，当前元素：";
    79. 	print(d);
    80.  
    81. 	//8、erase(pos); 
    82. 	d.erase(pos);
    83. 	cout << "8、删除第1位置数据，当前元素：";
    84. 	print(d);
    85.  
    86. 	//9、erase(beg, end); 
    87. 	pos = d.begin();
    88. 	pos++;
    89. 	d.erase(pos, d.end());
    90. 	cout << "9、删除第2位置至尾区间数据，当前元素：";
    91. 	print(d);
    92.  
    93. 	//10、clear();  
    94. 	d.clear();
    95. 	cout << "10、清空数据，容器大小：" << d.size() << "，当前元素：";
    96. 	print(d);
    97.  
    98. 	system("pause");
    99.  
    100. 	return 0;
    101. }

    输出结果

    1、尾部添加3个数据，当前元素：1 2 3
    2、头部插入5个数据，当前元素：15 14 13 12 11 1 2 3
    3、尾部删除1个数据，当前元素：15 14 13 12 11 1 2
    4、头部删除1个数据，当前元素：14 13 12 11 1 2
    5、在第1位置添加数据，当前元素：99 14 13 12 11 1 2
    6、在第1位置添加数据，当前元素：88 88 88 99 14 13 12 11 1 2
    7、在第1位置添加数据，当前元素：1 2 88 88 88 99 14 13 12 11 1 2
    8、删除第1位置数据，当前元素：2 88 88 88 99 14 13 12 11 1 2
    9、删除第2位置至尾区间数据，当前元素：2
    10、清空数据，容器大小：0，当前元素：

    1.5、deque数据读取

    函数原型：

    • at(int idx);   //返回索引idx所指的数据
    • operator[];  //返回索引idx所指的数据
    • front();       //返回容器中第一个数据元素
    • back();      //返回容器中最后一个数据元素
    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. void print(const deque<int>& d)
    6. {
    7. 	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
    8. 	{
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. int main()
    15. {
    16. 	// STL - deque - 数据读取
    17. 	/*函数原型：
    18. 		1、at(int idx);   //返回索引idx所指的数据
    19. 		2、operator[];    //返回索引idx所指的数据
    20. 		3、front();       //返回容器中第一个数据元素
    21. 		4、back();        //返回容器中最后一个数据元素
    22. 	*/
    23.  
    24. 	deque<int> d;
    25. 	for (int i = 0; i < 5; i++)
    26. 	{
    27. 		d.push_back(i + 1);
    28. 	}
    29. 	cout << "容器中的元素：";
    30. 	print(d);
    31.  
    32. 	//1、at(int idx);
    33. 	cout << "1、读取第3个元素：" << d.at(2) << endl;
    34.  
    35. 	//2、operator[];
    36. 	cout << "2、读取第2个元素：" << d[1] << endl;
    37.  
    38. 	//3、front(); 
    39. 	cout << "3、读取第一个元素：" << d.front() << endl;
    40.  
    41. 	//4、back();  
    42. 	cout << "4、读取最后一个元素：" << d.back() << endl;
    43.  
    44. 	system("pause");
    45.  
    46. 	return 0;
    47. }

    输出结果

    容器中的元素：1 2 3 4 5
    1、读取第3个元素：3
    2、读取第2个元素：2
    3、读取第一个元素：1
    4、读取最后一个元素：5

    1.6、deque排序

    算法：

    • sort(iterator beg, iterator end);  //对beg和end区间内元素进行排序

    默认升序排序，对于支持随机访问的迭代器的容器（如vector, deque），都可以使用sort进行排序。

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. void print(const deque<int>& d)
    7. {
    8. 	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
    9. 	{
    10. 		cout << *it << " ";
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. int main()
    16. {
    17. 	// STL - deque - 排序
    18. 	/*算法：
    19. 		sort(iterator beg, iterator end);  //对beg和end区间内元素进行排序
    20. 	*/
    21.  
    22. 	deque<int> d;
    23. 	d.push_back(33);
    24. 	d.push_back(26);
    25. 	d.push_back(75);
    26. 	d.push_back(18);
    27. 	d.push_back(89);
    28.  
    29. 	cout << "容器中的元素：";
    30. 	print(d);
    31.  
    32. 	//排序 - 默认升序排序
    33. 	sort(d.begin(), d.end());
    34. 	cout << "排序后，容器中的元素：";
    35. 	print(d);
    36.  
    37. 	system("pause");
    38.  
    39. 	return 0;
    40. }

    输出结果

    容器中的元素：33 26 75 18 89
    排序后，容器中的元素：18 26 33 75 89

    2、stack容器

    stack是一种先进后出（First In Last Out, FILO）的数据结构，它只有一个出囗，且入囗与出囗共用一个。栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历行为。栈可以为空，也可以返回栈中的元素个数。栈中进入数据称为入栈（push），弹出数据称为出栈（pop），如下图所示：

    2.1、stack常用接囗

    函数原型：

    构造函数

    • stack stk;                    //stack采用模板类实现，stack对象的默认构造形式
    • stack(const stack& stk);   //拷贝构造函数

    赋值操作

    • stack& operator=(const stack& stk);  //重载运算符=

    数据存取

    • push(elem); //向栈顶添加元素
    • pop();          //从栈顶移除第一个元素
    • top();           //返回栈顶元素

    大小操作

    • empty();  //判断堆栈是否为空
    • size();     //返回栈大小
    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. int main()
    6. {
    7. 	// STL - stack - 常用接囗
    8. 	/*函数原型：
    9. 		构造函数
    10. 		1、stack stk;              //stack采用模板类实现，stack对象的默认构造形式
    11. 		2、stack(const stack& stk);   //拷贝构造函数
    13. 		赋值操作
    14. 		3、stack& operator=(const stack& stk);  //重载运算符=
    16. 		数据存取
    17. 		4、push(elem); //向栈顶添加元素
    18. 		5、pop();      //从栈顶移除第一个元素
    19. 		6、top();      //返回栈顶元素
    21. 		大小操作
    22. 		7、empty();  //判断堆栈是否为空
    23. 		8、size();   //返回栈大小
    24. 	*/
    25.  
    26. 	//1、stack stk; 
    27. 	stack<int> s1;
    28.  
    29. 	//7、empty();  //判断堆栈是否为空
    30. 	cout << "7、栈是否为空：" << (s1.empty() ? "是" : "否") << endl;
    31.  
    32. 	//4、push(elem); //向栈顶添加元素
    33. 	s1.push(20);
    34. 	s1.push(17);
    35.  
    36. 	//8、size();   //返回栈大小
    37. 	cout << "8、栈大小：" << s1.size() << endl;
    38.  
    39. 	//6、top();      //返回栈顶元素
    40. 	cout << "6、栈顶元素：" << s1.top() << endl;
    41.  
    42. 	//5、pop();      //从栈顶移除第一个元素
    43. 	s1.pop();
    44. 	cout << "5、移除栈顶元素后，栈大小：" << s1.size() << endl;
    45.  
    46. 	//2、stack(const stack& stk);   //拷贝构造函数
    47. 	stack<int> s2(s1);
    48. 	cout << "2、通过拷贝构造函数初始化栈，栈大小：" << s1.size() << endl;
    49.  
    50. 	//3、stack& operator=(const stack& stk);  //重载运算符=
    51. 	stack<int> s3;
    52. 	s3 = s2;
    53. 	cout << "3、通过重载运算符=赋值栈，栈大小：" << s1.size() << endl;
    54.  
    55. 	system("pause");
    56.  
    57. 	return 0;
    58. }

    输出结果

    7、栈是否为空：是
    8、栈大小：2
    6、栈顶元素：17
    5、移除栈顶元素后，栈大小：1
    2、通过拷贝构造函数初始化栈，栈大小：1
    3、通过重载运算符=赋值栈，栈大小：1

    3、queue容器

    queue是一种先进先出（First In First Out, FIFO）的数据结构，它有两个出囗，只有队头和队尾能被外界访问，因此不允许有遍历 为，可以判断队列是否为空，也可以返回队列大小，如下图所示：

    3.1、queqe常用接囗

    构造函数

    • queue que;                   //queue采用模板类实现，queue对象的默认构造形式
    • queue(const queue& que); //拷贝构造函数

    赋值操作

    • queue& operator(const queue& que);  //重载运算符=

    数据存取

    • push(elem);  //向队尾添加元素
    • pop();           //从队头移除第一个元素
    • back();         //返回最后一个元素
    • front();         //返回第一个元素

    大小操作

    • empty();  //判断队列是否为空
    • size();      //返回栈大小
    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. int main()
    6. {
    7. 	// STL - queue - 常用接囗
    8. 	/*函数原型：
    9. 		构造函数
    10. 		1、queue que;            //queue采用模板类实现，queue对象的默认构造形式
    11. 		2、queue(const queue& que); //拷贝构造函数
    13. 		赋值操作
    14. 		3、queue& operator(const queue& que);  //重载运算符=
    16. 		数据存取
    17. 		4、push(elem);  //向队尾添加元素
    18. 		5、pop();       //从队头移除第一个元素
    19. 		6、back();      //返回最后一个元素
    20. 		7、front();     //返回第一个元素
    22. 		大小操作
    23. 		8、empty();  //判断队列是否为空
    24. 		9、size();   //返回栈大小
    25. 	*/
    26.  
    27. 	//1、queue que; 默认构造函数
    28. 	queue<int> q1;
    29.  
    30. 	//4、push(elem);  //向队尾添加元素
    31. 	q1.push(22);
    32. 	q1.push(16);
    33. 	q1.push(67);
    34.  
    35. 	//9、size();   //返回栈大小
    36. 	cout << "9、添加元素后，队列大小：" << q1.size() << endl;
    37.  
    38. 	//6、back();      //返回最后一个元素
    39. 	cout << "6、最后一个元素：" << q1.back() << endl;
    40.  
    41. 	//7、front();     //返回第一个元素
    42. 	cout << "7、第一个元素：" << q1.front() << endl;
    43.  
    44. 	//2、queue(const queue & que); //拷贝构造函数
    45. 	queue<int> q2(q1);
    46. 	cout << "2、拷贝构造函数，队列大小：" << q1.size() << endl;
    47.  
    48. 	//3、queue& operator(const queue& que);  //重载运算符=
    49. 	queue<int> q3 = q1;
    50. 	cout << "3、重载运算符=，队列大小：" << q1.size() << endl;
    51.  
    52. 	cout << "8、重载运算符=，队列是否为空：" << (q1.empty() ? "是" : "否") << endl;
    53.  
    54. 	//8、empty();  //判断队列是否为空
    55. 	while (!q1.empty())
    56. 	{
    57. 		//5、pop();       //从队头移除第一个元素
    58. 		q1.pop();
    59. 	}
    60. 	cout << "5、移除所有元素后，队列大小：" << q1.size() << endl;
    61.  
    62. 	system("pause");
    63.  
    64. 	return 0;
    65. }

    输出结果

    9、添加元素后，队列大小：3
    6、最后一个元素：67
    7、第一个元素：22
    2、拷贝构造函数，队列大小：3
    3、重载运算符=，队列大小：3
    8、重载运算符=，队列是否为空：否
    5、移除所有元素后，队列大小：0

  • 相关阅读:
    Java Tomcat内存马——Servlet内存马
    【C语言 | 符号】C语言中符号易出错的地方
    C# tcp通信连接正常判断
    Hive中窗口函数的基本语法和示例
    java之ArrayList和Vector源码分析
    03 【布局之Aspect-Ratio Container Box-Decoration-Break Object-Fit Object-Position】
    时间轴_打印机
    【完全二叉树魔法：顺序结构实现堆的奇象】
    IntelliJ IDEA 安装及创建Java项目
    OVS与Linux Bridge的区别整理
  • 原文地址：https://blog.csdn.net/ling1998/article/details/126112636