192. A Queue That Knows Its Maximum
Build a queue that can also report its largest value at any moment, without scanning through it.
This is the same idea as the min-stack from the previous topic, but harder: a stack only changes at one end, so one parallel stack was enough. A queue changes at BOTH ends, and the value that has to be discarded is not the one that just arrived.
Print Empty if the maximum is asked for while the queue holds nothing.
Constraints - `1 ≤ q ≤ 200000` - `-1000000000 ≤ x ≤ 1000000000`
Input
The first line contains an integer q, the number of operations.
Each of the next q lines is one operation:
- 1 x, add x to the back
- 2, remove the front value, printing nothing
- 3, print the largest value currently in the queue
Output
Print one line for each 3 operation, the largest value, or Empty.
Operations 1 and 2 print nothing. A 2 on an empty queue is ignored.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.