Input a series of numbers and write them out to a queue in ascending order as follows:
1. Each input number can be either pushed into a staging stack or added to the output queue.
2. Use a variable nextOut to keep track of the next number to be added to the output queue. Initialize nextOut to a value of 1.
3. If an input number is equal to nextOut, it is added to the output queue. nextOut is then incremented by 1. Numbers that have been pushed into the staging stacks must now be examined to see if they can be moved to the output queue. (e.g. a number at the top of a stack can be moved to the queue if it is equal to nextOut).
4. If an input number is not equal to nextOut, it must be pushed into a staging stack.
5. If no staging stack exists, create a new one and push in the number.
6. If there is only one staging stack, compare the input number (u) against the number (v) at the top of the stack. If u is less than v, push u into the stack. Otherwise create another new stack and push the input number in it.
7. If more than one staging stacks have been created, than find all the stack(s) where the top element(s) (v) are greater than the input number (u). Push u into the stack with the smallest v.
8. Once all the input numbers have been read in (i.e. either added to the output queue or pushed into the staging stacks), iteratively peek the stacks and pop the smallest number and add it to an output queue of numbers. Continue until all the staging stacks are empty.
Obviously you can process the numbers by creating a separate stack for each input number, without any staging. However, your objective is to use the smallest number of (staging) stacks.
Each number can only be moved once into one of the staging stacks or moved directly to the output queue. If a number is moved into a staging stack then it can only be moved once into the output queue.
Since the amount of input numbers to be pushed into each stack is unknown, use linked stacks instead of sequential stacks.
*Please make this program as simple as possible using stacks and queues.
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
I need this to work on any Windows system.