[C++知识库]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<T> deqT;? ? ? ? //默认构造形式
• deque(beg, end);? ? ? //构造函数将[beg, end)区间中的元素拷贝给当前deque
• deque(n, elem);? ? ? ? //构造函数将n个elem拷贝给当前deque
• deque(const deque& deq); //拷贝构造函数

#include <iostream>
#include <deque>
using namespace std;

void print(const deque<int>& d)
{
	for (deque<int>::const_iterator  it = d.begin(); it < d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	// STL - deque - 构造函数
	/*函数原型：
		1、deque<T> deqT;? ? ? ?	//默认构造形式
		2、deque(beg, end);? ? ?	//构造函数将[beg, end)区间中的元素拷贝给当前deque
		3、deque(n, elem);? ? ? ?	//构造函数将n个elem拷贝给当前deque
		4、deque(const deque& deq); //拷贝构造函数
	*/
	
	//1、deque<T> deqT;
	deque<int> d1;
	for (int i = 0; i < 5; i++)
	{
		d1.push_back(i + 1);
	}
	print(d1);

	//2、deque(beg, end);
	deque<int> d2(d1.begin(), d1.end());
	print(d2);

	//3、deque(n, elem);
	deque<int> d3(5, 8);
	print(d3);

	//4、deque(const deque& deq); 
	deque<int> d4(d1);
	print(d4);

	system("pause");

	return 0;
}

输出结果

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拷贝赋值给本身

#include <iostream>
#include <deque>
using namespace std;

void print(const deque<int>& d)
{
	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	// STL - deque - 赋值操作
	/*函数原型：
		1、deque& operator=(const deque& deq);? //重载运算符=
		2、assign(beg, end);? ?//将[beg, end)区间中的数据拷贝给当前deque
		3、assign(n, elem);? ? ?//将n个elem拷贝赋值给本身
	*/

	deque<int> d;
	for (int i = 0; i < 5; i++)
	{
		d.push_front(i + 1);
	}
	print(d);

	//1、deque& operator=(const deque& deq);
	deque<int> d1;
	d1 = d;
	print(d1);

	//2、assign(beg, end);?
	deque<int>::iterator it = d1.begin();
	it++;
	deque<int> d2;
	d2.assign(it, d1.end());
	print(d2);

	//3、assign(n, elem);
	deque<int> d3;
	d3.assign(5, 8);
	print(d3);

	system("pause");

	return 0;
}

输出结果

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值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除

#include <iostream>
#include <deque>
using namespace std;

void print(const deque<int>& d)
{
	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	// STL - deque - 大小操作
	/*函数原型：
		1、deque.empty();? ? ? ? ?	//判断容器是否为空
		2、deque.size();? ? ? ? ? ? //返回容器中元素个数
		3、deque.resize(num);?		//重新指定容器的长度为num，若容器变长，则以默认值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
		4、deque.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
	*/

	deque<int> d;
	//1、deque.empty();? 
	cout << "1、容器是否为空：" << (d.empty() ? "是" : "否") << endl;

	for (int i = 0; i < 5; i++)
	{
		d.push_front(i + 1);
	}
	cout << "1、容器初始化元素：";
	print(d);
	cout << "1、容器是否为空：" << (d.empty() ? "是" : "否") << endl;

	//2、deque.size();
	cout << "2、容器中元素个数：" << d.size() << endl;

	//3、deque.resize(num);
	d.resize(8);
	cout << "3、容器长度变长后大小：" << d.size() << "，元素：";
	print(d);

	d.resize(3);
	cout << "3、容器长度变短后大小：" << d.size() << "，元素：";
	print(d);

	//4、deque.resize(num, elem);
	d.resize(9, 10);
	cout << "4、容器长度变长后大小：" << d.size() << "，元素：";
	print(d);

	d.resize(5, 6);
	cout << "4、容器长度变短后大小：" << d.size() << "，元素：";
	print(d);

	system("pause");

	return 0;
}

输出结果

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();? ? ? ? ? ? ? ? ? ? ? ? //清空容器中所有数据

#include <iostream>
#include <deque>
using namespace std;

void print(const deque<int>& d)
{
	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	// STL - deque - 插入和删除
	/*函数原型：
	两端操作：
		1、push_back(elem);? ?  //在容器尾部添加一个数据
		2、push_front(elem);? ? //在容器头部插入一个数据
		3、pop_back();? ? ? ? ? //删除容器最后一个数据
		4、pop_front();? ? ? ? ?//删除容器第一个数据

	指定位置操作：
		5、insert(pos, elem);? ? ?//在pos位置插入一个elem元素的拷贝，返回新数据的位置
		6、insert(pos, n, elem);? //在pos位置插入n个elem数据，无返回值
		7、insert(pos, beg, end);?//在pos位置插入[beg, end)区间的数据，无返回值
		8、erase(pos);? ? ? ? ? ? //删除pos位置的数据，返回下一个数据的位置
		9、erase(beg, end);? ? ?  //删除[beg, end)区间的数据，返回下一个数据的位置
		10、clear();? ? ? ? ? ? ? //清空容器中所有数据
	*/

	deque<int> d;
	//1、push_back(elem);
	for (int i = 0; i < 3; i++)
	{
		d.push_back(i + 1);
	}

	cout << "1、尾部添加3个数据，当前元素：";
	print(d);

	//2、push_front(elem);?
	for (int i = 10; i < 15; i++)
	{
		d.push_front(i + 1);
	}

	cout << "2、头部插入5个数据，当前元素：";
	print(d);

	//3、pop_back();?
	d.pop_back();
	cout << "3、尾部删除1个数据，当前元素：";
	print(d);

	//4、pop_front();?
	d.pop_front();
	cout << "4、头部删除1个数据，当前元素：";
	print(d);

	//5、insert(pos, elem);? 
	deque<int>::iterator pos = d.insert(d.begin(), 99);
	cout << "5、在第1位置添加数据，当前元素：";
	print(d);

	//6、insert(pos, n, elem);
	d.insert(pos, 3, 88);
	cout << "6、在第1位置添加数据，当前元素：";
	print(d);

	//7、insert(pos, beg, end)
	deque<int> d2;
	d2.push_back(1);
	d2.push_back(2);

	pos = d.insert(d.begin(), d2.begin(), d2.end());
	cout << "7、在第1位置添加数据，当前元素：";
	print(d);

	//8、erase(pos);?
	d.erase(pos);
	cout << "8、删除第1位置数据，当前元素：";
	print(d);

	//9、erase(beg, end);?
	pos = d.begin();
	pos++;
	d.erase(pos, d.end());
	cout << "9、删除第2位置至尾区间数据，当前元素：";
	print(d);

	//10、clear();? 
	d.clear();
	cout << "10、清空数据，容器大小：" << d.size() << "，当前元素：";
	print(d);

	system("pause");

	return 0;
}

输出结果

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();? ? ? //返回容器中最后一个数据元素

#include <iostream>
#include <deque>
using namespace std;

void print(const deque<int>& d)
{
	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	// STL - deque - 数据读取
	/*函数原型：
		1、at(int idx);? ?//返回索引idx所指的数据
		2、operator[];?   //返回索引idx所指的数据
		3、front();? ? ? ?//返回容器中第一个数据元素
		4、back();? ? ?   //返回容器中最后一个数据元素
	*/

	deque<int> d;
	for (int i = 0; i < 5; i++)
	{
		d.push_back(i + 1);
	}
	cout << "容器中的元素：";
	print(d);

	//1、at(int idx);
	cout << "1、读取第3个元素：" << d.at(2) << endl;

	//2、operator[];
	cout << "2、读取第2个元素：" << d[1] << endl;

	//3、front();?
	cout << "3、读取第一个元素：" << d.front() << endl;

	//4、back();? 
	cout << "4、读取最后一个元素：" << d.back() << endl;

	system("pause");

	return 0;
}

输出结果

容器中的元素：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进行排序。

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

void print(const deque<int>& d)
{
	for (deque<int>::const_iterator it = d.begin(); it < d.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	// STL - deque - 排序
	/*算法：
		sort(iterator beg, iterator end);? //对beg和end区间内元素进行排序
	*/

	deque<int> d;
	d.push_back(33);
	d.push_back(26);
	d.push_back(75);
	d.push_back(18);
	d.push_back(89);

	cout << "容器中的元素：";
	print(d);

	//排序 - 默认升序排序
	sort(d.begin(), d.end());
	cout << "排序后，容器中的元素：";
	print(d);

	system("pause");

	return 0;
}

输出结果

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

2、stack容器

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

2.1、stack常用接囗

函数原型：

构造函数

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

赋值操作

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

数据存取

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

大小操作

• empty();? //判断堆栈是否为空
• size();? ? ?//返回栈大小

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	// STL - stack - 常用接囗
	/*函数原型：
		构造函数
		1、stack<T> stk;? ? ? ? ? ? ? //stack采用模板类实现，stack对象的默认构造形式
		2、stack(const stack& stk);? ?//拷贝构造函数

		赋值操作
		3、stack& operator=(const stack& stk);? //重载运算符=

		数据存取
		4、push(elem); //向栈顶添加元素
		5、pop();? ? ? //从栈顶移除第一个元素
		6、top();? ? ? //返回栈顶元素

		大小操作
		7、empty();? //判断堆栈是否为空
		8、size();? ?//返回栈大小
	*/

	//1、stack<T> stk;?
	stack<int> s1;

	//7、empty();? //判断堆栈是否为空
	cout << "7、栈是否为空：" << (s1.empty() ? "是" : "否") << endl;

	//4、push(elem); //向栈顶添加元素
	s1.push(20);
	s1.push(17);

	//8、size();? ?//返回栈大小
	cout << "8、栈大小：" << s1.size() << endl;

	//6、top();? ? ? //返回栈顶元素
	cout << "6、栈顶元素：" << s1.top() << endl;

	//5、pop();? ? ? //从栈顶移除第一个元素
	s1.pop();
	cout << "5、移除栈顶元素后，栈大小：" << s1.size() << endl;

	//2、stack(const stack& stk);? ?//拷贝构造函数
	stack<int> s2(s1);
	cout << "2、通过拷贝构造函数初始化栈，栈大小：" << s1.size() << endl;

	//3、stack& operator=(const stack& stk);? //重载运算符=
	stack<int> s3;
	s3 = s2;
	cout << "3、通过重载运算符=赋值栈，栈大小：" << s1.size() << endl;

	system("pause");

	return 0;
}

输出结果

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

3、queue容器

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

3.1、queqe常用接囗

构造函数

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

赋值操作

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

数据存取

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

大小操作

• empty();? //判断队列是否为空
• size();? ? ? //返回栈大小

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	// STL - queue - 常用接囗
	/*函数原型：
		构造函数
		1、queue<T> que;? ? ? ? ? ? //queue采用模板类实现，queue对象的默认构造形式
		2、queue(const queue& que); //拷贝构造函数

		赋值操作
		3、queue& operator(const queue& que);? //重载运算符=

		数据存取
		4、push(elem);? //向队尾添加元素
		5、pop();? ? ? ?//从队头移除第一个元素
		6、back();? ? ? //返回最后一个元素
		7、front();? ? ?//返回第一个元素

		大小操作
		8、empty();? //判断队列是否为空
		9、size();? ?//返回栈大小
	*/

	//1、queue<T> que;?默认构造函数
	queue<int> q1;

	//4、push(elem);? //向队尾添加元素
	q1.push(22);
	q1.push(16);
	q1.push(67);

	//9、size();? ?//返回栈大小
	cout << "9、添加元素后，队列大小：" << q1.size() << endl;

	//6、back();? ? ? //返回最后一个元素
	cout << "6、最后一个元素：" << q1.back() << endl;

	//7、front();? ? ?//返回第一个元素
	cout << "7、第一个元素：" << q1.front() << endl;

	//2、queue(const queue & que); //拷贝构造函数
	queue<int> q2(q1);
	cout << "2、拷贝构造函数，队列大小：" << q1.size() << endl;

	//3、queue& operator(const queue& que);? //重载运算符=
	queue<int> q3 = q1;
	cout << "3、重载运算符=，队列大小：" << q1.size() << endl;

	cout << "8、重载运算符=，队列是否为空：" << (q1.empty() ? "是" : "否") << endl;

	//8、empty();? //判断队列是否为空
	while (!q1.empty())
	{
		//5、pop();? ? ? ?//从队头移除第一个元素
		q1.pop();
	}
	cout << "5、移除所有元素后，队列大小：" << q1.size() << endl;

	system("pause");

	return 0;
}

输出结果

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