Do you think IIT Guwahati certified course can help you in your career?
No
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.
What is reverse a stack?
Reversing a stack involves changing the order of elements in a stack from the original arrangement to the opposite. This operation typically utilizes auxiliary data structures, such as another stack or recursion, to rearrange the elements in reverse order.
Different Methods to Reverse the Stack
Lets discuss various methods to reverse the stack:-
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.
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
Working
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.
Reason: O(N) is the time complexity to reverse a linked list.
Space Complexity: O(1)
Reason: No extra space is required.
Problem Statement for Reversing a Stack:
Write a program to insert elements to the stack and display the reversed stack.
Problem Statement
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.
Push Operation
Pop Operation
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.
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);
}
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
Working
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)
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
Working
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(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). Must Read C Program to Reverse a Number
Frequently Asked Questions
Why is the space complexity in recursive solution O(N) even though no extra data structure is used?
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.
Why is the time complexity in a recursive solution O(N²)?
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²).
How is the topmost stack element inserted at the top element at the bottom of the stack in the recursive approach?
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.
Can the stack be reversed without using any extra space?
Yes, if the linked list is used to implement the stack, it can be reversed without extra space and linear time complexity.
Conclusion
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. You can also consider our Mern Stack Course to give your career an edge over others. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.