双端队列DEQUE
deque又叫双端队列，它支持随机访问迭代器。与普通的队列不同，双端队列可以在队首增加和删除元素，也可以在对尾增加和删除元素，不必再遵循队首出队、队尾入队的原则。
双端队列与vector的区别
- 缺点：
deque存储元素的速度比vector快一些。因为它们两都是可变长的，实现可变长的方法是倍增(什么是倍增思想？如：长度变为当前容器内元素个数的2倍)。但是，vector只需要在一端改变，而deque需要向两端增加长度，操作变多，因此速度稍慢一些。 - 优点：使用
vector存储元素时，当遇到在数组头部位置插入元素的时候，需要先将所有的元素后移一位，再将新元素插入首位，这样操作的话时间复杂度为O(N)。相同的情况，如果使用双端队列存储元素，可以直接在首部插入元素，时间复杂度为O(1)。
函数
- push_front() —— 在双端队列的队头加入元素
- push_back() —— 在双端队列的队尾加入元素
- pop_front() —— 在双端队列的队头删除元素
- pop_back() —— 在双端队列的队尾删除元素
- 以上函数如果不记得，可以在需要使用时前往C++ Reference中查找
deque的基本操作(插入、删除及遍历)
#include <iostream>
#include <deque>
using namespace std;
void print(deque<int> d)//输出函数
{
for (int i = 0;i < d.size();i++)
cout << d[i] << " ";
cout << endl;
}
int main()
{
deque<int> d(5,100);//双端队列中包含5个100
print(d);//100 100 100 100 100
d.push_front(521);
d.push_back(521);//在队首和队尾都插入元素
print(d);//521 100 100 100 100 100 521
d.pop_back();
d.pop_front();//删除队首和队尾元素
print(d);//100 100 100 100 100
//迭代器遍历双端队列
deque<int>::iterator it;
for (it = d.begin();it != d.end();it++)
cout << *it << " ";//100 100 100 100 100
cout << endl;
for (it = d.begin();it < d.end();it += 2)
cout << *it << " ";//100 100 100
cout << endl;
return 0;
}
例题(原题链接)
题目描述
想想双向链表……双向队列的定义差点儿相同，也就是说一个队列的队尾同一时候也是队首。两头都能够做出队，入队的操作。
如今给你一系列的操作。请输出最后队列的状态；
命令格式：
LIN X (X表示一个整数）命令代表左边进队操作；
RIN X 表示右边进队操作；
ROUT 表示右边出队操作；
LOUT 表示从左边出队操作。
输入
第一行包括一个整数M(M<=10000)，表示有M个操作；下面M行每行包括一条命令；
命令可能不合法，对于不合法的命令，请在输出中处理；
输出
输出的第一行包括队列进行了M次操作后的状态。从左往右输出，每两个之间用空格隔开。
下面若干行处理不合法的命令（假设存在）；
对于不合法的命令。请输出一行X ERROR
当中X表示是第几条命令；
样例输入
8
LIN 5
RIN 6
LIN 3
LOUT
ROUT
ROUT
ROUT
LIN 3
样例输出
3
7 ERROR
解题思路：模拟过程即可
AC代码：
#include <iostream>
#include <deque>
using namespace std;
const int N = 10010;
int x,cnt,acnt;//cnt用来记录命令的编号,acnt是错误命令的编号在数组中的下标
int a[N];//存储错误命令的编号
deque<int> d;
int main()
{
deque<int>::iterator it;
int t; cin >> t;
string s;//表示接受的命令
while (t --)
{
cin >> s;
if (s == "LIN")
{
cnt++;
cin >> x;
d.push_front(x);
}
else if (s == "RIN")
{
cnt++;
cin >> x;
d.push_back(x);
}
else if (s == "LOUT")
{
cnt++;
if (d.empty()) a[acnt++] = cnt;//队空
else d.pop_front();//队列左端元素出队
}
else if (s == "ROUT")
{
cnt++;
if (d.empty()) a[acnt++] = cnt;//队空
else d.pop_back();//队列右端元素出队
}
}
//遍历deque
for (it = d.begin();it != d.end();it++) cout << *it << " ";
cout << endl;
//遍历数组
for (int i = 0;i < acnt;i++)
{
cout << a[i] << " " << "ERROR";
cout << endl;
}
return 0;
}
