Write a program to reverse a stack using recursion, without using any loop.
Example:
Input: elements present in stack from top to bottom 1 2 3 4
Output: 4 3 2 1Input: elements present in stack from top to bottom 1 2 3
Output: 3 2 1
Reverse a stack using Recursion
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 at the bottom of the stack.
Illustration:
Below is the illustration of the above approach
- Let given stack be
1 2 3 4
- After all calls of reverse, 4 will be passed to function insert at bottom, after that 4 will pushed to the stack when stack is empty
4
- Then 3 will be passed to function insert at bottom , it will check if the stack is empty or not if not then pop all the elements back and insert 3 and then push other elements back.
4 3
- Then 2 will be passed to function insert at bottom , it will check if the stack is empty or not if not then pop all the elements back and insert 2 and then push other elements back.
4 3 2
- Then 1 will be passed to function insert at bottom , it will check if the stack is empty or not if not then pop all the elements back and insert 1 and then push other elements back.
4 3 2 1
Follow the steps mentioned below to implement the idea:
- Create a stack and push all the elements in it.
- Call reverse(), which will pop all the elements from the stack and pass the popped element to function insert_at_bottom()
- Whenever insert_at_bottom() is called it will insert the passed element at the bottom of the stack.
- Print the stack
Below is the implementation of the above approach:
C++
// C++ code to reverse a// stack using recursion#include <bits/stdc++.h>using namespace std;// Below is a recursive function// that inserts an element// at the bottom of a stack.void insert_at_bottom(stack<int>& st, int x){ if (st.size() == 0) { st.push(x); } else { // All items are held in Function Call // Stack until we reach end of the stack // When the stack becomes empty, the // st.size() becomes 0, the above if // part is executed and the item is // inserted at the bottom int a = st.top(); st.pop(); insert_at_bottom(st, x); // push allthe items held in // Function Call Stack // once the item is inserted // at the bottom st.push(a); }}// Below is the function that// reverses the given stack using// insert_at_bottom()void reverse(stack<int>& st){ if (st.size() > 0) { // Hold all items in Function // Call Stack until we // reach end of the stack int x = st.top(); st.pop(); reverse(st); // Insert all the items held // in Function Call Stack // one by one from the bottom // to top. Every item is // inserted at the bottom insert_at_bottom(st, x); } return;}// Driver Codeint main(){ stack<int> st, st2; // push elements into // the stack for (int i = 1; i <= 4; i++) { st.push(i); } st2 = st; cout << "Original Stack" << endl; // printing the stack after reversal while (!st2.empty()) { cout << st2.top() << " "; st2.pop(); } cout<<endl; // function to reverse // the stack reverse(st); cout << "Reversed Stack" << endl; // printing the stack after reversal while (!st.empty()) { cout << st.top() << " "; st.pop(); } return 0;} |
C
// C program to reverse a// stack using recursion#include <stdio.h>#include <stdlib.h>#define bool int// structure of a stack nodestruct sNode { char data; struct sNode* next;};// Function Prototypesvoid push(struct sNode** top_ref, int new_data);int pop(struct sNode** top_ref);bool isEmpty(struct sNode* top);void print(struct sNode* top);// Below is a recursive function// that inserts an element// at the bottom of a stack.void insertAtBottom(struct sNode** top_ref, int item){ if (isEmpty(*top_ref)) push(top_ref, item); else { // Hold all items in Function Call // Stack until we reach end of the // stack. When the stack becomes // empty, the isEmpty(*top_ref)becomes // true, the above if part is executed // and the item is inserted at the bottom int temp = pop(top_ref); insertAtBottom(top_ref, item); // Once the item is inserted // at the bottom, push all // the items held in Function // Call Stack push(top_ref, temp); }}// Below is the function that// reverses the given stack using// insertAtBottom()void reverse(struct sNode** top_ref){ if (!isEmpty(*top_ref)) { // Hold all items in Function // Call Stack until we // reach end of the stack int temp = pop(top_ref); reverse(top_ref); // Insert all the items (held in // Function Call Stack) // one by one from the bottom // to top. Every item is // inserted at the bottom insertAtBottom(top_ref, temp); }}// Driver Codeint main(){ struct sNode* s = NULL; push(&s, 4); push(&s, 3); push(&s, 2); push(&s, 1); printf("\n Original Stack "); print(s); reverse(&s); printf("\n Reversed Stack "); print(s); return 0;}// Function to check if// the stack is emptybool isEmpty(struct sNode* top){ return (top == NULL) ? 1 : 0;}// Function to push an item to stackvoid push(struct sNode** top_ref, int new_data){ // allocate node struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode)); if (new_node == NULL) { printf("Stack overflow \n"); exit(0); } // put in the data new_node->data = new_data; // link the old list // off the new node new_node->next = (*top_ref); // move the head to // point to the new node (*top_ref) = new_node;}// Function to pop an item from stackint pop(struct sNode** top_ref){ char res; struct sNode* top; // If stack is empty then error if (*top_ref == NULL) { printf("Stack overflow \n"); exit(0); } else { top = *top_ref; res = top->data; *top_ref = top->next; free(top); return res; }}// Function to print a// linked listvoid print(struct sNode* top){ printf("\n"); while (top != NULL) { printf(" %d ", top->data); top = top->next; }} |
Java
// Java code to reverse a// stack using recursionimport java.util.Stack;class Test { // using Stack class for // stack implementation static Stack<Character> st = new Stack<>(); // Below is a recursive function // that inserts an element // at the bottom of a stack. static void insert_at_bottom(char x) { if (st.isEmpty()) st.push(x); else { // All items are held in Function // Call Stack until we reach end // of the stack. When the stack becomes // empty, the st.size() becomes 0, the // above if part is executed and // the item is inserted at the bottom char a = st.peek(); st.pop(); insert_at_bottom(x); // push allthe items held // in Function Call Stack // once the item is inserted // at the bottom st.push(a); } } // Below is the function that // reverses the given stack using // insert_at_bottom() static void reverse() { if (st.size() > 0) { // Hold all items in Function // Call Stack until we // reach end of the stack char x = st.peek(); st.pop(); reverse(); // Insert all the items held // in Function Call Stack // one by one from the bottom // to top. Every item is // inserted at the bottom insert_at_bottom(x); } } // Driver Code public static void main(String[] args) { // push elements into // the stack st.push('1'); st.push('2'); st.push('3'); st.push('4'); System.out.println("Original Stack"); System.out.println(st); // function to reverse // the stack reverse(); System.out.println("Reversed Stack"); System.out.println(st); }} |
Python3
# Python program to reverse a# stack using recursion# Below is a recursive function# that inserts an element# at the bottom of a stack.def insertAtBottom(stack, item): if isEmpty(stack): push(stack, item) else: temp = pop(stack) insertAtBottom(stack, item) push(stack, temp)# Below is the function that# reverses the given stack# using insertAtBottom()def reverse(stack): if not isEmpty(stack): temp = pop(stack) reverse(stack) insertAtBottom(stack, temp)# Below is a complete running# program for testing above# functions.# Function to create a stack.# It initializes size of stack# as 0def createStack(): stack = [] return stack# Function to check if# the stack is emptydef isEmpty(stack): return len(stack) == 0# Function to push an# item to stackdef push(stack, item): stack.append(item)# Function to pop an# item from stackdef pop(stack): # If stack is empty # then error if(isEmpty(stack)): print("Stack Underflow ") exit(1) return stack.pop()# Function to print the stackdef prints(stack): for i in range(len(stack)-1, -1, -1): print(stack[i], end=' ') print()# Driver Codestack = createStack()push(stack, str(4))push(stack, str(3))push(stack, str(2))push(stack, str(1))print("Original Stack ")prints(stack)reverse(stack)print("Reversed Stack ")prints(stack)# This code is contributed by Sunny Karira |
C#
// C# code to reverse a// stack using recursionusing System;using System.Collections;public class GFG { // using Stack class for // stack implementation static Stack st = new Stack(); // Below is a recursive function // that inserts an element // at the bottom of a stack. static void insert_at_bottom(char x) { if (st.Count == 0) st.Push(x); else { // All items are held in Function // Call Stack until we reach end // of the stack. When the stack becomes // empty, the st.size() becomes 0, the // above if part is executed and // the item is inserted at the bottom char a = (char)st.Peek(); st.Pop(); insert_at_bottom(x); // push all the items held // in Function Call Stack // once the item is inserted // at the bottom st.Push(a); } } // Below is the function that // reverses the given stack using // insert_at_bottom() static void reverse() { if (st.Count > 0) { // Hold all items in Function // Call Stack until we // reach end of the stack char x = (char)st.Peek(); st.Pop(); reverse(); // Insert all the items held // in Function Call Stack // one by one from the bottom // to top. Every item is // inserted at the bottom insert_at_bottom(x); } } // Driver Code public static void Main(String[] args) { // push elements into // the stack st.Push('1'); st.Push('2'); st.Push('3'); st.Push('4'); Console.WriteLine("Original Stack"); foreach(char i in st) { Console.Write(i + ", "); } // function to reverse // the stack reverse(); Console.WriteLine("\nReversed Stack"); foreach(char i in st) { Console.Write(i + ", "); } }}// This code is Contributed by Arnab Kundu |
Javascript
<script>// JavaScript code to reverse a// stack using recursion// using Stack class for// stack implementationlet st = [];// Below is a recursive function// that inserts an element// at the bottom of a stack.function insert_at_bottom(x){ if(st.length==0) st.push(x); else { // All items are held in Function // Call Stack until we reach end // of the stack. When the stack becomes // empty, the st.size() becomes 0, the // above if part is executed and // the item is inserted at the bottom let a = st.pop(); insert_at_bottom(x); // push allthe items held // in Function Call Stack // once the item is inserted // at the bottom st.push(a); } }// Below is the function that // reverses the given stack using // insert_at_bottom()function reverse(){ if(st.length > 0) { // Hold all items in Function // Call Stack until we // reach end of the stack let x = st.pop(); reverse(); // Insert all the items held // in Function Call Stack // one by one from the bottom // to top. Every item is // inserted at the bottom insert_at_bottom(x); }}// Driver Code// push elements into// the stackst.push('1');st.push('2');st.push('3');st.push('4');document.write("Original Stack<br>");document.write(st.join(" ")+"<br>");// function to reverse// the stackreverse();document.write("Reversed Stack<br>");document.write(st.join(" "));// This code is contributed by avanitrachhadiya2155</script> |
Output
Original Stack 4 3 2 1 Reversed Stack 1 2 3 4
Time Complexity: O(N2).
Auxiliary Space: O(N) use of Stack
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!
