A "deque" is a data structure which allows constant time insertion and removal at both the front and back ends. In this problem, you will be given a int[] data, and asked to sort the numbers contained therein using the following algorithm. For each number x in data, you must do exactly one of the following:
- 1. Push x onto the front end of an existing deque.
- 2. Push x onto the back end of an existing deque.
- 3. Create a new deque with x as its only element.
You must process each number in data in the order they are given. It is not permissible to skip a number temporarily and process it at a later time. It is also not permissible to insert a number into the middle of an existing deque; only front and back insertions are allowed. To make things easier, data will not contain duplicate elements.
Once all the numbers have been processed, if you have created your deques wisely, you should be able to create a single, sorted list by placing the resulting deques on top of each other in an order of your choice. Your method should return the minimum number of deques needed for this to be possible. |