#include <iostream>
using namespace std;
const int MAX_SIZE = 32; // 最大栈容量，对应32位二进制数

// 使用数组模拟栈结构
int stack[MAX_SIZE]; // 栈数组
int top = -1;        // 栈顶指针，-1表示空栈

// 入栈函数
void push(int value) {
    if (top < MAX_SIZE - 1) { // 检查栈是否已满
        top++;                // 栈顶上移
        stack[top] = value;   // 存入数据
    }
}

// 出栈函数
int pop() {
    if (top >= 0) {           // 检查栈是否为空
        int value = stack[top]; // 取出栈顶数据
        top--;                // 栈顶下移
        return value;         // 返回取出的数据
    }
    return -1; // 栈为空时返回-1
}

// 检查栈是否为空
bool isEmpty() {
    return top == -1; // 栈顶为-1表示空栈
}

// 十进制转二进制函数
void decimalToBinary(int number) {
    // 特殊情况：如果输入是0，直接输出0
    if (number == 0) {
        cout << "0 -> 0" << endl;
        return;
    }
    
    int original = number; // 保存原始数字，用于最后输出
    
    // 处理负数：如果是负数，先转成正数处理
    bool isNegative = false;
    if (number < 0) {
        isNegative = true;
        number = -number; // 变成正数
    }
    
    // 核心算法：除2取余法
    // 不断除以2，把余数存入栈中
    while (number > 0) {
        int remainder = number % 2; // 求余数
        push(remainder);            // 余数入栈
        number = number / 2;        // 更新为商
    }
    
    // 输出结果
    cout << original << " -> ";
    
    // 如果是负数，先输出负号
    if (isNegative) {
        cout << "-";
    }
    
    // 从栈中依次取出所有数字（这就是二进制结果）
    while (!isEmpty()) {
        cout << pop(); // 出栈并输出
    }
    
    cout << endl;
}

int main() {
    // 测试不同的数字
    cout << "十进制转二进制演示：" << endl;
    cout << "==================" << endl;
     
    decimalToBinary(10);   // 10的二进制是1010
    decimalToBinary(42);   // 42的二进制是101010
    decimalToBinary(0);    // 0的二进制是0
    decimalToBinary(15);   // 15的二进制是1111
    decimalToBinary(255);  // 255的二进制是11111111
    decimalToBinary(-15);  // -15的二进制是-1111
    
    return 0;
}

1. 栈类(Stack)设计 • 数据存储：使用固定大小数组data[MAX_SIZE] • 栈顶指针：top初始为-1，采用"先移动后操作"的原则 • 关键操作： o push()：入栈前检查栈满 o pop()：出栈前检查栈空 o isEmpty()：通过top值判断栈状态
2. 转换算法核心 - 除2取余法 text 转换过程示例（10转二进制）： 10 ÷ 2 = 5 ... 0 ↑ 5 ÷ 2 = 2 ... 1 ↑
   2 ÷ 2 = 1 ... 0 ↑ 1 ÷ 2 = 0 ... 1 ↑ 从下往上读：1010
3. 关键实现细节 • 负数处理：先转换为正数计算，最后添加负号 • 栈的作用：利用LIFO特性反转余数顺序 • 边界处理：单独处理0的情况
4. 输出示例 text 10 -> 1010 42 -> 101010 0 -> 0 -15 -> -1111
5. 算法特点 • 时间复杂度：O(log n)，其中n为输入数值 • 空间复杂度：O(1)，使用固定大小的栈 • 局限性：负数处理采用简单方法，实际计算机中使用补码表示 这个实现很好地展示了栈在进制转换中的经典应用，通过后进先出的特性自然实现了余数的逆序输出。