Embedded Prep

Reverse a Stack Using Recursion : Stacks are an important data structure in programming. They work like a stack of plates — you can only add or remove plates from the top. This behavior is called LIFO (Last In, First Out).

Sometimes, you might want to reverse a stack, so the element that was at the top moves to the bottom and vice versa. But how do you reverse a stack without using extra memory or another stack? The answer is recursion!

In this article, we’ll learn how to reverse a stack using recursion by inserting elements at the bottom.

What is a Stack?

A stack allows only two main operations:

• push(x): Add element x to the top.
• pop(): Remove the top element.

You cannot directly access or modify elements below the top.

Problem Statement

Given a stack, reverse the order of elements using recursion. For example:

Original stack (top to bottom):
5, 4, 3, 2, 1

After reversing, the stack should be:
1, 2, 3, 4, 5

Key Idea: Insert at Bottom

Since we can only add or remove elements from the top, how do we insert an element at the bottom?

We use recursion:

1. If the stack is empty, push the element — that’s the bottom.
2. Otherwise, pop the top element, call the function recursively to insert the element at the bottom, then push the popped element back on top.

This way, the new element ends up at the bottom, and the original elements remain on top.

Step-by-Step Solution

1. Write a function to insert an element at the bottom:

void insertAtBottom(stack<int> &st, int x) {
    if (st.empty()) {
        st.push(x);  // If empty, push element (bottom)
        return;
    }
    
    int topElement = st.top();
    st.pop();  // Remove top element
    
    insertAtBottom(st, x);  // Recursive call
    
    st.push(topElement);  // Push the popped element back on top
}

2. Write a function to reverse the stack:

void reverseStack(stack<int> &st) {
    if (st.empty()) return;  // Base case
    
    int topElement = st.top();
    st.pop();  // Remove top
    
    reverseStack(st);  // Reverse remaining stack
    
    insertAtBottom(st, topElement);  // Insert removed element at bottom
}

How Does This Work?

• reverseStack() keeps popping the top element until the stack is empty.
• Then it starts inserting each popped element at the bottom of the stack.
• This reverses the order because the first popped element (which was originally on top) goes to the bottom.

Full Working Code

#include <iostream>
#include <stack>
using namespace std;

// Insert element x at the bottom of stack st
void insertAtBottom(stack<int> &st, int x) {
    if (st.empty()) {
        st.push(x);
        return;
    }
    int topElement = st.top();
    st.pop();
    insertAtBottom(st, x);
    st.push(topElement);
}

// Reverse the stack using recursion
void reverseStack(stack<int> &st) {
    if (st.empty()) return;
    int topElement = st.top();
    st.pop();
    reverseStack(st);
    insertAtBottom(st, topElement);
}

// Print stack elements from top to bottom
void printStack(stack<int> st) {
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
}

int main() {
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);

    cout << "Original Stack: ";
    printStack(st);

    reverseStack(st);

    cout << "Reversed Stack: ";
    printStack(st);

    return 0;
}

Output:

Original Stack: 5 4 3 2 1
Reversed Stack: 1 2 3 4 5

Conclusion

By cleverly using recursion, we can reverse a stack without using any extra data structure like another stack or array.

The trick lies in the helper function insertAtBottom() which helps us insert an element at the bottom of the stack, allowing us to place elements in reverse order during recursion unwinding.

If you want to practice further, try these exercises:

• Write a function to reverse a stack without recursion (using an extra stack or queue).
• Modify the code to reverse a stack of strings instead of integers.