180. Deque Operations
Core1000 ms256 MBSolved by 0%
A DEQUE — a double-ended queue — allows adding and removing at BOTH ends, all in constant time.
That makes it a queue and a stack at once, and it is exactly what a sliding-window problem needs later in this topic.
Print Empty for any read or removal on an empty deque, and carry on.
Constraints - `1 ≤ q ≤ 200000` - `-1000000 ≤ x ≤ 1000000`
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 at the FRONT
- 2 x — add x at the BACK
- 3 — remove the front value and print it
- 4 — remove the back value and print it
- 5 — print the front value without removing it
- 6 — print the back value without removing it
Output
Print one line for each operation from 3 to 6 — the value, or Empty.
Operations 1 and 2 print nothing.
Input6
2 1
2 2
1 0
5
6
3
Output0
2
0
Noteadds at both ends and reads both ends
Input2
3
4
OutputEmpty
Empty
Noteremoves from both ends of an empty deque
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution