2.8 deque双端队列容器
deque双端队列容器与vector一样，采用线性表顺序存储结构。但与vector唯一不同的是，deque采用分块的线性存储结构来存储数据，每块的大小一般为512字节，称为一个deque块，所有的deque块使用一个Map块进行管理，每个Map数据项记录各个deque块的首地址。这样一来，deque块在头部和尾部都可插入和删除元素，而不需移动其他元素（使用push_back()方法在尾部插入元素，会扩张队列；而使用push_front()方法在首部插入元素和使用insert()方法在中间插入元素，只是将原位置上的元素值覆盖，不会增加新元素）。一般来说，当考虑到容器元素的内存分配策略和操作的性能时，deque相对于vector更有优势。双端队列容器结构示意图如图2-6所示。
图2-6 双端队列容器结构示意图
使用deque需要声明头文件包含“#include <deque>”，文件deque在C:\Program Files\Microsoft Visual Studio\VC98\Include文件夹中。
2.8.1 创建deque对象
创建deque对象的方法通常有三种。
（1）创建没有任何元素的deque对象，如：
deque<int> d;
deque<float> dd;
（2）创建具有n个元素的deque对象，如：
deque<int> d（10）; //创建具有10个整型元素的deque对象d
（3）创建具有n个元素的deque对象，并赋初值，如：
deque<int> d（10,8.5）; //创建具有10个整型元素的deque对象d，每个元素值为8.5
2.8.2 插入元素
（1）使用push_back()方法从尾部插入元素，会不断扩张队列。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入三个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
//以数组方式输出元素
cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
return 0;
}
运行结果：
1 2 3
（2）从头部插入元素，不会增加新元素，只将原有的元素覆盖。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入三个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
//从头部插入元素，不会增加新元素，只将原有的元素覆盖
d.push_front(10);
d.push_front(20);
//以数组方式输出元素
cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
return 0;
}
运行结果：
20 10 1
（3）从中间插入元素，不会增加新元素，只将原有的元素覆盖。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入三个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
//中间插入元素，不会增加新元素，只将原有的元素覆盖
d.insert(d.begin()+1,88);
//以数组方式输出元素
cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
return 0;
}
运行结果：
1 88 2
2.8.3 前向遍历
（1）以数组方式遍历。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入三个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
//以数组方式输出元素
int i;
for(i=0; i<d.size(); i++)
{
cout<<d[i]<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
1 2 3
（2）以前向迭代器的方式遍历。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入三个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
//以前向迭代器的方式遍历
deque<int>::iterator it;
for(it=d.begin(); it! =d.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
1 2 3
2.8.4 反向遍历
采用反向迭代器对双端队列容器进行反向遍历。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入三个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
//以反向迭代器的方式遍历
deque<int>::reverse_iterator rit;
for(rit=d.rbegin(); rit! =d.rend(); rit++)
{
cout<<*rit<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
3 2 1
2.8.5 删除元素
可以从双端队列容器的首部、尾部、中部删除元素，并可以清空双端队列容器。下面分别举例说明这4种删除元素的操作方法。
（1）采用pop_front()方法从头部删除元素。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入五个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
d.push_back(4);
d.push_back(5);
//从头部删除元素
d.pop_front();
d.pop_front();
//以前向迭代器的方式遍历
deque<int>::iterator it;
for(it=d.begin(); it! =d.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
3 4 5
（2）采用pop_back()方法从尾部删除元素。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入五个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
d.push_back(4);
d.push_back(5);
//从尾部删除元素
d.pop_back();
//以前向迭代器的方式遍历
deque<int>::iterator it;
for(it=d.begin(); it! =d.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
1 2 3 4
（3）使用erase()方法从中间删除元素，其参数是迭代器位置。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入五个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
d.push_back(4);
d.push_back(5);
//从中间删除元素，erase的参数是迭代器位置
d.erase(d.begin()+1);
//以前向迭代器的方式遍历
deque<int>::iterator it;
for(it=d.begin(); it! =d.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
1 3 4 5
（4）使用clear()方法清空deque对象。
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义deque对象，元素类型是整型
deque<int> d;
//从尾部连续插入五个元素
d.push_back(1);
d.push_back(2);
d.push_back(3);
d.push_back(4);
d.push_back(5);
//清空元素
d.clear();
//输出元素的个数
cout<<d.size()<<endl;
return 0;
}
运行结果：
0