#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。