#STL007. 双端传送带
双端传送带
双端传送带
传送带上有一列整数标记,初始没有任何标记。你需要按给定顺序执行左右两端的操作,并记录查询与取出操作的结果。翻转后,所有标记的先后顺序都要反过来,接下来的“左端”和“右端”按翻转后的顺序理解。
支持以下指令:
| 指令 | 行为 | 输出 |
|---|---|---|
LEFT x |
在左端放入一个值为 x 的标记 | 无 |
RIGHT x |
在右端放入一个值为 x 的标记 | |
POPL |
取出并删除左端标记 | 被取出的值;空时为 EMPTY |
POPR |
取出并删除右端标记 | |
FRONT |
查询左端标记,不删除 | 该值;空时为 EMPTY |
BACK |
查询右端标记,不删除 | |
REVERSE |
翻转整列标记 | 无 |
标记可以重复,值为 0 也表示一个普通标记。对空传送带取出或翻转,传送带仍为空。
输入格式
第一行一个整数 q,表示指令数。接下来 q 行,每行一条上述指令。
输出格式
按指令出现顺序输出所有 POPL、POPR、FRONT、BACK 的结果,每个结果占一行。放入和翻转不输出;如果整个输入没有需要输出的指令,输出为空。
数据范围
- 1 ≤ q ≤ 200000。
- −10⁹ ≤ x ≤ 10⁹。
- 对每条
REVERSE,记执行前传送带的长度为 L,所有这些 L 的总和不超过 2000000。 - 输入保证指令格式合法。
样例 1
输入:
15
FRONT
LEFT 4
RIGHT 9
LEFT -2
BACK
REVERSE
FRONT
POPL
POPR
BACK
POPL
POPR
REVERSE
LEFT 0
FRONT
输出:
EMPTY
9
9
9
-2
4
4
EMPTY
0
解释:前三次放入后,从左到右为 [-2, 4, 9],第一次 BACK 输出 9。翻转得到 [9, 4, -2],随后分别取出 9 和 −2。再取出唯一的 4 后,传送带为空;末尾放入 0,FRONT 输出 0。
样例 2
输入:
10
RIGHT 1
RIGHT 1
REVERSE
BACK
POPL
POPR
FRONT
REVERSE
LEFT -1
BACK
输出:
1
1
1
EMPTY
-1
解释:两个值为 1 的标记分别存在,翻转不会合并它们。依次取出两端后,FRONT 输出 EMPTY。之后放入 −1,BACK 输出 −1。