Solution: Sort Values in a Stack
Let's solve Sort Values in a Stack problem.
Statement
Given a stack of integers, stack, sort its elements in ascending order. In the resulting stack, the smallest element should be at the top.
Constraints:
stack.lengthstack[i]
Solution 1: Using a temporary stack
The solution takes an iterative approach towards the problem. It starts by initializing a temporary stack to facilitate sorting. While the main stack contains elements, we compare each element with the top of the temporary stack. If the current popped element is larger or equal, we add it to the temporary stack; otherwise, we store it and rearrange the remaining elements of the main and temporary stack until the temporary stack’s top is smaller than the current element. The stored element is then pushed onto the temporary stack, and the steps are repeated until the main stack is empty. Finally, the temporary stack holds elements in descending order, which we transfer back to the main stack to achieve a sorted ascending order.
Let’s look at the illustration below to better understand the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.