Introduction
Reversing a stack is one of the most basic coding questions in stacks. In this blog, we are going to discuss the various methods to reverse the stack. Let’s get started.
Problem Statement for Reversing a Stack:
Write a program to insert elements to the stack and display the reversed stack.
Stack
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.
Check out Stack Notes to learn stack in detail.
Driver code(Main function):
Let’s check out the main function before moving to each approach. In the main function, we initialize the stack, enter elements, reverse the stack by calling reverseStack() function and print the reversed stack.
Main function for Driver code:
public static void main(String args[]) { // initialize stack Stack<Integer> s = new Stack<Integer>(); // push elements s.push(1); s.push(2); s.push(3); s.push(4); // print elements before reversing System.out.println("Stack before reversing:"); System.out.println(s); // reverse stack using reverseStack() s = reverseStack(s); // using stacks reverseStack() // recursion // print elements after reversing System.out.println("Stack after reversing:"); System.out.println(s); }
Now let’s go through each approach.
Reversing a Stack using Another Stack
In this approach, we would be using an extra stack to reverse the stack. Let’s see the pseudo-code for this approach.
Pseudo – Code for reverseStack()
initialize an empty extra stack set n to the size of the original stack for i to n set the variable element to the topmost element of the original stack pop the topmost element of the original stack push this element into the extra stack return the extra stack, which is reversed
reverseStack()
// function to reverse stack using another stack static Stack<Integer> reverseStack(Stack<Integer> s) { // initialize extra stack Stack<Integer> extraStack = new Stack<Integer>(); int n = s.size(); for (int i = 0; i < n; i++) { // access the top element int element = s.peek(); // remove the top element s.pop(); // push the element into the extra stack extraStack.push(element); } // return the extraStack which is reversed return extraStack; }
Time Complexity: O(N)
Reason: The loop runs for n times and the time complexity for all the stack operations is O(1). Therefore the overall time complexity is O(N)
Space Complexity: O(N)
Reason: An extra stack of size N is used.
Reversing a Stack using Two Stacks
In this approach, we would be using two stacks to reverse the stack. This is similar to the above approach; the difference is that in this approach, instead of returning the extra stack, we directly use the original stack after transferring elements. Let’s see the pseudo-code for this approach.
Pseudo – Code for reverseStack()
initialize two empty stacks, a and b transfer elements from s to a transfer elements from a to b transfer elements from b to s display elements of s
Pseudo – Code for transfer
While stack is not empty Set element to the topmost element of the s1 stack Push element into the s2 stack Pop element from the s1 stack
transfer()
// function to transfer elements static void transfer(Stack<Integer> s1, Stack<Integer> s2) { while (!s1.empty()) { int element = s1.peek(); s2.push(element); s1.pop(); } }
reverseStack()
// function to reverse stack static Stack<Integer> reverseStack(Stack<Integer> s) { // initialize stack a and b Stack<Integer> a = new Stack<Integer>(); Stack<Integer> b = new Stack<Integer>(); // transfer elements from s to a transfer(s,a); // transfer elements from a to b transfer(a,b); // transfer elements from b to s transfer(b,s); // return the original stack return s; }
Time Complexity: O(N)
Reason: The loop runs for 3n times and the time complexity for all the stack operations is O(1). Therefore the overall time complexity is O(N)
Space Complexity: O(N)
Reason: Two extra stacks of size N is used and the overall space complexity becomes O(N)
Reversing a Stack using Recursion
If the question specifies that no other data structure can be used to solve the problem, recursion has to be used. In this approach, we pop the top element from the given stack and recursively call another instance of the same function. When this child function returns to the parent function, append the popped element to the bottom of the stack. For this, we would be using two recursive functions: reverseStack() and insertAtBottom().
reverseStack():
It checks if the stack is empty or not. The top element is popped out and stored in the element variable if the stack is not empty. We then call reverseStack() function again on the updated stack. When this child function returns, we call the helper function insertAtBottom().
insertAtBottom():
It recursively inserts an element at the bottom of a stack. If the stack is empty, it simply pushes the element else; the top element is popped out and stored in the topElement variable. Then insertAtBottom() is called again on the updated stack. When this child function returns, it pushes the topElement back in the stack.
In this solution, we would be using recursion so check out this blog Recursion in Data Structure: How Does it Work, Types & When Used to know more about recursion.
reverseStack()
specify the base case when the stack is empty, return set element to topmost element of the stack pop the topmost element of the stack recursively call reverseStack on the updated stack insert the element at the bottom of the stack
insertAtBottom()
specify the base case when the stack is empty, push element to stack and return set toElement to topmost element of the stack pop the topmost element of the stack recursively call insertAtBottom on the updated stack push element to stack
reverseStack()
// function to reverse stack using recursion static void reverseStack(Stack<Integer> s) { // base case if(s.empty()) { return; } // access the top element int element = s.peek(); // remove the top element s.pop(); // reverse the remaining elements of a stack reverseStack(s); // insert the popped out element at the bottom insertAtBottom(s,element); }
insertAtBottom()
// function to insert top element at the bottom of stack static void insertAtBottom(Stack<Integer> s, int element) { // base case if(s.empty()) { // push the element at bottom s.push(element); return; } // access the top element int topElement = s.peek(); // remove the top element s.pop(); // insert the element at the bottom of the stack insertAtBottom(s,element); // add the top element to the stack s.push(topElement); }
Time Complexity: O(N²)
Two recursive functions are there in which the first function is calling itself recursively and the second function in each call. Also, the second function is recursively called.
Space Complexity: O(N)
The recursive program uses a memory of O(N) to store the function call stack.
Reversing a Stack without using Recursion
In this solution, we would be implementing Implement Stack using Linked List and reverse the linked list to get the reversed stack.
Please try to implement a Stack using a Linked List on CodeStudio. Also, check out this blog, How To Master Linked List And Its Importance, and notes on Linked List Reversal to know more about Linked List.
Time Complexity: O(N)
Reason: O(N) is the time complexity to reverse a linked list.
Space Complexity: O(1)
Reason: No extra space is required.
Frequently Asked Questions
The recursive program uses a memory of O(N) to store the function call stack. In the recursive program, we are storing both the functions in the call stack one after another.
For each topmost element of the stack, the whole stack is popped out and the topmost element is placed at the bottom of the stack. This takes O(N) complexity and doing this for every stack element makes the overall time complexity O(N²).
The top element of the stack is popped out and stored in the call stack frame until the stack becomes empty. When the stack becomes empty, the top element is added to the empty stack, and all the elements stored in the call stack are pushed while returning down the recursion tree.
es, if the linked list is used to implement the stack, it can be reversed without extra space and linear time complexity.
The head node (or the first node) is considered the top element when a stack is implemented using a linked list.
Key Takeaways
This blog covered the various methods of reversing a stack. The methods involved: reversing a stack using another stack, reversing a stack using two stacks, reversing a stack using recursion, and reversing a stack using Linked List.
Don’t stop here. Check out our Data Structures and Algorithms -guided path to learning DSA from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.
Leave a Reply