Menu Close

Reverse a stack using recursion

In this tutorial, We are going to learn how to reverse a stack using recursion.

Algorithm to reverse a stack using recursion:

  • Take input from user and insert elements into stack
  • Pop all elements from stack using recursion
  • Create one more stack and insert elements into new stack.
  • Before inserting, First pop all the elements using recursion. 
  • Now, insert new element from bottom.

Code:

#include <iostream>
#include <stack>

using namespace std;

void insert_at_bottom_into_stack(stack<int> *s, int data) {

    if ((*s).empty()) {

        (*s).push(data);

        return;
    }

    int top = (*s).top();

    (*s).pop();

    insert_at_bottom_into_stack(s, data);

    (*s).push(top);
}

void reverse_stack(stack<int> *s) {

    if (!(*s).empty()) {

        int data = (*s).top();

        (*s).pop();

        reverse_stack(s);

        insert_at_bottom_into_stack(s, data);

    }
}

int main() {

    int element_number, element;

    stack<int> s;
    
    cout<<"Enter number of elements: ";

    cin>>element_number;
    
    for(int index = 0; index < element_number; index++) {

        cout<<"\n";

        cin>>element;

        s.push(element);
    }
    
    // Function to reverse the stack
    reverse_stack(&s);
    
    cout<<"\nStack elements after reverse: \n\n";

    while(!s.empty()) {

        cout<<s.top()<<"\n";

        s.pop();
    }
    return 0;
}

Output:

Enter number of elements: 5
1
2
3
4
5

Stack elements after reverse: 

1
2
3
4
5

To learn more about golang, Please refer given below link:

https://www.techieindoor.com/go-lang-tutorial/
https://www.techieindoor.com/go-lang-tutorial/

References:

https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
Posted in C++