SDUTOJ 1466 双向队列（std::Deque的应用）

Problem Description

      想想双向链表……双向队列的定义差不多，也就是说一个队列的队尾同时也是队首；两头都可以做出队，入队的操作。 现在给你一系列的操作，请输出最后队列的状态； 命令格式： LIN X  X表示一个整数，命令代表左边进队操作； RIN X  表示右边进队操作； ROUT LOUT   表示出队操作；

Input

第一行包含一个整数M(M<=10000)，表示有M个操作； 以下M行每行包含一条命令； 命令可能不合法，对于不合法的命令，请在输出中处理；

Output

输出的第一行包含队列进行了M次操作后的状态，从左往右输出，每两个之间用空格隔开； 以下若干行处理不合法的命令（如果存在）； 对于不合法的命令，请输出一行X ERROR 其中X表示是第几条命令；

Sample Input

8 LIN 5 RIN 6 LIN 3 LOUT ROUT ROUT ROUT LIN 3

Sample Output

3 7 ERROR

根据题给设定，很明显这是一个双端队列的应用。

由于自己实现这个结构太麻烦，所以直接用STL内的deque(double ended queue)就好了

下面对它的结构进行简要说明：

_Map是一个映射函数，不同于std::map，这里的_Map单纯就是一个概念性的起到“主控制区”的一个设定。也就是说_Map每一个小块都对应一段大块空间，从而实现各种操作的需要。

所以有如下的思路：

利用deque进行模拟即可，注意越界判定（也就是ERROR操作的判断） #include <iostream> #include <cstdio> #include <bits/stdc++.h> #include <map> #include <algorithm> #include <stack> #include <iomanip> #include <cstring> #include <cmath> #define DETERMINATION main #define lldin(a) scanf_s("%lld", &a) #define println(a) printf("%lld\n", a) #define reset(a, b) memset(a, b, sizeof(a)) const int INF = 0x3f3f3f3f; using namespace std; const double PI = acos(-1); typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int mod = 1000000007; const int tool_const = 19991126; const int tool_const2 = 33; inline ll lldcin() { ll tmp = 0, si = 1; char c; c = getchar(); while (c > '9' || c < '0') { if (c == '-') si = -1; c = getchar(); } while (c >= '0' && c <= '9') { tmp = tmp * 10 + c - '0'; c = getchar(); } return si * tmp; } ///Untersee Boot IXD2(1942) /**Although there will be many obstructs ahead, the desire for victory still fills you with determination..**/ /**Last Remote**/ string command; int errors[50000]; deque<ll>dq; ll m, tmp, cnt2 = 0; int DETERMINATION() { cin >> m; for (int i = 1; i <= m; i++) { cin.get(); cin >> command; //cout << command << " " << tmp << endl; if (command[0] == 'L'&&command[1] == 'I') { cin >> tmp; dq.push_front(tmp); } else if (command[0] == 'R'&&command[1] == 'I') { cin >> tmp; dq.push_back(tmp); } else if (command[0] == 'L'&&command[1] == 'O') { if (!dq.empty())//注意越界判定，否则会因为题给的错误操作而Runtime error dq.pop_front(); else errors[cnt2++] = i; } else if (command[0] == 'R'&&command[1] == 'O' ) { if (!dq.empty()) dq.pop_back(); else errors[cnt2++] = i; } //cout << cnt2 << endl; } ll tmp2, cnt = 0; while (!dq.empty()) { tmp2 = dq.front(); dq.pop_front(); if (cnt == 0) cout << tmp2; else cout << " " << tmp2; cnt++; } cout << endl; for (int i = 0;i < cnt2; i++) cout << errors[i] << " ERROR" << endl; return 0; }