Reverse A Stack Using C++ [Easy Implementation]

Filed Under: C++
Reverse A Stack Using 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;
}
Algorithm 1
Algorithm 1

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;
}
Driver Code
Driver Code

Output

Stack Reverse Output
Stack Reverse Output

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.

Further Readings

To learn more about recursion or stack, you can go through the following articles.

https://www.journaldev.com/56477/stack-class-cpp

https://www.journaldev.com/56918/0-1-knapsack-using-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content