Through this tutorial, we will look at a famous data structure question “Reverse A Stack Using Recursion”. Reversing a stack using recursion is not a complicated task if you are aware about stack and recursion. Don’t worry, we will discuss everything including what is stack, what is recursion, and what are the steps to reverse stack using recursion. Let’s get to our topic and see how to reverse a stack using recursion.
Firstly we will discuss what a stack is.
What is a Stack?
The Last-In-First-Out (LIFO) principle is used by Stack, a type of linear data structure. Stack has only one end i.e. rear end. It only has one pointer i.e. top pointer, which points to the stack’s topmost element. When an element is added to the stack, it is always added to the top, and it can only be removed from the stack. To put it another way, a stack is a container that allows insertion and deletion only from the one end which is the stack’s top.
The terms "Push operation" and "Pop operation" refer to the operations used for addition and removal of the elements from the stack, respectively.
Let’s see how we can “reverse a stack using recursion”.
How To Reverse a Stack Using Recursion
The term "recursive solution" is used in the problem name itself.
You must be aware that a stack typically consists of two actions at the top, namely push and pop operations. Therefore, if we need to invert a stack, we must pop each element and put it to a different auxiliary stack one at a time. The auxiliary stack will then be the same stack, but in reverse.
Recursion can be used instead of an additional stack as it is not what we are after. A recursive function also functions similarly to a stack. Therefore, what we will do is build a recursive function that pops every item from the stack and saves it in the function call stack. The new item kept in the call stack is pushed to the bottom of the input stack when the input stack is empty.
In order to return to the previous state of recursion, we push the stored element in each recursion stack at the bottom of the input stack. In brief, we remove the top element of the input stack and store it in the recursion stack until the stack becomes empty.
Logic To Reverse Stack Using Recursion
The goal of the solution is to keep every value in the Function Call Stack until it becomes empty . Place each held element one by one to the bottom of the stack after it is completely full.
Dry Run
The example of the above strategy may be seen below.
-
Let given stack be
-
4 will be supplied to the function insert at the bottom after all calls to reverse, and when the stack is empty, 4 will then be pushed to the stack.
-
The function insert at bottom will then receive 3 and check to see if the stack is empty or not before inserting 3 and pushing the other components back.
-
The function insert at bottom will then receive 2 and check to see if the stack is empty or not before inserting 2 and pushing back the other elements if necessary.
-
The function insert at bottom will then receive 1 and check to see if the stack is empty or not before inserting 1 and pushing back the other components if necessary.
Following are the steps mentioned below to implement reverse a stack using recursion:
- Make a stack and place all the elements inside of it.
- Call the function reverse() to remove every piece from the stack, then feed the removed element to the insert at bottom() function.
- When the function insert at bottom() is invoked, the provided element is inserted at the bottom of the stack.
- Print The Stack Elements.
Code Implementation
#include <stdio.h>
#include <stdlib.h>
#define bool int
// structure of a stack node
struct sNode {
char data;
struct sNode* next;
};
// Function Prototypes
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isEmpty(struct sNode* top);
void print(struct sNode* top);
// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
void insertAtBottom(struct sNode** top_ref, int item)
{
if (isEmpty(*top_ref))
push(top_ref, item);
else {
// Hold all items in Function Call
// Stack until we reach end of the
// stack. When the stack becomes
// empty, the isEmpty(*top_ref)becomes
// true, the above if part is executed
// and the item is inserted at the bottom
int temp = pop(top_ref);
insertAtBottom(top_ref, item);
// Once the item is inserted
// at the bottom, push all
// the items held in Function
// Call Stack
push(top_ref, temp);
}
}
// Below is the function that
// reverses the given stack using
// insertAtBottom()
void reverse(struct sNode** top_ref)
{
if (!isEmpty(*top_ref)) {
// Hold all items in Function
// Call Stack until we
// reach end of the stack
int temp = pop(top_ref);
reverse(top_ref);
// Insert all the items (held in
// Function Call Stack)
// one by one from the bottom
// to top. Every item is
// inserted at the bottom
insertAtBottom(top_ref, temp);
}
}
// Driver Code
int main()
{
struct sNode* s = NULL;
push(&s, 4);
push(&s, 3);
push(&s, 2);
push(&s, 1);
printf("\n Original Stack ");
print(s);
reverse(&s);
printf("\n Reversed Stack ");
print(s);
return 0;
}
// Function to check if
// the stack is empty
bool isEmpty(struct sNode* top)
{
return (top == NULL) ? 1 : 0;
}
// Function to push an item to stack
void push(struct sNode** top_ref, int new_data)
{
// allocate node
struct sNode* new_node
= (struct sNode*)malloc(sizeof(struct sNode));
if (new_node == NULL) {
printf("Stack overflow \n");
exit(0);
}
// put in the data
new_node->data = new_data;
// link the old list
// off the new node
new_node->next = (*top_ref);
// move the head to
// point to the new node
(*top_ref) = new_node;
}
// Function to pop an item from stack
int pop(struct sNode** top_ref)
{
char res;
struct sNode* top;
// If stack is empty then error
if (*top_ref == NULL) {
printf("Stack overflow \n");
exit(0);
}
else {
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}
// Function to print a
// linked list
void print(struct sNode* top)
{
printf("\n");
while (top != NULL) {
printf(" %d ", top->data);
top = top->next;
}
}
#include <bits/stdc++.h>
using namespace std;
void insert_at_bottom(stack<int>& st, int x)
{
if (st.size() == 0) {
st.push(x);
}
else {
// All items are held in Function Call
// Stack until we reach end of the stack
// When the stack becomes empty, the
// st.size() becomes 0, the above if
// part is executed and the item is
// inserted at the bottom
int a = st.top();
st.pop();
insert_at_bottom(st, x);
// push allthe items held in
// Function Call Stack
// once the item is inserted
// at the bottom
st.push(a);
}
}
// Below is the function that
// reverses the given stack using
// insert_at_bottom()
void reverse(stack<int>& st)
{
if (st.size() > 0) {
// Hold all items in Function
// Call Stack until we
// reach end of the stack
int x = st.top();
st.pop();
reverse(st);
// Insert all the items held
// in Function Call Stack
// one by one from the bottom
// to top. Every item is
// inserted at the bottom
insert_at_bottom(st, x);
}
return;
}
// Driver Code
int main()
{
stack<int> st, st2;
// push elements into
// the stack
for (int i = 1; i <= 4; i++) {
st.push(i);
}
st2 = st;
cout << "Original Stack" << endl;
// printing the stack after reversal
while (!st2.empty()) {
cout << st2.top() << " ";
st2.pop();
}
cout<<endl;
// function to reverse
// the stack
reverse(st);
cout << "Reversed Stack" << endl;
// printing the stack after reversal
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
return 0;
}
import java.util.Stack;
class Test {
// using Stack class for
// stack implementation
static Stack<Character> st = new Stack<>();
// Below is a recursive function
// that inserts an element
// at the bottom of a stack.
static void insert_at_bottom(char x)
{
if (st.isEmpty())
st.push(x);
else {
// All items are held in Function
// Call Stack until we reach end
// of the stack. When the stack becomes
// empty, the st.size() becomes 0, the
// above if part is executed and
// the item is inserted at the bottom
char a = st.peek();
st.pop();
insert_at_bottom(x);
// push allthe items held
// in Function Call Stack
// once the item is inserted
// at the bottom
st.push(a);
}
}
// Below is the function that
// reverses the given stack using
// insert_at_bottom()
static void reverse()
{
if (st.size() > 0) {
// Hold all items in Function
// Call Stack until we
// reach end of the stack
char x = st.peek();
st.pop();
reverse();
// Insert all the items held
// in Function Call Stack
// one by one from the bottom
// to top. Every item is
// inserted at the bottom
insert_at_bottom(x);
}
}
// Driver Code
public static void main(String[] args)
{
// push elements into
// the stack
st.push('1');
st.push('2');
st.push('3');
st.push('4');
System.out.println("Original Stack");
System.out.println(st);
// function to reverse
// the stack
reverse();
System.out.println("Reversed Stack");
System.out.println(st);
}
}
def insertAtBottom(stack, item):
if isEmpty(stack):
push(stack, item)
else:
temp = pop(stack)
insertAtBottom(stack, item)
push(stack, temp)
# Below is the function that
# reverses the given stack
# using insertAtBottom()
def reverse(stack):
if not isEmpty(stack):
temp = pop(stack)
reverse(stack)
insertAtBottom(stack, temp)
# Below is a complete running
# program for testing above
# functions.
# Function to create a stack.
# It initializes size of stack
# as 0
def createStack():
stack = []
return stack
# Function to check if
# the stack is empty
def isEmpty(stack):
return len(stack) == 0
# Function to push an
# item to stack
def push(stack, item):
stack.append(item)
# Function to pop an
# item from stack
def pop(stack):
# If stack is empty
# then error
if(isEmpty(stack)):
print("Stack Underflow ")
exit(1)
return stack.pop()
# Function to print the stack
def prints(stack):
for i in range(len(stack)-1, -1, -1):
print(stack[i], end=' ')
print()
# Driver Code
stack = createStack()
push(stack, str(4))
push(stack, str(3))
push(stack, str(2))
push(stack, str(1))
print("Original Stack ")
prints(stack)
reverse(stack)
print("Reversed Stack ")
prints(stack)
Output
Original Stack
4 3 2 1
Reversed Stack
1 2 3 4Complexity Analysis
Time Complexity: The time complexity to reverse stack using recursion is O(N**2).
Auxiliary Space: The space complexity to reverse a stack using recursion is O(N).
FAQs Related To Reverse A Stack Using Recursion
1. Why is the time complexity to reverse a stack using recursion is O(n²)?
We are popping the entire stack out and setting the top element at the bottom for each element on the stack, which requires O(n) operations. For each value in the stack, these O(n) operations are carried out, resulting in a quadratic time complexity.
2. How will the top element be added to the bottom of the stack?
Until the stack is empty, we pop each element at the top and put it in the call stack frame. When the stack is empty, we place the top element there before pushing all of the call stack frame’s elements and returning to the top of the recursive tree.
3. How do I reverse one stack with the help of another stack?
Reversing a stack is possible since it is a first-in-last-out (FILO) data structure. To do this, continually remove the top element and push it into another stack. Simply swap out the original stack for the reversed one when finished.
4. Can a stack be FIFO?
The main distinction between stack and queue data structures is that while queue uses a FIFO data structure type, stack uses LIFO. Last In First Out is referred to as LIFO. It implies that the last element is processed first when data is added to a stack. On the other hand, FIFO stands for First In First Out.