Last Updated: Mar 27, 2024
Difficulty: Easy

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;
}``````

Output:

``Reversed Number: 5452``

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)``````

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.

What is the greedy approach?

It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution.

Why is Stack a recursive data structure?

A stack is a recursive data structure; it's either empty or made up of a top and the remainder, a stack in and of itself.

Why are stacks useful?

They're helpful because they allow you to insert or remove data from the front of a data structure in constant time O(1) operations. A stack is commonly employed in compilers to ensure that all brackets and parentheses in a code file are balanced, that is, that they have an opening and closing counterpart. Mathematical expressions can also be evaluated using stacks.

How to Linked List using Stack?

Two stacks can be used to imitate a linked list. The "list" stack is one, while the "temporary storage" stack is the other.

• Push an item into the Stack to add it to the top.
• Pop the Stack from the head to remove it.
• To insert somewhere in the middle, pop items off the "list" Stack and place them on the temporary Stack until you reach your insertion point.
• Push the new item to the "list" Stack, remove it from the temporary Stack and re-add it to the "list" Stack. An arbitrary node can be deleted similarly.

Conclusion

In this article, we discussed a very interesting problem, in which we have to reverse the decimal number given to us using the stack data structure.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

You can also consider our Mern Stack Course to give your career an edge over others.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Topics covered
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Solution Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.3.
Implementation in Python
2.3.1.
Complexity Analysis
3.