1. Overview
In this article, we’ll look into the different ways of reversing a stack using Java. A stack is a LIFO(Last In, First Out) data structure that supports the insertion (push) and removal (pop) of elements from the same side.
We can visualise a stack as a stack of plates on a table; accessing the plates is the safest when done from the top.
2. Problem: Reverse a Stack
Let’s explore the problem statement in depth. We’re given a Stack of objects as input, and we’re required to return the stack with the elements in reverse order. Here’s an example.
Input: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Output: [9, 8, 7, 6, 5, 4, 3, 2, 1]
The input is a stack of the first nine natural numbers, and the output of our code should be the same natural numbers in reverse order. We can extend this problem to any type of stack, for example, a stack of String elements, a stack of custom objects such as Node, etc.
For example:
Input: [“Red”, “Blue”, “Green”, “Yellow”]
Output: [“Yellow”, “Green”, “Blue”, “Red”]
3. Reverse a Stack Using a Queue
In this section, let’s see how we can solve the problem by using a Queue data structure. A Queue is a FIFO(First In, First Out) data structure and supports the addition of elements from the rear side and the removal of elements from the front side.
Given a stack of elements as input, we can pick elements from the top of the stack, one at a time, and insert them into our queue. From our first example of the natural numbers, we’ll start with the top of the stack pointing to 9. We insert the stack’s top element into the queue’s rear end at each step, and eventually, we would have emptied the stack. At this point we have filled the queue with the elements in the following order:
(rear) [1, 2, 3, 4, 5, 6, 7, 8, 9] (front).
Once this is done, we can remove elements from the queue, which takes place from the front side, and push it back onto our stack. After this activity completes, we’ll be left with our desired output stack [9, 8, 7, 6, 5, 4, 3, 2, 1].
This is how the code looks, considering the stack to be of type Integer:
public Stack reverseIntegerStack(Stack<Integer> inputStack) {
Queue<Integer> queue = new LinkedList<>();
while (!inputStack.isEmpty()) {
queue.add(inputStack.pop());
}
while (!queue.isEmpty()) {
inputStack.add(queue.remove());
}
return inputStack;
}
4. Reverse a Stack Using Recursion
Let’s discuss an approach to solving this problem without using any additional data structure. Recursion is a core concept that is abundant in computer science and deals with the idea of a method calling itself repeatedly as long as a precondition is satisfied. Any recursion function should have two components to it:
- The Recursive Call: in our case, the recursive call to the method will remove elements from the given stack
- The Stop Condition: the recursion will end when the given stack is empty
Every call to the recursive method adds to the call stack in JVM memory. We can leverage this fact to reverse the given stack. A recursive call will remove an element from the top of the stack and add it to the memory call stack.Â
When the input stack is empty, the memory call stack contains the elements of the stack in reversed order. The top of the call stack contains the number 1, whereas the bottommost call stack contains the number 10. At this point, we take items from the call stack and insert the elements to the bottom of the stack, reversing the elements’ original order.
Let’s see the two-step recursive algorithm in the code here:
private void reverseStack(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int top = stack.pop();
reverseStack(stack);
insertBottom(stack, top);
}
The reverseStack()Â method pops the top element from the stack recursively. Once the input stack is empty, we insert the elements which are currently in the call stack, to the bottom of the stack:
private void insertBottom(Stack<Integer> stack, int value) {
if (stack.isEmpty()) {
stack.add(value);
} else {
int top = stack.pop();
insertBottom(stack, value);
stack.add(top);
}
}
5. Comparing the Approaches of Reversing a Stack
We discussed two approaches to the problem of reversing a given stack. These algorithms work on a Stack of any type. The first solution of using an additional Queue data structure reverses the stack in O(n) time complexity. However, since we’re using additional space in the form of the Queue, the space complexity is O(n) as well.
On the other hand, the recursive solution has a time complexity of O(n²) because of the recursive calls but comes with no additional space complexity as we are utilising the program call stack to store the elements of the stack.
6. Conclusion
In this article, we discussed two approaches to reversing a Stack in Java and compared the running time and space complexities of the algorithms. As usual, all code samples can be found over on GitHub.
