# Reverse A Stack Using C++ [Easy Implementation]

Filed Under: C++

In this article, we will learn to reverse a stack using C++. Stacks are an indispensable part of the data structures and algorithm courses. Generally, students find it difficult to master recursion. Don’t worry, we will help you glide through your DSA course with ease. First, we will go through the problem statement and then move to the concept and the algorithm. So without any delay, let’s get started.

## Problem Statement

You are given a stack, you have to reverse it using constant space.

For example,

```Stack:
Top --> |1|--> |2|--> |3|--> |4|--> |5|--> |6|--> |7|--> |8|--> |9|--> Bottom
Solution:
Top--> |9|--> |8|--> |7|--> |6|--> |5|--> |4|--> |3|--> |2|--> |1|--> Bottom

Stack:
Top--> |10|--> |30|--> |90|--> |40|--> |70|--> |50|--> |20|--> Bottom
Solution:
Top--> |20|--> |50|--> |70|--> |40|--> |90|--> |30|--> |10|--> Bottom
```

## Concept of Reversing A Stack

As indicated earlier, we will solve this problem using a recursive approach. We will create two recursive functions to do this task. The first will be `reverse_stack` and the second will be `insert_at_bottom`. Below are the steps which explain in detail the working of these functions.

Note: In this algorithm, we will take the help of the heap memory of the program to store the intermediate states. This is because we are not using any additional space to store the stack.

• Recursively call the function reverse_stack until the stack becomes empty.
• Base case: if(stack.empty())
• return from here
• Recursive case:
• Store the top element using a variable and remove it from the stack.
• int top = stk.top()
• stack.pop()
• Keep calling the same function until we hit the base case.
• reverse_stack(stack)
• After this step, insert the topmost element at the bottom
• insert_at_bottom(stack, top)
• The work is over, finally, return from the function

Now let’s discuss the working of the insert_at_bottom(stack, x) function.

• Base case: If the stack is empty, push the current element into it and return
• if(stack.empty())
• stack.push(x)
• Otherwise, we will proceed in the following manner
• First, make empty this stack and then insert the current element at the bottom
• int data = stack.top()
• stack.pop()
• Then, recursively insert x at the bottom
• insert_at_bottom(stack, x)
• Finally, insert the topmost element back into the stack
• stack.push(data)
• Return from the function
• return

## Algorithm for Reversing A Stack

```void insert_at_bottom(stack <int> &stk, int x)
{
// base case
if(stk.empty())
{
stk.push(x);
return;
}

// recursive case
// store and remove the top element
int data = stk.top();
stk.pop();

// now recursively insert x at the
// bottom of the remaining stack
insert_at_bottom(stk, x);

// once this is over, just
// insert the top element back
stk.push(data);

return;
}

void reverse_stack(stack <int> &stk)
{
// base case
if(stk.empty())
return;

// recursive case
// store the topmost element
int top_ele = stk.top();

// remove the topmost element
stk.pop();

// recursively reverse the smaller
// stack first
reverse_stack(stk);

// once done, insert the top
// most element at the bottom
insert_at_bottom(stk, top_ele);

//finally return
return;
}
```

## Reverse A Stack Using C++ – A Complete Implementation

Let’s get started with implementing a reverse stack program using C++.

```#include <iostream>
#include <stack>

using namespace std;

// notice that we are passing the stack
// by reference, just to make sure that
// the changes reflect into the actual
// stack after the function calls

void insert_at_bottom(stack <int> &stk, int x)
{
// base case
if(stk.empty())
{
stk.push(x);
return;
}

// recursive case
// store and remove the top element
int data = stk.top();
stk.pop();

// now recursively insert x at the
// bottom of the remaining stack
insert_at_bottom(stk, x);

// once this is over, just
// insert the top element back
stk.push(data);

return;
}
void reverse_stack(stack <int> &stk)
{
// base case
if(stk.empty())
return;

// recursive case
// store the topmost element
int top_ele = stk.top();

// remove the topmost element
stk.pop();

// recursively reverse the smaller
// stack first
reverse_stack(stk);

// once done, insert the top
// most element at the bottom
insert_at_bottom(stk, top_ele);

//finally return
return;
}

void print_stack(stack <int> stk)
{
cout << "|Top-->|";

while(!stk.empty())
{
cout << stk.top() << "|-->|";
stk.pop();
}
cout << "Bottom|" << endl;
}

int main()
{
cout << "Enter the elements, press -1 to stop" << endl;

stack <int> stk;

while(true)
{
int ele;
cin >> ele;

if(ele == -1)
break;

stk.push(ele);
}

cout << "Initially the stack is:" << endl;
print_stack(stk);

reverse_stack(stk);

cout << "Stack after reversing is:" << endl;
print_stack(stk);

return 0;
}
```

## Conclusion

In this article, we learned to reverse a stack using C++. The algorithm that we coded reverses the stack in place, i.e. no extra space is needed. First, we looked at the problem statement, then we understood the concept. In the end, we coded the algorithm and a driver C++ program to test its working.