双端队列类模板和链表类模板

一、双端队列类模板

双端队列（deque）是一种随机访问的数据类型，提供了在序列两端快速插入和删除操作的功能，它可以在需要的时候修改其自身的大小，主要完成标准c++数据结构中队列的功能。

1、使用双端队列类模板需要创建deque对象，创建deque对象有以下几种方法：

（1）、std::dequename;

（2）、std::dequename(size);

（3）、std::dequename(size,value);

（4）、std::dequename(mydeque);

（5）、std::dequename(first,last);

2、实例

#include
#include
using namespace std;

void main()
{
	dequeintdeque;
	intdeque.push_back(2);
	intdeque.push_back(3);
	intdeque.push_back(4);
	intdeque.push_back(7);
	intdeque.push_back(9);
	cout<<"Deque:old"< 
结果如下：
 
 
二、链表类模板
 
链表（list），即双向列表容器，它不支持随机访问，访问链表元素要指针从链表的某个端点开始，插入和删除操作所花费的时间是固定的，和该元素在链表中的位置无关。list在任何位置插入和删除动作都很快，不像vector只在末尾进行操作。
 
1、使用链表类模板需要创建list对象，创建list对象有以下几种方法
 
（1）、std::listname;
 
（2）、std::listname(size);
 
（3）、std::listname(size,value);
 
（4）、std::listname(mylist);
 
（5）、std::listname(first,last);
 
 list所支持的操作与vector很相近。但这些操作的实现原理很不相同，执行效率也不一样。List（双向链表）的优点是插入元素的效率很高，缺点是不支持随机访问。也就是说，链表无法像数组一样通过索引来访问。
 
2、实例：list和vector中的迭代器
 
#include
#include
#include
using std::list;
using std::vector;
using std::cout;
using std::endl;

void main()
{
	cout<<"使用未排序储存0—9的数组初始化list1"<list1(array,array+10);
	cout<<"list1调用sort方法排序"<::iterator iter=list1.begin();
	cout<<"通过迭代器访问list双向链表中从头开始向后的第四个元素"< 
结果如下：
 
 
通过程序可以观察到，迭代器iterator类和指针用法很相似，支持自增操作符，并且通过"*"可以访问相应的对象内容。但list中的迭代器不支持"+"运算符，而指针与vector中的迭代器都支持。