Home C++ 双端队列deque
Post
Cancel

C++ 双端队列deque

deque (双端队列) 可以向两端插入元素, queue 只能向一端插入元素.

头文件

1
#include <deque>

定义和初始化

1
2
3
4
5
deque<int> a; // 定义一个int类型的双端队列a
deque<int> a(10); // 定义一个int类型的双端队列a,并设置初始大小为10
deque<int> a(10, 1); // 定义一个int类型的双端队列a,并设置初始大小为10且初始值都为1
deque<int> b(a); // 定义并用双端队列a初始化双端队列b
deque<int> b(a.begin(), a.begin()+3); // 将双端队列a中从第0个到第2个(共3个)作为双端队列b的初始值

另一种有趣的初始化方法:

1
2
3
4
5
6
7
8
9
int a[]={1,2,3,4,5,6,7};
deque<int>q1(a+1,a+5);
for(auto it=q1.begin();it!=q1.end();++it)
    cout<<*it<<" ";
cout<<endl;
deque<int>q2(&a[1],&a[4]); // 将a[1],a[2],a[3]作为初值
for(auto it=q2.begin();it!=q2.end();++it)
    cout<<*it<<" ";
cout<<endl;

注意 deque 是有迭代器的, 可以用 begin(), end() 等函数获取迭代器, 而 stackqueue 没有迭代器.

容量函数

容器大小: deq.size()

容器最大容量: deq.max_size()

更改容器大小: deq.resize()

容器判空: deq.empty()

减少容器大小到满足元素所占存储空间的大小: deq.shrink_to_fit()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	for (int i = 0; i<6; i++)
	{
		deq.push_back(i);
	}

	cout << deq.size() << endl; // 输出:6
	cout << deq.max_size() << endl; // 输出:1073741823
	deq.resize(0); // 更改元素大小
	cout << deq.size() << endl; // 输出:0
	if (deq.empty())
		cout << "元素为空" << endl; // 输出:元素为空

	return 0;
}

添加函数

头部添加元素: deq.push_front(const T& x)

末尾添加元素: deq.push_back(const T& x)

任意位置插入一个元素: deq.insert(iterator it, const T& x)

任意位置插入 n 个相同元素: deq.insert(iterator it, int n, const T& x)

插入另一个向量的 [first,last] 间的数据:deq.insert(iterator it, iterator first, iterator last)

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
36
37
38
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;

	// 头部增加元素
	deq.push_front(4); // 4
	// 末尾添加元素
	deq.push_back(5); // 4 5

	// 任意位置插入一个元素
	deque<int>::iterator it = deq.begin();
	deq.insert(it, 2); // 2 4 5

	// 任意位置插入n个相同元素
	it = deq.begin();
	deq.insert(it, 3, 9); // 9 9 9 2 4 5

	deque<int> deq2(5,8); // 8 8 8 8 8
	it = deq.begin();
	deq.insert(it, deq2.end() - 1, deq2.end());

	// 遍历显示
	for (it = deq.begin(); it != deq.end(); it++)
		cout << *it << " "; // 输出:8 9 9 9 2 4 5
	cout << endl;

    deq.insert(it, deq2.end() - 3, deq2.end());
    for (it = deq.begin(); it != deq.end(); it++)
		cout << *it << " "; // 输出:8 9 9 9 2 4 5 8 8 8
	cout << endl;

	return 0;
}

删除函数

头部删除元素: deq.pop_front()

末尾删除元素: deq.pop_back()

任意位置删除一个元素: deq.erase(iterator it)

[first,last) 间的数据删除: deq.erase(iterator first, iterator last)

清空所有元素: deq.clear()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
    deque<int> deq;
    for (int i = 0; i<6; i++)
    {
        deq.push_back(i);
    }
    deque<int>::iterator it = deq.begin();
    deq.erase(it); // 删除头部元素
    it = deq.end();
    deq.erase(--it); // 删除末尾元素
    it = deq.begin();
    deq.erase(it, it + 2); // 删除中间2个元素
    for (it = deq.begin(); it != deq.end(); it++)
        cout << *it << " "; // 输出:3 4
    cout << endl;
    return 0;
}

