Program Reverse a String using Stack in C++

Problem: Given a String, reverse the given string using stack. 

Input: str = "algolesson"
Output: str = "nosselogla"

Input: str = "orange"
Output: str = "egnaro"

Steps to reverse the string using stack.

• Create one empty Stack.
• Push all the characters of the given string one by one into the stack.
• Create a new empty string.
• Add the top character of the stack to the empty string then pop the top character.  
• Repeat the fourth step until the stack gets empty and you will get the reverse of the given string.

Example: C++ Code to reverse a string using stack.

//C++ Program to reverse String using Stack

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

int main()
{
    string str = "orange";
    stack<char> sc;
    string s = "";
    //push all the char to the stack
    for (int i = 0; i < str.size(); i++)
    {
        sc.push(str[i]);
    }
    //pop all the char from the stack

    // and add then to new empty string.
    while (!sc.empty())
    {
        s += sc.top();
        sc.pop();
    }
    cout << "Reverser String " << s << endl;
}

Output:

Reverser String egnaro

• Time Complexity: O(n)
• Space Complexity: O(n)

As you can see that we are using extra space to reverse the given string which means that this is not an efficient algorithm because we solve the same problem without using any extra space and without using a stack. 

Example: C++ Code to reverse a string without using extra space and without using stack.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str = "orange";

    //size of the given string
    int n = str.size();
    
    for (int i = 0; i < n / 2; i++)
    {
        swap(str[i], str[n - 1 - i]);
    }
    cout << "Reverse String " << str << endl;
}

Output:

Reverse String egnaro

Time Complexity: O(n).

Space Complexity: O(1)