C++ Double Ended Queues(双向队列)

双向队列和向量很相似，但是它允许在容器头部快速插入和删除（就像在尾部一样）。

Constructors	创建一个新双向队列
Operators	比较和赋值双向队列
assign()	设置双向队列的值
at()	返回指定的元素
back()	返回最后一个元素
begin()	返回指向第一个元素的迭代器
clear()	删除所有元素
empty()	返回真如果双向队列为空
end()	返回指向尾部的迭代器
erase()	删除一个元素
front()	返回第一个元素
get_allocator()	返回双向队列的配置器
insert()	插入一个元素到双向队列中
max_size()	返回双向队列能容纳的最大元素个数
pop_back()	删除尾部的元素
pop_front()	删除头部的元素
push_back()	在尾部加入一个元素
push_front()	在头部加入一个元素
rbegin()	返回指向尾部的逆向迭代器
rend()	返回指向头部的逆向迭代器
resize()	改变双向队列的大小
size()	返回双向队列中元素的个数
swap()	和另一个双向队列交换元素

// 1. 定义一个int类型的空双端队列 v0
deque v0;
// 2. 定义一个int类型的双端队列 v1，并设置初始大小为10; 线性复杂度
deque v1(10);
// 3. 定义一个int类型的双端队列 v2，并初始化为10个1; 线性复杂度
deque v2(10, 1);
// 4. 复制已有的双端队列 v1; 线性复杂度
deque v3(v1);
// 5. 创建一个v2的拷贝deque v4，其内容是v4[0]至v4[2]; 线性复杂度
deque v4(v2.begin(), v2.begin() + 3);
// 6. 移动v2到新创建的deque v5，不发生拷贝; 常数复杂度; 需要 C++11
deque v5(std::move(v2));

1. at()

   v.at(pos) 返回容器中下标为 pos 的引用。如果数组越界抛出 std::out_of_range 类型的异常。

2. operator[]

   v[pos] 返回容器中下标为 pos 的引用。不执行越界检查。

3. front()

   v.front() 返回首元素的引用。

4. back()

   v.back() 返回末尾元素的引用。

5. data()

   v.data() 返回指向数组第一个元素的指针。

1. begin()/cbegin()

   返回指向首元素的迭代器，其中 *begin = front。

2. end()/cend()

   返回指向数组尾端占位符的迭代器，注意是没有元素的。

3. rbegin()/crbegin()

   返回指向逆向数组的首元素的逆向迭代器，可以理解为正向容器的末元素。

4. rend()/crend()

   返回指向逆向数组末元素后一位置的迭代器，对应容器首的前一个位置，没有元素。

• empty() 返回一个 bool 值，即 v.begin() == v.end()，true 为空，false 为非空。

• size() 返回容器长度（元素数量），即 std::distance(v.begin(), v.end())。

• resize() 改变 vector 的长度，多退少补。补充元素可以由参数指定。

• max_size() 返回容器的最大可能长度。

  与容量相关：

• reserve() 使得 vector 预留一定的内存空间，避免不必要的内存拷贝。

• capacity() 返回容器的容量，即不发生拷贝的情况下容器的长度上限。

• shrink_to_fit() 使得 vector 的容量与长度一致，多退但不会少。

7、元素增删及修改

• clear() 清除所有元素
• insert() 支持在某个迭代器位置插入元素、可以插入多个。复杂度与 pos 距离末尾长度成线性而非常数的
• erase() 删除某个迭代器或者区间的元素，返回最后被删除的迭代器。复杂度与 insert 一致。
• push_back() 在末尾插入一个元素，均摊复杂度为 常数，最坏为线性复杂度。
• pop_back() 删除末尾元素，常数复杂度。
• swap() 与另一个容器进行交换，此操作是 常数复杂度 而非线性的。

 8、代码示例：

#include

#include

using namespace std;

int main()
{
	
	deque v0;//创建一个双端队列v0（双端向量）

	deque v1(10);//创建一个int类型的大小为10的双端队列

	deque v2(10, 1);//双端队列初始化10个1

	deque v3(v1);//创建队列v3拷贝v1

	deque v4(v2.begin(), v2.begin() + 3);//v4[0]~v4[2]的内容为v2的一部分

	for (int i = 0; i < 10; i++)
	{
		v0.push_back(i);
	}

	for (int i = 0; i < 10; i++)
	{
		cout << v0.front()<<' ';

		v0.pop_front();
	}

	cout< vc;

	for (int i = 0; i < 10; i++)
		vc.push_back(i + 65);

	deque::iterator it;

	for (it = vc.begin(); it != vc.end(); it++)
	{
		cout << *it << ' ';
	}

	return 0;
}