How to reverse a stack using Recursion? In this tutorial, I am going to discuss this interesting problem.
Given a stack of integers, we have to write a code to reverse them using recursion. For solving this problem, we don’t have to use any loop constructs (For, While etc.) or any additional data structure.
You can use stack methods like push, pop, isEmpty to solve this problem.
Programming Questions on Stacks
If we have to use additional data structure then this problem would be easily solved by using another stack.
Reverse a Stack using Recursion – Java Code
Before solving this problem, let’s understand few important points.
We know in a stack the element which we pushed at last is the first element to be popped out. It follows Last In First Out (LIFO) order.
To reverse a stack, First we have to pop all the values of a stack recursively until the stack becomes empty. And then insert each values one by one at the bottom of the stack.
It means we have to use two recursive function to solve this problem. I have also shared the video tutorial at the end of this post.
The time complexity of this approach is O(n^2). And it’s space complexity is O(n).
|
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 |
//Reverse a stack public class ReverseStack { public static void reverse(Stack<Integer> st) { //Base condition if(st.isEmpty()) return; int temp = st.pop(); reverse(st); insertAtLast(st, temp); } public static void insertAtLast(Stack<Integer> stack, int elem){ //If stack is empty, push the elem in a stack. if(stack.isEmpty()){ stack.push(elem); return; } //Pop elements from stack and keep it in a function call int topElem = stack.pop(); //Push elem at last insertAtLast(stack, elem); //Push all the popped elements in a stack stack.push(topElem); } public static void main(String[] args) { Stack<Integer> st = new Stack<>(); st.add(4); st.add(3); st.add(2); st.add(1); System.out.println(st); reverse(st); System.out.println(st); } |
