STL库实现之双端队列
度娘说：
deque 即双端队列。（deque，全名double-ended queue）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。
双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像栈一样，可以用一个铁道转轨网络来比喻双端队列。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻的栈了。
相关用法如下：
说明
#include <deque>deque容器类与vector类似，支持随机访问和快速插入删除，它在容器中某一位置上的操作所花费的是线性时间。与vector不同的是，deque还支持从开始端插入数据：push_front()。
构造：
deque<Elem> c 创建一个空的deque
deque<Elem> c1(c2) 复制一个deque。
deque<Elem> c(n) 创建一个deque，含有n个数据，数据均已缺省构造产生。
deque<Elem> c(n, elem) 创建一个含有n个elem拷贝的deque
deque<Elem> c(beg,end) 创建一个以[beg;end)区间的deque
c.~deque<Elem>() 销毁所有数据，释放内存
方法：
c.assign(beg,end) 将[beg; end)区间中的数据赋值给c。
c.assign(n,elem) 将n个elem的拷贝赋值给c。
c. at(idx) 传回索引idx所指的数据，如果idx越界，抛出out_of_range。
c.back() 传回最后一个数据，不检查这个数据是否存在。
c.begin() 传回迭代器中的第一个数据。
c.clear() 移除容器中所有数据。
c.empty() 判断容器是否为空。
c.end() 指向迭代器中的最后一个数据地址。
c.erase(pos) 删除pos位置的数据，传回下一个数据的位置。
c.erase(beg,end) 删除[beg,end)区间的数据，传回下一个数据的位置。
c.front() 传回第一个数据。
get_allocator 使用构造函数返回一个拷贝。
c.insert(pos,elem) 在pos位置插入一个elem拷贝，传回新数据位置
c.insert(pos,n,elem) 在pos位置插入>n个elem数据。无返回值
c.insert(pos,beg,end) 在pos位置插入在[beg,end)区间的数据。无返回值
c.max_size() 返回容器中最大数据的数量。
c.pop_back() 删除最后一个数据。
c.pop_front() 删除头部数据。
c.push_back(elem) 在尾部加入一个数据。
c.push_front(elem) 在头部插入一个数据。
c.rbegin() 传回一个逆向队列的第一个数据。
c.rend() 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num) 重新指定队列的长度。
c.size() 返回容器中实际数据的个数。
c.swap(c2)
swap(c1,c2) 将c1和c2元素互换。
下面是一个典型的不能在典型的题目了。。
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1466
#include <iostream>
#include <deque>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
//freopen("d:\\my1.txt","r",stdin);
//freopen("d:\\aaa.txt","w",stdout);
char s[10];
int wrong[10005];
int n,x,count=0,k=0;
cin>>n;
int j;
deque <int> c;
deque <int> ::iterator pos;
while(n--)
{
cin>>s;
if(!(strcmp(s,"LIN")))
{
cin>>x;
c.push_front(x);
count++;
}
else if(!(strcmp(s,"RIN")))
{
cin>>x;
c.push_back(x);
count++;
}
else if(!(strcmp(s,"LOUT")))
{
if(c.empty())
{
wrong[k++]=++count;
}
else
{
c.pop_front();
count++;
}
}
else if(!(strcmp(s,"ROUT")))
{
if(c.empty())
{
wrong[k++]=++count;
}
else
{
c.pop_back();
count++;
}
}
else wrong[k++]=++count;
}
j=0;
for (pos=c.begin();pos!=c.end();pos++)
{
if(j<c.size()-1) cout<<*pos<<" ";
else cout<<*pos;
}
cout<<endl;
for(int i=0;i<=k-1;i++)
{
cout<<wrong[i]<<" ERROR"<<endl;
//if(i!=(k-1)) cout<<endl;
}
}
MoreWindows说：
另外要注意一点。对于deque和vector来说，尽量少用erase(pos)和erase(beg,end)。因为这在中间删除数据后会导致后面的数据向前移动，从而使效率低下。