Sort a Stack Using Recursion: Codes with Visualization
Sasank is a Technical Content Writer with a strong background in competitive programming. He has solved nearly 1500 problems on LeetCode and achieved top rankings in LeetCode Weekly Contests, including global ranks of 171, 196, 206, 308, 352, and more. His expertise in algorithms and problem-solving is also reflected in his active participation on platforms like Codeforces. Sasank enjoys sharing his technical knowledge and helping others learn by creating clear and accessible content.
Problem Statement
Given a stack, sort it using recursion. You can only use the following standard stack operations:
- push(x): Push element x onto the stack
- pop(): Remove and return the top element from the stack
- peek() or top(): Return the top element without removing it
- isEmpty(): Return true if the stack is empty, false otherwise
You are not allowed to use any other data structures like arrays or another stack to solve this problem.
Recursive Approach
Explanation
The brute force approach for sorting a stack using only recursion involves removing elements one by one, inserting each element in its correct position in the already sorted stack.
The basic idea is:
- If the stack is empty, simply return
- If not, remove the top element
- Recursively sort the remaining stack
- Insert the removed element back into the sorted stack at its correct position
To insert an element in the correct position of a sorted stack, we:
- If the stack is empty or the element is greater than the top element, simply push it
- Otherwise, temporarily remove the top element, recursively insert our element, then push the removed element back
The beauty of this approach is its simplicity, though it's not the most efficient solution.
Time Complexity: O(n²) - In the worst case, we need to move n elements for each of the n elements.
Space Complexity: O(n) - Due to the recursive call stack.
Code (Python)
def sortStack(stack):
# Base case: if stack is empty
if not stack:
return
# Remove the top element
temp = stack.pop()
# Sort the remaining stack
sortStack(stack)
# Insert the removed element back in sorted position
insertSorted(stack, temp)
return stack
def insertSorted(stack, element):
# Base case: if stack is empty or element is greater than top
if not stack or element > stack[-1]:
stack.append(element)
return
# Remove the top element
temp = stack.pop()
# Recursively insert the element
insertSorted(stack, element)
# Put back the removed element
stack.append(temp)
# Example usage
stack = [34, 3, 31, 98, 92, 23]
sortStack(stack)
print(stack) # Output: [3, 23, 31, 34, 92, 98]Code (C++)
#include <iostream>
#include <stack>
using namespace std;
// Function to insert an element in sorted position
void insertSorted(stack<int>& s, int element) {
// Base case: if stack is empty or element is greater than top
if (s.empty() || element > s.top()) {
s.push(element);
return;
}
// Remove the top element
int temp = s.top();
s.pop();
// Recursively insert the element
insertSorted(s, element);
// Put back the removed element
s.push(temp);
}
// Function to sort the stack
void sortStack(stack<int>& s) {
// Base case: if stack is empty
if (s.empty()) {
return;
}
// Remove the top element
int temp = s.top();
s.pop();
// Sort the remaining stack
sortStack(s);
// Insert the removed element back in sorted position
insertSorted(s, element);
}
// Utility function to print a stack
void printStack(stack<int> s) {
if (s.empty()) return;
int x = s.top();
s.pop();
// Print elements in reverse order
printStack(s);
cout << x << " ";
// Push the element back
s.push(x);
}
int main() {
stack<int> s;
s.push(34);
s.push(3);
s.push(31);
s.push(98);
s.push(92);
s.push(23);
cout << "Original stack: ";
printStack(s);
sortStack(s);
cout << "\nSorted stack: ";
printStack(s);
return 0;
}
Code (Java)
import java.util.Stack;
public class SortStack {
// Function to sort the stack
public static void sortStack(Stack<Integer> stack) {
// Base case: if stack is empty
if (stack.isEmpty()) {
return;
}
// Remove the top element
int temp = stack.pop();
// Sort the remaining stack
sortStack(stack);
// Insert the removed element back in sorted position
insertSorted(stack, temp);
}
// Function to insert an element in sorted position
private static void insertSorted(Stack<Integer> stack, int element) {
// Base case: if stack is empty or element is greater than top
if (stack.isEmpty() || element > stack.peek()) {
stack.push(element);
return;
}
// Remove the top element
int temp = stack.pop();
// Recursively insert the element
insertSorted(stack, element);
// Put back the removed element
stack.push(temp);
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(34);
stack.push(3);
stack.push(31);
stack.push(98);
stack.push(92);
stack.push(23);
System.out.println("Original stack: " + stack);
sortStack(stack);
System.out.println("Sorted stack: " + stack);
}
}
Optimized Approach
Explanation
For this particular problem, there isn't a significantly more optimized approach than our brute force solution if we strictly follow the constraints of using only recursion and the standard stack operations.
However, we can make a slight optimization in how we think about the problem. Instead of removing elements one by one and then inserting them back in sorted order, we can use a "merge sort" inspired approach:
- Divide the stack in half
- Sort each half recursively
- Merge the two sorted halves
But implementing this with only stack operations and recursion would be complex and likely wouldn't improve the time complexity.
In practice, the brute force approach we discussed is the most straightforward solution for this specific problem, especially given the constraints.
If we were allowed to use additional data structures, we could achieve O(n log n) time complexity using:
- Convert the stack to an array
- Sort the array using a sorting algorithm like merge sort
- Convert the sorted array back to a stack
Since we're limited to recursion and stack operations, our original solution remains optimal.
Time Complexity: O(n²)
Space Complexity: O(n) for the recursive call stack
Lets consider our stack [3, 23, 34, 92, 98], Lets See what happens when we insert 31 into it
First, we check if 98 < 31. Since 98 < 31, we move 98 to the result stack
Next, we check if 92 < 31. Since 92 < 31, we move 92 to the result stack.
Now we check if 34 < 31. Since 34 > 31, we move 34 to temporary storage.
Now that we've found the correct position, we insert 31 onto the result stack.
Next, we move the element 34 from temporary storage back to the result stack.
We continue by moving 23 , 3 to the result stack.
<visualization-box>
Code (Python)
def sortStack(stack):
# Base case: if stack is empty
if not stack:
return
# Remove the top element
temp = stack.pop()
# Sort the remaining stack
sortStack(stack)
# Insert the removed element back in sorted position
insertSorted(stack, temp)
return stack
def insertSorted(stack, element):
# Base case: if stack is empty or element is greater than top
if not stack or element > stack[-1]:
stack.append(element)
return
# Remove the top element
temp = stack.pop()
# Recursively insert the element
insertSorted(stack, element)
# Put back the removed element
stack.append(temp)
# Example usage
stack = [34, 3, 31, 98, 92, 23]
sortStack(stack)
print(stack) # Output: [3, 23, 31, 34, 92, 98]Code (C++)
#include <iostream>
#include <stack>
using namespace std;
// Function to insert an element in sorted position
void insertSorted(stack<int>& s, int element) {
// Base case: if stack is empty or element is greater than top
if (s.empty() || element > s.top()) {
s.push(element);
return;
}
// Remove the top element
int temp = s.top();
s.pop();
// Recursively insert the element
insertSorted(s, element);
// Put back the removed element
s.push(temp);
}
// Function to sort the stack
void sortStack(stack<int>& s) {
// Base case: if stack is empty
if (s.empty()) {
return;
}
// Remove the top element
int temp = s.top();
s.pop();
// Sort the remaining stack
sortStack(s);
// Insert the removed element back in sorted position
insertSorted(s, element);
}
// Utility function to print a stack
void printStack(stack<int> s) {
if (s.empty()) return;
int x = s.top();
s.pop();
// Print elements in reverse order
printStack(s);
cout << x << " ";
// Push the element back
s.push(x);
}
int main() {
stack<int> s;
s.push(34);
s.push(3);
s.push(31);
s.push(98);
s.push(92);
s.push(23);
cout << "Original stack: ";
printStack(s);
sortStack(s);
cout << "\nSorted stack: ";
printStack(s);
return 0;
}
Code (Java)
import java.util.Stack;
public class SortStack {
// Function to sort the stack
public static void sortStack(Stack<Integer> stack) {
// Base case: if stack is empty
if (stack.isEmpty()) {
return;
}
// Remove the top element
int temp = stack.pop();
// Sort the remaining stack
sortStack(stack);
// Insert the removed element back in sorted position
insertSorted(stack, temp);
}
// Function to insert an element in sorted position
private static void insertSorted(Stack<Integer> stack, int element) {
// Base case: if stack is empty or element is greater than top
if (stack.isEmpty() || element > stack.peek()) {
stack.push(element);
return;
}
// Remove the top element
int temp = stack.pop();
// Recursively insert the element
insertSorted(stack, element);
// Put back the removed element
stack.push(temp);
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(34);
stack.push(3);
stack.push(31);
stack.push(98);
stack.push(92);
stack.push(23);
System.out.println("Original stack: " + stack);
sortStack(stack);
System.out.println("Sorted stack: " + stack);
}
}Conclusion
We've explored how to sort a stack using recursion while sticking to its basic operations. The solution relies on two key recursive functions:
1. sortStack() - Removes elements one by one and sorts the remaining stack
2. insertSorted() - Places elements back in their correct sorted positions
This problem showcases the power of recursive thinking. By breaking down the complex task of sorting into smaller, manageable sub-problems, we can create an elegant solution despite the limited operations available.
While our solution has a time complexity of O(n²), it's important to note that given the constraints of the problem, this is a reasonable approach. Learning to solve such problems with constrained resources is a valuable skill for any programmer, especially when facing technical interviews.
