Reverse a number using Stack

Introduction 

This article will discuss the problem of reversing the decimal number using the Stack; before reading the problem statement, let's first discuss in brief what is a stack data structure. 

Stack: A stack is a linear data structure in which operations are carried out in a specific order. The sequence could be LIFO (Last In First Out) or FILO (First In Last Out) (First In Last Out). To study more about the Stack, you can refer to this blog on coding ninjas. 

Problem Statement

The problem states that we are given a number N, and we need to reverse a number N using the stack data structure. To understand more clearly, let's discuss the sample examples. 

Sample Examples 

Input 1:

N = 2545 

Output 1:

5452 

Explanation: 

When the number 2545 is reversed, the output will be 5452.    

Input 2: 

N = 36 

Output 2: 

63 

Explanation:

When the number 36 is reversed, the output will be 63.    

Solution Approach 

The idea is simple; we will declare one Stack. We will push each digit of a number N in the stack data structure. Since the Stack is LIFO, when we pop out all the digits from the Stack, the new number formed will be in reverse order.   

Steps of Algorithm 

• Initialize the empty Stack S. 
• Push all the digits of the number N into the Stack 
• Keep on popping the number from the Stack, and make the reversed number by multiplying the popped number by a power of 10 and adding the number formed till now. 
• Keep on performing the process until the Stack becomes empty, and hence we will obtain the revered number

Implementation in C++

// c++ program to reverse the number using stack
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 2545;
    // declaring the empty stack
    stack<int> st;

    // pushing the digits into the stack
    while (n > 0)
    {
        st.push(n % 10);
        n /= 10;
    }
    // we will store the reverse number into this variable
    int ans = 0;

    // intializing to multiply with the power of 10
    int i = 1;
    // now start popping from the
    // stack, until stack becomes empty
    while (!st.empty())
    {
        int val = st.top();
        st.pop();
        ans = ans + val * i;
        i = i * 10;
    }
    // printing the reverse number
    cout << "Reversed Number: " << ans << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Reversed Number: 5452

Must Read Stack Operations

Implementation in Python

from queue import Empty

n = 2545
# declaring the empty stack
stack = []
# pushing the digits into the stack
while n > 0:
    stack.append(n % 10)
    n = int(n/10)
# we will store the reverse number into this variable
ans = 0
# intializing to multiply with the power of 10
i = 1
# now start popping from the
# stack, until stack becomes empty
while len(stack) > 0:
    val = stack.pop()
    ans = ans + val*i
    i = i*10
# printing the reverse number
print(ans)

You can also try this code with Online Python Compiler

Run Code

Output:

5452

Complexity Analysis

Time Complexity: O(log(N))

Each time number is divided by 10, so the overall complexity is log10(N). 

Space Complexity: O(log(N))

We will maximally store log(N) digits into the stack data structure. 

Must Read  C Program to Reverse a Number.