Maintain a doubly linked list, which supports the following operations:
(1) IH i : Insert a new integer i to the head of the list.
(2) IT i : Insert a new integer i to the tail of the list.
(3) RH : Print and remove the element in the head of the list. If the list is empty, print a blank line.
(4) RT : Print and remove the element in the tail of the list. If the list is empty, print a blank line.
(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.
To improve the performance, it is suggested that three pointers be maintained in case4: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.
There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains OP operations, and it is terminated by end-of-file (EOF). You may assume that i is a nonnegative integer not greater then 100000. The list is initially empty.
For case1, 1<=OP<=100, test case contains only IT and RH operation. That is, you may use “queue” to pass this test case. And guaranteed that RH operation only appears when the list is not empty.
For case2, 1<=OP<=1000, test case contains only IH, IT, RH, RT operation. That is, no S operation will appear in this test case.
For case3, 1<=OP<=10000, test case contains all kinds of operation. For each S operation, O(n) is also accepted.
For case4, 1<=OP<=500000, each operation should be done in O(1).
For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
Recall for case2~4, for RH and RT operation: if the list is empty, print a blank line.