Suppose a stack is given having values:
15
-8
1
-5
10
I want to sort it so sorted stack should look like:
15
10
1
-5
-8
Category: Data Structure And Algorithms | Tags: C# |
Suppose a stack is given having values:
15
-8
1
-5
10
I want to sort it so sorted stack should look like:
15
10
1
-5
-8
Answers:
Using recursion:
Sorting stack is similar to sort an array using insertion sort, in insertion sort we do insert elements at their correct position. But in stack we cannot move elements like we can in array so first we have to pop all the elements then we can start inserting them back one by one.
When we insert elements back one by one we check if peek element is smaller than current element or not, if yes we simply push the element else we pop the top element from stack and compare next top element with element we are trying to insert, we do same until we find correct position of the element.
The stack is: 15 (top), -8, 1, -5, 10 (bottom) and suppose now all elements are popped out and we will insert them back one by one (in stack last popped out element will be inserted back first so 10 will be inserted first and then -5 and so on):
10 -> 10
-5, 10 -> 10, -5
1, 10, -5 -> 10, 1, -5
-8, 10,1,-5 -> 10, 1, -5, -8
15, 10, 1, -5, -8 -> 15, 10, 1, -5, -8
Go through below implementation:
Output:
Sorted stack:
15
10
1
-5
-8
Using temporary stack:
Same concept is used of insertion sort only temporary stack is used instead of recursion.
Sorted stack:
15
10
1
-5
-8