Given a stack, the task is to sort it using recursion.
Example:
Input: elements present in stack from top to bottom -3 14 18 -5 30
Output: 30 18 14 -3 -5
Explanation: The given stack is sorted know 30 > 18 > 14 > -3 > -5Input: elements present in stack from top to bottom 1 2 3
Output: 3 2 1
Explanation: The given stack is sorted know 3 > 2 > 1
How to Sort a Stack Using Stack
The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order. and then print the stack
Illustration:
Below is the illustration of above approach
- Let given stack be
-3
14 18 -5 30
- Let us illustrate sorting of stack using the above example:
First pop all the elements from the stack and store popped element in the variable ‘temp’. After popping all the elements function’s stack frame will look like this:
-3 stack frame 1 14 stack frame 2 18 stack frame 3 -5 stack frame 4 30 stack frame 5
- Now stack is empty so function insert in sorted order is called and it inserts 30 (from stack frame 5) at the bottom of the stack. Now stack looks like the below:
30
- Now next element -5 (from stack frame 4) is picked. Since -5 < 30, -5 is inserted at the bottom of the stack. Now stack becomes:
30 -5
- Next 18 (from stack frame 3) is picked. Since 18 < 30, 18 is inserted below 30. Now stack becomes:
30 18 -5
- Next 14 (from stack frame 2) is picked. Since 14 < 30 and 14 < 18, it is inserted below 18. Now stack becomes:
30 18 14 -5
- Now -3 (from stack frame 1) is picked, as -3 < 30 and -3 < 18 and -3 < 14, it is inserted below 14. Now stack becomes:
30 18 14 -3 -5
Follow the steps mentioned below to implement the idea:
- Create a stack and push all the elements in it.
- Call sortStack(), which will pop an element from the stack and pass the popped element to function sortInserted(), then it will keep calling itself until the stack is empty.
- Whenever sortInserted() is called it will insert the passed element in stack in sorted order.
- Print the stack
Below is the implementation of the above approach:
C++
// C++ program to sort a stack using recursion#include <iostream>using namespace std;// Stack is represented using linked liststruct stack { int data; struct stack* next;};// Utility function to initialize stackvoid initStack(struct stack** s) { *s = NULL; }// Utility function to check if stack is emptyint isEmpty(struct stack* s){ if (s == NULL) return 1; return 0;}// Utility function to push an item to stackvoid push(struct stack** s, int x){ struct stack* p = (struct stack*)malloc(sizeof(*p)); if (p == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } p->data = x; p->next = *s; *s = p;}// Utility function to remove an item from stackint pop(struct stack** s){ int x; struct stack* temp; x = (*s)->data; temp = *s; (*s) = (*s)->next; free(temp); return x;}// Function to find top itemint top(struct stack* s) { return (s->data); }// Recursive function to insert an item x in sorted wayvoid sortedInsert(struct stack** s, int x){ // Base case: Either stack is empty or newly inserted // item is greater than top (more than all existing) if (isEmpty(*s) or x > top(*s)) { push(s, x); return; } // If top is greater, remove the top item and recur int temp = pop(s); sortedInsert(s, x); // Put back the top item removed earlier push(s, temp);}// Function to sort stackvoid sortStack(struct stack** s){ // If stack is not empty if (!isEmpty(*s)) { // Remove the top item int x = pop(s); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); }}// Utility function to print contents of stackvoid printStack(struct stack* s){ while (s) { cout << s->data << " "; s = s->next; } cout << "\n";}// Driver codeint main(void){ struct stack* top; initStack(&top); push(&top, 30); push(&top, -5); push(&top, 18); push(&top, 14); push(&top, -3); cout << "Stack elements before sorting:\n"; printStack(top); sortStack(&top); cout << "\n"; cout << "Stack elements after sorting:\n"; printStack(top); return 0;}// This code is contributed by SHUBHAMSINGH10 |
C
// C program to sort a stack using recursion#include <stdio.h>#include <stdlib.h>// Stack is represented using linked liststruct stack { int data; struct stack* next;};// Utility function to initialize stackvoid initStack(struct stack** s) { *s = NULL; }// Utility function to check if stack is emptyint isEmpty(struct stack* s){ if (s == NULL) return 1; return 0;}// Utility function to push an item to stackvoid push(struct stack** s, int x){ struct stack* p = (struct stack*)malloc(sizeof(*p)); if (p == NULL) { fprintf(stderr, "Memory allocation failed.\n"); return; } p->data = x; p->next = *s; *s = p;}// Utility function to remove an item from stackint pop(struct stack** s){ int x; struct stack* temp; x = (*s)->data; temp = *s; (*s) = (*s)->next; free(temp); return x;}// Function to find top itemint top(struct stack* s) { return (s->data); }// Recursive function to insert an item x in sorted wayvoid sortedInsert(struct stack** s, int x){ // Base case: Either stack is empty or newly inserted // item is greater than top (more than all existing) if (isEmpty(*s) || x > top(*s)) { push(s, x); return; } // If top is greater, remove the top item and recur int temp = pop(s); sortedInsert(s, x); // Put back the top item removed earlier push(s, temp);}// Function to sort stackvoid sortStack(struct stack** s){ // If stack is not empty if (!isEmpty(*s)) { // Remove the top item int x = pop(s); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); }}// Utility function to print contents of stackvoid printStack(struct stack* s){ while (s) { printf("%d ", s->data); s = s->next; } printf("\n");}// Driver codeint main(void){ struct stack* top; initStack(&top); push(&top, 30); push(&top, -5); push(&top, 18); push(&top, 14); push(&top, -3); printf("Stack elements before sorting:\n"); printStack(top); sortStack(&top); printf("\n\n"); printf("Stack elements after sorting:\n"); printStack(top); return 0;} |
Java
// Java program to sort a Stack using recursion// Note that here predefined Stack class is used// for stack operationimport java.util.ListIterator;import java.util.Stack;class Test { // Recursive Method to insert an item x in sorted way static void sortedInsert(Stack<Integer> s, int x) { // Base case: Either stack is empty or newly // inserted item is greater than top (more than all // existing) if (s.isEmpty() || x > s.peek()) { s.push(x); return; } // If top is greater, remove the top item and recur int temp = s.pop(); sortedInsert(s, x); // Put back the top item removed earlier s.push(temp); } // Method to sort stack static void sortStack(Stack<Integer> s) { // If stack is not empty if (!s.isEmpty()) { // Remove the top item int x = s.pop(); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); } } // Utility Method to print contents of stack static void printStack(Stack<Integer> s) { ListIterator<Integer> lt = s.listIterator(); // forwarding while (lt.hasNext()) lt.next(); // printing from top to bottom while (lt.hasPrevious()) System.out.print(lt.previous() + " "); } // Driver code public static void main(String[] args) { Stack<Integer> s = new Stack<>(); s.push(30); s.push(-5); s.push(18); s.push(14); s.push(-3); System.out.println( "Stack elements before sorting: "); printStack(s); sortStack(s); System.out.println( " \n\nStack elements after sorting:"); printStack(s); }} |
Python3
# Python program to sort a stack using recursion# Recursive method to insert element in sorted waydef sortedInsert(s, element): # Base case: Either stack is empty or newly inserted # item is greater than top (more than all existing) if len(s) == 0 or element > s[-1]: s.append(element) return else: # Remove the top item and recur temp = s.pop() sortedInsert(s, element) # Put back the top item removed earlier s.append(temp)# Method to sort stackdef sortStack(s): # If stack is not empty if len(s) != 0: # Remove the top item temp = s.pop() # Sort remaining stack sortStack(s) # Push the top item back in sorted stack sortedInsert(s, temp)# Printing contents of stackdef printStack(s): for i in s[::-1]: print(i, end=" ") print()# Driver Codeif __name__ == '__main__': s = [] s.append(30) s.append(-5) s.append(18) s.append(14) s.append(-3) print("Stack elements before sorting: ") printStack(s) sortStack(s) print("\nStack elements after sorting: ") printStack(s)# This code is contributed by Muskan Kalra. |
C#
// C# program to sort a Stack using recursion// Note that here predefined Stack class is used// for stack operationusing System;using System.Collections;public class GFG { // Recursive Method to insert an item x in sorted way static void sortedInsert(Stack s, int x) { // Base case: Either stack is empty or // newly inserted item is greater than top // (more than all existing) if (s.Count == 0 || x > (int)s.Peek()) { s.Push(x); return; } // If top is greater, remove // the top item and recur int temp = (int)s.Peek(); s.Pop(); sortedInsert(s, x); // Put back the top item removed earlier s.Push(temp); } // Method to sort stack static void sortStack(Stack s) { // If stack is not empty if (s.Count > 0) { // Remove the top item int x = (int)s.Peek(); s.Pop(); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); } } // Utility Method to print contents of stack static void printStack(Stack s) { foreach(int c in s) { Console.Write(c + " "); } } // Driver code public static void Main(String[] args) { Stack s = new Stack(); s.Push(30); s.Push(-5); s.Push(18); s.Push(14); s.Push(-3); Console.WriteLine( "Stack elements before sorting: "); printStack(s); sortStack(s); Console.WriteLine( " \n\nStack elements after sorting:"); printStack(s); }}// This code is Contributed by Arnab Kundu |
Javascript
<script>// JavaScript program to sort a Stack using recursion// Note that here predefined Stack class is used// for stack operation// Recursive Method to insert an item x in sorted wayfunction sortedInsert(s,x){ // Base case: Either stack is empty or newly // inserted item is greater than top (more than all // existing) if (s.length==0 || x > s[s.length-1]) { s.push(x); return; } // If top is greater, remove the top item and recur let temp = s.pop(); sortedInsert(s, x); // Put back the top item removed earlier s.push(temp);}// Method to sort stackfunction sortStack(s){ // If stack is not empty if (s.length!=0) { // Remove the top item let x = s.pop(); // Sort remaining stack sortStack(s); // Push the top item back in sorted stack sortedInsert(s, x); }}// Utility Method to print contents of stackfunction printStack(s){ for(let i=s.length-1;i>=0;i--) { document.write(s[i]+" "); } document.write("<br>")} // Driver code let s=[];s.push(30);s.push(-5);s.push(18);s.push(14);s.push(-3);document.write("Stack elements before sorting: <br>");printStack(s);sortStack(s);document.write(" <br><br>Stack elements after sorting:<br>");printStack(s);// This code is contributed by avanitrachhadiya2155</script> |
Time Complexity: O(N2).
Auxiliary Space: O(N) use of Stack
Another Method Using STL stack, collection in Java
C++
#include <stack>#include <iostream>using namespace std;// Function to sort a stack using recursionvoid sortStack(stack<int> &s) { // If the stack is empty, return if (s.empty()) return; // Remove the top element of the stack int x = s.top(); s.pop(); // Sort the remaining elements in the stack using recursion sortStack(s); // Create two auxiliary stacks stack<int> tempStack; // Move all elements that are greater than x from the main stack to the tempStack while (!s.empty() && s.top() > x) { tempStack.push(s.top()); s.pop(); } // Push x back into the main stack s.push(x); // Move all elements from tempStack back to the main stack while (!tempStack.empty()) { s.push(tempStack.top()); tempStack.pop(); }}int main() { // Create a stack stack<int> s; // Push elements into the stack s.push(34); s.push(3); s.push(31); s.push(98); s.push(92); s.push(23); // Sort the stack sortStack(s); // Print the sorted elements cout << "Sorted numbers are: "; while (!s.empty()) { cout << s.top() << " "; s.pop(); } return 0;} |
Java
import java.util.Stack;public class Main { public static void sortStack(Stack<Integer> s) { // If the stack is empty, return if (s.empty()) return; // Remove the top element of the stack int x = s.pop(); // Sort the remaining elements in the stack using // recursion sortStack(s); // Create two auxiliary stacks Stack<Integer> tempStack = new Stack<>(); // Move all elements that are greater than x from // the main stack to the tempStack while (!s.empty() && s.peek() > x) { tempStack.push(s.pop()); } // Push x back into the main stack s.push(x); // Move all elements from tempStack back to the main // stack while (!tempStack.empty()) { s.push(tempStack.pop()); } } public static void main(String[] args) { // Create a stack Stack<Integer> s = new Stack<>(); // Push elements into the stack s.push(34); s.push(3); s.push(31); s.push(98); s.push(92); s.push(23); // Sort the stack sortStack(s); // Print the sorted elements System.out.print("Sorted numbers are: "); while (!s.empty()) { System.out.print(s.pop() + " "); } }} |
Python3
# Function to sort a stack using recursiondef sortStack(s): # If the stack is empty, return if not s: return # Remove the top element of the stack x = s.pop() # Sort the remaining elements in the stack using recursion sortStack(s) # Create two auxiliary stacks tempStack = [] # Move all elements that are greater than x from the main stack to the tempStack while s and s[-1] > x: tempStack.append(s.pop()) # Push x back into the main stack s.append(x) # Move all elements from tempStack back to the main stack while tempStack: s.append(tempStack.pop())# Create a stacks = []# Push elements into the stacks.append(34)s.append(3)s.append(31)s.append(98)s.append(92)s.append(23)# Sort the stacksortStack(s)# Print the sorted elementsprint("Sorted numbers are: ", end="")while s: print(s.pop(), end=" ") |
C#
using System;using System.Collections.Generic;public class Program{ // Function to sort a stack using recursion public static void SortStack(Stack<int> s) { // If the stack is empty, return if (s.Count == 0) return; // Remove the top element of the stack int x = s.Peek(); s.Pop(); // Sort the remaining elements in the stack using recursion SortStack(s); // Create two auxiliary stacks Stack<int> tempStack = new Stack<int>(); // Move all elements that are greater than x from the main stack to the tempStack while (s.Count > 0 && s.Peek() > x) { tempStack.Push(s.Peek()); s.Pop(); } // Push x back into the main stack s.Push(x); // Move all elements from tempStack back to the main stack while (tempStack.Count > 0) { s.Push(tempStack.Peek()); tempStack.Pop(); } } public static void Main() { // Create a stack Stack<int> s = new Stack<int>(); // Push elements into the stack s.Push(34); s.Push(3); s.Push(31); s.Push(98); s.Push(92); s.Push(23); // Sort the stack SortStack(s); // Print the sorted elements Console.Write("Sorted numbers are: "); while (s.Count > 0) { Console.Write(s.Peek() + " "); s.Pop(); } }} |
Javascript
function sortStack(s) { // If the stack is empty or has only one element, return if (s.length <= 1) { return; } // Remove the top element of the stack let x = s.pop(); // Sort the remaining elements in the stack using recursion sortStack(s); // Create two auxiliary stacks let tempStack = []; // Move all elements that are greater than x from the main stack to the tempStack while (s.length !== 0 && s[s.length - 1] > x) { tempStack.push(s.pop()); } // Push x back into the main stack s.push(x); // Move all elements from tempStack back to the main stack while (tempStack.length !== 0) { s.push(tempStack.pop()); }}// Create a stacklet s = [];// Push elements into the stacks.push(34);s.push(3);s.push(31);s.push(98);s.push(92);s.push(23);// Sort the stacksortStack(s);// Print the sorted elementslet result = "Sorted numbers are: ";while (s.length !== 0) { result += s.pop() + " ";}console.log(result.trim());// This code is contributed by divyansh2212 |
Output
Sorted numbers are: 98 92 34 31 23 3
Time complexity: O(n^2)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
