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 and case2, 1<=OP<=1000
For case3, 1<=OP<=10000, For each S operation, O(n) is also accepted.
For case4 and case5, 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.
For RH and RT operation: if the list is empty, print a blank line.