[Solved] How to reverse a Stack in Java using Recursion and Iteration? Example Tutorial

Hello guys, if you are wondering how to reveres a stack in Java then don't go anywhere. In this article, I will show you step by step how to reverse a given stack in Java. There are two ways to reverse a stack, you can use iteration or recursion. The most common way of reversing a stack is to use an auxiliary stack. First, we will pop all the elements from the stack and push them into the auxiliary stack. Once all the elements are pushed into the auxiliary stack, then it contains the elements in the reverse order and we simply print them. But, here, we will not use the auxiliary stack. We will use a recursion method to reverse a stack where recursion means calling the function itself again and again. 
What do I mean by auxiliary stack? Auxiliary data structure is a sweet way of saying helper data structure. Something you might use to solve a given problem and is terminated after the problem is solved.

For example, if I asked you to find the count of each element I have in an array. One way to do this is by using a hash table(key-value pairs). You would store the elements in the table as keys and their occurrences as values. 

Then you could traverse the table and find the occurrences of each element. After you get the occurrences you wouldn't need the table, therefore, it's an auxiliary data structure. Taking up extra space for a temporary period of time.

In the recursion method, we first pop all the elements from the input stack and push all the popped items into the function call stack until the stack becomes empty. When the stack becomes empty, all the items will be pushed at the stack. 

Btw, this is also one of the common stack coding problems from Java interviews and if you need more stack questions then you can also check that article

How to reverse a Stack in Java using Recursion? Code Example

Stack is a linear data structure similar to arrays and linked lists that allow us to store and retrieve data sequentially. In general, insertion operation is called “push,” and deletion operation is called “pop.” They are useful when dynamic addition and deletion of elements are required.

At any given time, one can only access the top element of a stack. Due to this reason, it is a LIFO (Last In First Out) data structure. In this, the element added last is accessed first. The time complexity for all operations in a stack is O(1), making it efficient and improving performance.

In Stack data structure, the last item is the first to get out as it has been said above. Think of plates that you place on themselves after washing. Yeah! That is exactly the stack data structure. It makes no logical sense to bring out the first item that got in out first,

You doing that means you are out of stack data structure, you are already going into another type of data structure. Here, we want to reverse a stack. Imagine that you have numbers 1 - 10 stored in a stack, now we want to implement it to be stored the other way round which means 10 - 1, lets go!

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

public class StackReversion { static Stack < Character > stack = new Stack < > (); static void insert_at_bottom(char x) { if (stack.isEmpty()) stack.push(x); else { char a = stack.peek(); stack.pop(); insert_at_bottom(x); stack.push(a); } } static void reverse() { if (stack.size() > 0) { char x = st.peek(); stack.pop(); reverse(); insert_at_bottom(x); } } // Driver Code public static void main(String[] args) { stack.push('1'); stack.push('2'); stack.push('3'); stack.push('4'); System.out.println("Original Stack"); System.out.println(stack); reverse(); System.out.println("Reversed Stack"); System.out.println(stack); } }

Explanation of Solution and Code

Class declaration in line 1 and Stack was introduced in line 2, which takes in character as a type. Note: because the stack can not hold primitive types it has to be auto-boxed to reference types that is why the character was a capital letter, with a variable name stack which was initialized to the new stack.

In line 3, the method "insertFromBottom" was created that takes in a parameter of character type, so if the stack is empty, it should push in the parameter, but if not it should proceed to carry out the rest of the codes. So line 19 executes by peeking at the item at the top and saving in a variable. 

After the peek method was called then the method reverse was called.

So, the implementation of the method “reverse” goes thus: line 15, the method “reverse” was created which returns void. So, if the size of the stack is greater than zero then the peek method would be called and stored inside variable then, after that, the pop method does it work too to pop out the element, and after that was a recursion call. 

This keeps happening until it reaches the end of the stack. After each recursion call, the method “insertFromBottom” is always called.

Driver class:
The main method was declared in line 26. from lines 28 to 31, four different items were pushed into the stack, 1,2,3,4 respectively. Line 33 and 35 print the original stack after which the reverse() method was called, then the reversed stack was printed.


OUTPUT

Original Stack:
[1,2,3,4,]

Reversed Stack:
[4,3,2,1]

 

That's all about how to reverse a Stack in Java. This is not only a good exercise to learn about Stack but also to learn about recursion and how you can convert an iterative solution to recursion one using the appropriate data structure. 

Stack is one of the important data structures and I believe every programmer should know about it and be familiar with its properties. I mostly use stack to convert interactive algorithms to a recursion one like in this example. If you have any questions with respect to this solution or explanation feel free to ask. 

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog

• Top 15 Data Structure and Algorithm Interview Questions (see here)
• Top 20 String coding interview questions (see here)
• How to implement a linked list using generics in Java? (solution)
• How to reverse a singly linked list in Java? (solution)
• How to find the middle element of the linked list using a single pass? (solution)
• 133 core Java interview questions of the last 5 years (see here)
• Top 30 Array Coding Interview Questions with Answers (see here)
• Top 30 linked list coding interview questions (see here)
• How to find the 3rd element from the end of a linked list in Java? (solution)
• Top 50 Java Programs from Coding Interviews (see here)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• 10 Algorithms Books Every Programmer Should Read (books)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this coding problem solution so far. If you like this article, then please share it with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.

P. S. - If you want to improve your DSA skills and need the best free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check these free data structure and algorithms courses from Coursera, Educative, and Udemy. It's authored by a Google Software Engineer and Algorithm expert, and it's completely free of cost.