Convert Decimal Number to Binary Using Stacks in C++

Decimal numbers are the set of numbers with base 10, whereas binary numbers are the numbers with base 2. In this article, we will learn how to convert a decimal number to a binary number using stack data structure in C++ program. First of all, let's understand how decimal to binary conversion technique works.

Decimal to Binary Conversion Technique

To convert a decimal number to a binary number follow the steps below:

• Divide the decimal number by 2
• Save the reminder (either 1 or 0) in a place.
• Now, update the decimal number with the quotient of the division.
• Repeat the above steps until the number becomes zero.
• The binary number of the given decimal number will be the sequence of the reminders taken in reverse order.

For example, consider that we need to convert the decimal number 13 to it's binary form. The table below shows how division works for the conversion.

In this example, the initial decimal number 13 is divided by 2 to get 1 as reminder and 6 as quotient, which then again divided by 2 and so on. The final set of reminders we got is "10110". The reverse of this sequence reminders is binary equivalent of 13. That is, the binary number for 13 is 1101.

Now, let's see how to write a program that uses stack data structure to convert decimal number to binary number.

Algorithm: Convert Decimal to Binary Using Stack

Following are steps to write a program to convert decimal to binary using stack.

• Step 1: Create an empty stack.
• Step 2: Repeat steps 3 and 4 until decimal number 'n' is greater than 0:
• Step 3: Push n%2 (ie, the reminder) into the stack.
• Step 4: Update n=n/2
• Step 5: Pop out all the elements from stack to get the required binary number.

C++ Code: Convert Decimal to Binary Using Stack

The code below shows implementation of above algorithm in C++

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

void decimalToBinary(int n) {
    stack<int> binaryStack;

    if (n == 0) {
        cout << "0";
        return;
    }

    while (n > 0) {
        binaryStack.push(n % 2);
        n /= 2;
    }

    while (!binaryStack.empty()) {
        cout << binaryStack.top();
        binaryStack.pop();
    }
}

int main() {
    int number=13;
    decimalToBinary(number);
    cout << endl;

    return 0;
}

The output of the above code will be:

1101

Time and Space Complexity

• Time Complexity: O(log n), Where n in length of input string
• Space Complexity: O(log n), Number of binary digits for n is about log n.