Deque — Operations at Both Ends

Practice this coding question on Coding Gurukul.

Problem statement

Implement a deque that starts empty. A deque allows insertion and removal at both ends. - PUSH_FRONT x / PUSH_BACK x: add x at the specified end. - POP_FRONT / POP_BACK: remove and print the value at that end. - FRONT / BACK: print the value at that end without removing it. - SIZE: print the number of values. Print EMPTY when a pop or inspection is requested on an empty deque. Insertions produce no output. Support O(1) amortized time per command. Worked example The insertions create [2, 5, 9]. POP_BACK prints 9 and POP_FRONT prints 2. Only 5 remains, so FRONT and BACK both print 5, and SIZE prints 1.

Input format

First line: q. Next q lines contain one command described above.

Output format

Print one line for each pop, inspection or SIZE command.

Constraints

1 <= q <= 100000; -10^9 <= x <= 10^9. At least one output command.

Sample input

8
PUSH_BACK 5
PUSH_FRONT 2
PUSH_BACK 9
POP_BACK
POP_FRONT
FRONT
BACK
SIZE

Sample output

9
2
5
5
1

Sign in to run or submit a solution in C++, Java or Python.