查找函数

查找元素: deq.find(const T& x)

查找元素的位置: deq.find(const T& x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
    deque<int> deq;
    for (int i = 0; i<6; i++)
    {
        deq.push_back(i);
    }
    deque<int>::iterator it = deq.begin();
    it = deq.find(3); // 查找元素3的位置
    if (it != deq.end())
        cout << "找到了" << endl; // 输出:找到了
    else
        cout << "没找到" << endl; // 输出:没找到
    return 0;
}

访问函数

头部元素: deq.front()

末尾元素: deq.back()

下标访问: deq[1] (并不会检查是否越界) at 方法访问: deq.at(1) (以上两者的区别就是 at 会检查是否越界, 抛出 out of range 异常)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
    deque<int> deq;
    for (int i = 0; i<6; i++)
    {
        deq.push_back(i);
    }
    cout << deq.front() << endl; // 输出:0
    cout << deq.back() << endl; // 输出:5
    // 下标访问
	cout << deq[0] << endl; // 输出:0
	// at方法访问
	cout << deq.at(0) << endl; // 输出:0
    return 0;
}

其他函数

多个元素赋值: deq.assign(int nSize, const T& x) (类似于初始化时用数组进行赋值)

交换两个同类型容器的元素: swap(deque&)

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
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	// 多个元素赋值
	deque<int> deq;
	deq.assign(3, 1);
	deque<int> deq2;
	deq2.assign(3, 2);

	// 交换两个容器的元素
	deq.swap(deq2);

	// 遍历显示
	cout << "deq: ";
	for (int i = 0; i < deq.size(); i++)
		cout << deq[i] << " "; // 输出:2 2 2
	cout << endl;

	// 遍历显示
	cout << "deq2: ";
	for (int i = 0; i < deq2.size(); i++)
		cout << deq2[i] << " "; // 输出:1 1 1
	cout << endl;

	return 0;
}

迭代器

开始迭代器指针: deq.begin()

末尾迭代器指针: deq.end() (指向最后一个元素的下一个位置)

指向常量的开始迭代器指针: deq.cbegin() (不能通过这个指针来修改所指的内容, 但还是可以通过其他方式修改, 而且指针也是可以移动的)

指向常量的末尾迭代器指针: deq.cend()

反向迭代器指针, 指向最后一个元素: deq.rbegin()

反向迭代器指针, 指向第一个元素的前一个元素: deq.rend()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char* argv[])
{
	deque<int> deq;
	deq.push_back(1);
	deq.push_back(2);
	deq.push_back(3);

	cout << *(deq.begin()) << endl; // 输出:1
	cout << *(--deq.end()) << endl; // 输出:3
	cout << *(deq.cbegin()) << endl; // 输出:1
	cout << *(--deq.cend()) << endl; // 输出:3
	cout << *(deq.rbegin()) << endl; // 输出:3
	cout << *(--deq.rend()) << endl; // 输出:1
	cout << endl;

	return 0;
}

翻转:

1
2
#include <algorithm>
reverse(deq.begin(), deq.end());

排序:

1
2
3
4
5
6
7
8
#include <algorithm>
sort(deq.begin(), deq.end()); // 默认从小到大

bool cmp(const int& a, const int& b) { // 自定义比较器
    return a > b;
}

sort(deq.begin(), deq.end(), cmp);

总结

都说了这么多了, 写算法题肯定是够用了的.

可以看到, dequevector 的用法基本一致, 除了以下几处不同:

  • deque 没有 capacity() 函数, 而 vector 有;
  • dequepush_front()pop_front() 函数, 而 vector 没有;
  • deque 没有 data() 函数, 而 vector 有.

参考

This post is licensed under CC BY 4.0 by the author.