200. Design a Circular Deque
The last problem, and it brings the whole topic together: a deque of fixed
capacity c, stored in one array, with both ends wrapping around.
Every operation must be constant time and no memory may be allocated beyond the array. That means the front index must be able to move BACKWARDS off the start of the array and reappear at the end, the same wraparound as the circular queue, now in both directions.
Print Full when an add is rejected, and Empty when a read or removal finds nothing.
Constraints - `1 ≤ c ≤ 200000` - `1 ≤ q ≤ 200000` - `-1000000 ≤ x ≤ 1000000`
Input
The first line contains two integers c and q, the capacity and 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
- 6, print the back value
Output
Print one line for each operation from 3 to 6, the value, or Empty.
Print Full on its own line for each 1 or 2 rejected because the deque is at capacity.
A successful add prints nothing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.