Reverse a Stack Using Recursion

Introduction

We'll use recursion to reverse a stack in this example. Loop constructions such as for loop, while loop, do-while loop, and so on are not allowed. To reverse a stack using recursion, we should utilize the method.

For example:

input: s = [100, 200, 300, 400, 500]

Output: [500, 400, 300, 200, 100]

Recursion can be used in a variety of ways to reverse a stack. Using an auxiliary stack to reverse a stack is the most popular method. We'll remove all components from the stack and move them to the extra stack. After all of the items have been pushed into the auxiliary stack, it includes the elements in reverse order, which we can then print. However, we will not use the extra stack in this case. We'll utilize a recursion method to reverse a stack, where recursion means repeatedly running the function.

We pop all the components of the input stack and push all the popped things into the function call stack until the stack is empty in the recursion procedure. When the stack is empty, all things are pushed towards it. Let's look at an example to comprehend this situation better.

Example:

The solution's goal is to keep all values in the Function Call Stack until it is empty. When the stack is empty, place all held items at the bottom of the stack.

For example:

Lets take the input stack to be: s = [100, 200, 300, 400, 500]

The first 400 are inserted at the bottom.

Then 400 is inserted at the bottom, then 300, and so on.

So we'll need a function that uses the basic stack function to insert at the bottom of a stack.

void insertAtBottom(()): Uses recursion to pop all stack items and store the popped item in the function call stack. When the stack is empty, it pushes a new item, and all the items on the call stack.

void reverse(): This function mostly uses insertAtBottom() to pop each item and place them at the bottom.

Code:

#include

using namespace std;

stack stk;

string rev_string;

// Give below is a recursive function that inserts an element at the bottom of a stack.

void insert_bottom(char x)

{

if(stk.size() == 0)

stk.push(x);

else

{

char x = stk.top();

stk.pop();

insert_bottom(x);

stk.push(x);

}

}

//Given below is the function that reverses the given stack using insert_bottom()

void reverse()

{

if(stk.size())

{

// Store all items in Function Call Stack until we reach end of the stack

char x = stk.top();

stk.pop();

reverse();

// Insert all the items help  in Function Call Stack one by one from the bottom

// to top. Every item is inserted at the bottom

insert_bottom(x);

}

}

// Driver Code

int main()

{

stk.push('100');

stk.push('200');

stk.push('300');

stk.push('400');

cout<<"Input Stack"<

// print the elements  of original stack

cout<<"100"<<" "<<"200"<<" "

<<"300"<<" "<<"400"<

// Below function is used to reverse the stack

reverse();

cout<<"Output Reversed Stack"<

// storing values of reversed stack into a string for output

while(!stk.empty())

{

char p=st.top();

stk.pop();

rev_string+=p;

}

//display of reversed stack

cout<

        "   "<

return 0;

}

That's all from the article. I hope you all like it.