Prompt:

Sort a Stack class in ascending order without using any other data structure other than one more Stack. Solve it in strictly linear space complexity. You have access to the push, pop and isEmpty methods on the Stack.

Go!

First off, what is a Stack? To refresh your memory, a Stack resembles dirty dishes in a sink. When you need to wash them, you start with the dishes on top rather than the dishes on the bottom. So, the first dirty dish to enter the sink gets washed last.

There are three important methods on Stack:

• Push(value): Adds the value to the top of the Stack
• Pop(): Removes the value at the top of the Stack, and returns the value
• isEmpty(): Returns whether the Stack has any items

Setup

• Inputs: An unsorted Stack with some integers
• Outputs: A sorted Stack (largest integers on top, smallest at bottom)
• Constraints: Only use another Stack to help sort, and variables when required

My method involves popping a value from one Stack, comparing it to a variable, and selectively pushing it to another Stack. When the first Stack is empty, we can run the same Algorithmthm on the second Stack and selectively push values to the first Stack. When there are no more items to push, we can successfully say that we have sorted the Stack.

If you did not understand the solution from the paragraph above, do not fear, the rest of this article is for you!

Solution

Let us use an example problem to illustrate this technique.

Also, we have three variables, i, that starts at 0 , comparison, that starts at undefined, and done that starts as false.

Start: Full stack - Stack A, while empty stack is Stack B.

1. Set done to be true at the beginning of every loop.
2. pop() on Stack A. This returns 9. Stack now has only 4 elements, since 9 is removed from the Stack.
3. Assign 9 to comparison.
4. If i is divisible by 2:
   • Compare 4 to comparison (9), and push the smaller value in the other Stack (Stack B).
   • We place the larger value in the comparison variable.
5. If i is not divisible by 2:
   • Compare 4 to comparison (9), and push the larger value in the other Stack (Stack B).
   • We place the smaller value in the comparison variable.
6. Repeat process over the entire Stack A. If the comparisonvariable changes at any time, set done to be false
7. When Stack A is empty, isEmpty(Stack A) returns true.
8. i is incremented. In this case, i is 1.
9. If done is true, we push comparison value to the recently filled Stack. For i % 2 = 0, it is Stack B, while for i % 2 = 1, it is Stack A.
10. If i is not divisible by 2:
    • Repeat 1 through 7.
    • Push value in comparison variable in Stack A.
    • Move items from Stack B to Stack A.
11. If i is divisible by 2:
    • Repeat 1 through 7.
    • Push value in comparison variable in Stack B.
    • Move items from Stack A to Stack B.

After the first pass, the stacks should look as follows:

i = 1, comparison = 12

After the second pass, the stacks should look as follows:

i = 2, comparison = 4

After the third pass, the stacks should look as follows:

i = 3, comparison = 12

After the fourth pass, the stacks should look as follows:

i = 4, comparison = 4

Since done stays as true through the entire pass, we push the value in comparison to Stack A.

Eventually, it looks like this:

And voila, sort for a Stack has been accomplished!

Have questions or suggestions? Feel free to open an issue on GitHub.

Cheers!