Doggie will run following operations on an original queue containing numbers from 1 to n inclusively:
The funniest thing is that the printed numbers are 1, 2, 3, …., n in ascending order, then find out the original queue.
There are two methods to handle this problem:
- reverse the whole process using deque from the last to the first;
- re-run the whole operations and meantime recording the positions and then set numbers by the positions accordingly.
According to the operations, we can easily reverse the whole operations and retrieve the original.
By recording the positions of the numbers and repeating the operations above, we then can set the corresponding elements to retrieve the original queue, which is more compatible but less efficient taking up extra O(n) space.
Always welcome new ideas and
practical tricks, just leave them in the comments!