6

Reverse A Stack Using C++ [Easy Implementation]

 2 years ago
source link: https://www.journaldev.com/61078/reverse-a-stack-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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 1Algorithm 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 CodeDriver Code

Output

Stack Reverse OutputStack 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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK