Recursive solution to sort a stack
Given a stack, sort it using recursion. The use of any other data structures (like containers in STL or Collections in Java) is not allowed.
For example,
Stack before sorting : 5 | -2 | 9 | -7 | 3 where 3 is the top element
Stack after sorting : -7 | -2 | 3 | 5 | 9 where 9 is the top element
Stack after sorting : -7 | -2 | 3 | 5 | 9 where 9 is the top element
The idea is simple – recursively remove values from the stack until the stack becomes empty and then insert those values (from the call stack) back into the stack in a sorted position.
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <iostream> #include <stack> #include <vector> using namespace std; // Insert the given key into the sorted stack while maintaining its sorted order. // This is similar to the recursive insertion sort routine void sortedInsert(stack<int> &stack, int key) { // base case: if the stack is empty or // the key is greater than all elements in the stack if (stack.empty() || key > stack.top()) { stack.push(key); return; } /* We reach here when the key is smaller than the top element */ // remove the top element int top = stack.top(); stack.pop(); // recur for the remaining elements in the stack sortedInsert(stack, key); // insert the popped element back into the stack stack.push(top); } // Recursive method to sort a stack void sortstack(stack<int> &stack) { // base case: stack is empty if (stack.empty()) { return; } // remove the top element int top = stack.top(); stack.pop(); // recur for the remaining elements in the stack sortstack(stack); // insert the popped element back into the sorted stack sortedInsert(stack, top); } void printStack(stack<int> stack) { while (!stack.empty()) { cout << stack.top() << " "; stack.pop(); } cout << endl; } int main() { vector<int> list = { 5, -2, 9, -7, 3 }; stack<int> stack; for (int i: list) { stack.push(i); } cout << "Stack before sorting: "; printStack(stack); sortstack(stack); cout << "Stack after sorting: "; printStack(stack); return 0; } |
Output:
Stack before sorting: 3 -7 9 -2 5
Stack after sorting: 9 5 3 -2 -7
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
import java.util.Arrays; import java.util.List; import java.util.Stack; class Main { // Insert the given key into the sorted stack while maintaining its // sorted order. This is similar to the recursive insertion sort routine. public static void sortedInsert(Stack<Integer> stack, int key) { // base case: if the stack is empty or // the key is greater than all elements in the stack if (stack.isEmpty() || key > stack.peek()) { stack.push(key); return; } /* We reach here when the key is smaller than the top element */ // remove the top element int top = stack.pop(); // recur for the remaining elements in the stack sortedInsert(stack, key); // insert the popped element back into the stack stack.push(top); } // Recursive method to sort a stack public static void sortStack(Stack<Integer> stack) { // base case: stack is empty if (stack.isEmpty()) { return; } // remove the top element int top = stack.pop(); // recur for the remaining elements in the stack sortStack(stack); // insert the popped element back into the sorted stack sortedInsert(stack, top); } public static void main(String[] args) { List<Integer> list = Arrays.asList(5, -2, 9, -7, 3); Stack<Integer> stack = new Stack<>(); stack.addAll(list); System.out.println("Stack before sorting: " + stack); sortStack(stack); System.out.println("Stack after sorting: " + stack); } } |
Output:
Stack before sorting: [5, -2, 9, -7, 3]
Stack after sorting: [-7, -2, 3, 5, 9]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
from collections import deque # Insert the given key into the sorted stack while maintaining its sorted order. # This is similar to the recursive insertion sort routine def sortedInsert(stack, key): # base case: if the stack is empty or # the key is greater than all elements in the stack if not stack or key > stack[-1]: stack.append(key) return ''' We reach here when the key is smaller than the top element ''' # remove the top element top = stack.pop() # recur for the remaining elements in the stack sortedInsert(stack, key) # insert the popped element back into the stack stack.append(top) # Recursive method to sort a stack def sortStack(stack): # base case: stack is empty if not stack: return # remove the top element top = stack.pop() # recur for the remaining elements in the stack sortStack(stack) # insert the popped element back into the sorted stack sortedInsert(stack, top) if __name__ == '__main__': A = [5, -2, 9, -7, 3] stack = deque(A) print('Stack before sorting:', list(stack)) sortStack(stack) print('Stack after sorting:', list(stack)) |
Output:
Stack before sorting: [5, -2, 9, -7, 3]
Stack after sorting: [-7, -2, 3, 5, 9]
The time complexity of the above solution is O(n2) and requires O(n) implicit space for the call stack, where n is the total number of elements in the stack.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)