双端队列deque （非原创）

http://hi.baidu.com/xuehuo_0411/item/f72d5120d5006ad0a517b6b8  原文出处。

 

C++ STL 容器技术 之 deque双端队列容器

简介：

deque双端队列容器(double-ended queue)与vector非常相似，算法的时间复杂度也是常数阶O(1)，deque内部的数据机制和执行性能与vector不同，一般说来，当考虑到容器元素的内存分配策略和操作的性能时，deque相对vector较为有优势。deque双端队列采用分块的线性结构来存储数据，具有高效的删除首尾元素的函数，由于deque容器是以deque块为单位进行内存的分配，并使用了二级的Map进行管理，因此不容易实现类似于vector的capacity和reverse函数，而且deque容器也不需要这样的获取和调整容器大小的函数。

deque应用基础：

创建deque对象：

1、deque() 创建一个空的deque对象。

如：deque<int> d;

2、deque(size_type n) 创建一个具有n个元素的deque对象，每个deque元素具有它的类型下的默认值。

如：deque<int> d(10);

3、deque(size_type n, const T& value) 创建一个具有n个元素的deque对象，每个元素具有初始值value。

如：deque<int> d(10, 5);

4、deque(const deque&) 通过拷贝一个deque对象的各个元素值，创建一个新的deque对象。

如：deque<int> d1(10, 5);        deque<int> d2(d1);

5、deque(const InputIterator first, const InputIterator last, const A& a=A()) 通过拷贝迭代器区间[first, last)的元素值，创建一个新的deque对象中，内存分配器可省略。

如：int iArray[] = {1,2,3};      deque<int> d(iArray, iArray+3);

初始化赋值：

deque提供的push_back函数常用来进行deque容器的初始化，push_back函数在容器的尾端插入新元素value。

void push_back(const T&)

元素的遍历访问：

deque的元素可采用数组或迭代器的方式进行遍历访问。

元素的插入：

由于deque使用了两个迭代器分别指向双端队列的首尾，因此deque具有高效的头部插入元素的函数push_front()

void push_front(const T&)

其它位置的插入，将涉及相关元素的移位拷贝，insert函数的一个较常用的原型为：

iterator insert(iterator pos, const T& x)

元素的删除：

void pop_front() 删除deque的第一个元素

void pop_back() 删除deque的最后一个元素

iterator erase(iterator pos) 删除迭代器pos所指的元素

iterator erase(iterator first, iterator last) 删除迭代器区间[first, last)的所有元素

void clear() 调用erase函数，清除所有元素

元素的反向遍历：

reverse_iterator rbegin()

reverse_iterator rend()

deque的交换：

void swap(deque&)

其它常用函数：

bool empty()

size_type size()

size_type max_size()

reference front()

reference back()

 

 

举例分析：

1、

//用数组的方式访问deque元素
#include <iostream>
#include <deque>
using namespace std;
int main(void)
{
deque<int> d;
d.push_back(13);
d.push_back(32);
d.push_back(29);
for (int i=0; i<d.size(); i++)
{
   cout << "d[" << i << "] = " << d[i] << endl;
}

return 0;
}

2、

 

//用迭代器访问deque元素
#include <deque>
#include <iostream>
using namespace std;

int main(void)
{
deque<string> d;
d.push_back("a");
d.push_back("b");
d.push_back("c");
deque<string>::iterator i, iend;
iend = d.end();
int j;
for (i=d.begin(),j=0; i!=iend; i++,j++)
{
   cout << *i << " ";
}
cout << endl;

return 0;
}

3、

 

//头部和中间位置插入deque元素
#include <deque>
#include <iostream>
using namespace std;

int main(void)
{
deque<int> d;
d.push_back(6);
d.push_back(7);   
//头部插入
d.push_front(5);
for (int i=0; i<d.size(); i++)
{
   cout << d[i] << " ";
}
cout << endl;

//中间位置插入
d.insert(d.begin()+1, 9);
for (int j=0; j<d.size(); j++)
{
   cout << d[j] << ' ';
}
cout << endl;

return 0;
}

4、

 

//头尾和其它位置删除deque元素
#include <deque>
#include <iostream>
using namespace std;

int main(void)
{
deque<int> d;
d.push_back(4);
d.push_back(5);
d.push_back(3);
d.push_back(3);
d.push_back(3);
d.push_back(6);
for (int i=0; i<d.size(); i++)
{
   cout << d[i] << ' ' ;
}
cout << endl;

//头尾和任意位置删除元素
d.erase(d.begin()+1);
d.pop_front();
d.pop_back();
for (int j=0; j<d.size(); j++)
{
   cout << d[j] << ' ' ;
}
cout << endl;

//删除所有元素
d.clear();
cout << "执行clear()" << endl << "deque元素全部清除" << endl;

return 0;
}

5、

 

//deque元素的反向遍历
#include <deque>
#include <iostream>
using namespace std;

int main(void)
{
deque<int> d;
d.push_back(1);    
d.push_back(3);
d.push_back(5);
d.push_back(7);
d.push_back(9);

//deque元素的前向遍历
deque<int>::iterator i, iend;
iend = d.end();
for (i=d.begin(); i!=iend; i++)
{
   cout << *i << " ";
}
cout << endl;

//deque元素的反向遍历
deque<int>::reverse_iterator ri, riend;
riend = d.rend();
for (ri=d.rbegin(); ri!=riend; ri++)
{
   cout << *ri << " ";
}
cout << endl;

return 0;
}

6、

//两个deque容器的元素交换
#include <deque>
#include <iostream>
using namespace std;

void print(deque<int>& d)
{
for (int i=0; i<d.size(); i++)
{
   cout << d[i] << " ";
}
cout << endl;
}

int main(void)
{
deque<int> d1;
d1.push_back(11);
d1.push_back(12); 
d1.push_back(13);
cout << "d1 = ";
print(d1);

deque<int> d2;
d2.push_back(90);
d2.push_back(91);
d2.push_back(92);
cout << "d2 = ";
print(d2);

//d1和d2交换
d1.swap(d2);
cout << "d1与d2交换后" << endl;
cout << "d1 = ";
print(d1);
cout << "d2 = ";
print(d2);

return 0;
}

7、

 

//deque其它常用函数的使用
#include <deque>
#include <iostream>
using namespace std;

int main(void)
{
deque<string> d;
//打印deque为空
cout << "d是否为空: " << d.empty() << endl;
//装入元素
d.push_back("红楼梦");
d.push_back("源氏物语");
d.push_back("教父");
d.push_back("水浒传");
d.push_back("24史");

//打印deque所有元素
deque<string>::iterator i, iend;
iend = d.end();
for (i=d.begin(); i!=iend; i++)
{
   cout << *i << " ";
}
cout << endl;

//打印首元素
cout << "deque首元素为: " << d.front() << endl;
//打印末元素
cout << "deque末元素为: " << d.back() << endl;
//打印元素个数
cout << "deque元素个数为: " << d.size() << endl;
//打印可支持的最大deque元素个数
cout << "deque最大元素个数为: " << d.max_size() << endl;

return 0;
}