Last Updated on October 18, 2023 by Ankit Kochar
In this tutorial, we will delve into a well-known problem in data structures: "Reversing a Stack Using Recursion." If you have a good understanding of both stacks and recursion, tackling this task won’t be overly complex. Rest assured, we’ll cover the essentials, including explanations of what a stack is, the concept of recursion, and the step-by-step process of reversing a stack using recursive techniques. Let’s start by exploring the definition of a stack.
What is a Stack?
The Stack, a linear data structure, operates based on the Last-In-First-Out (LIFO) principle. This structure possesses a singular end, known as the rear end, and a lone pointer referred to as the top pointer, which indicates the highest element within the stack. Whenever an element is introduced into the stack, it is consistently placed atop the stack, and the only operation permissible for removal is from the stack’s uppermost part. In simpler terms, a stack serves as a receptacle permitting the addition and elimination of elements solely from one extremity, which is the uppermost section of the stack.
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.
It’s important to note that a standard stack primarily involves two key operations at its top: the "push" and "pop" operations. Consequently, when the objective is to reverse a stack, the approach involves systematically performing "pop" operations on each element and transferring them one by one to a separate auxiliary stack. Ultimately, this auxiliary stack will contain the same elements as the original stack but in the reverse order.
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).
Conclusion
Reversing a stack using recursion is a valuable problem-solving exercise in data structures and algorithms. This process leverages the Last-In-First-Out (LIFO) principle of stacks and the recursive nature of the algorithm to achieve the reversal. It involves systematically removing elements from the original stack and placing them onto an auxiliary stack, resulting in the reversal of the stack’s order.
FAQs Related To Reverse A Stack Using Recursion
Below are some of the FAQs related to Reverse a stack using recursion:
1. What is the purpose of reversing a stack using recursion?
The primary purpose is to reverse the order of elements in a stack. This operation can be useful in various scenarios, such as solving certain algorithmic problems or implementing specific data structure operations.
2. Can you reverse a stack using iteration instead of recursion?
Yes, it is possible to reverse a stack using iteration, but recursion often provides a more elegant and intuitive solution. The recursive approach mirrors the natural behavior of a stack (LIFO) and is frequently preferred.
3. What is the time complexity of reversing a stack using recursion?
The time complexity of reversing a stack using recursion is O(n), where "n" is the number of elements in the stack. This is because each element is pushed and popped once during the reversal process.
4. Are there any limitations or drawbacks to using recursion for stack reversal?
Recursive solutions may consume additional memory due to the recursive function calls, which can be a limitation for very large stacks. However, this is generally not a concern for most practical scenarios.
5. Can you provide a high-level overview of the steps involved in reversing a stack using recursion?
Certainly. The process involves recursively removing elements from the original stack while preserving them on an auxiliary stack. Once all elements are moved to the auxiliary stack, they are popped back onto the original stack, effectively reversing the order.
6. Are there any practical applications for reversing a stack in real-world programming?
Reversing a stack can be a useful component of more complex algorithms or data structure operations. For example, it can be employed in solving problems related to expression evaluation or creating specialized data structures.