【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

栈

by.Qin3Yu

下面的文章将通过使用栈完成辗转相除法转换十进制数为二四八进制来简要描述和解释栈。
特别声明：本文仅通过简单的例子帮助新手快速了解栈，包括且不限于完成家庭作业等水平，内容讲究简单明了，我妈看了都能学会！
如果您是进阶级别，请参阅其他大佬的详细教学。
文中所有代码默认已使用std命名空间

ps.简要介绍辗转相除法

• 辗转相除法，也称为欧几里德算法，是一种用于求解两个整数的最大公约数的算法。它也可以应用在将十进制数转换为其他进制数的过程中。

• 以将十进制数转化为二进制数为例，辗转相除法的原理如下：

1. 将给定的十进制数除以2，获得商和余数。
2. 将商作为新的被除数，再次除以2，并再次计算商和余数。
3. 重复上述步骤，直到商为0。
4. 最后，逆序排列获得的余数，即为十进制数转化的二进制数。

• 同样，可以使用辗转相除法将十进制数转化为4进制和8进制数。

本文只介绍栈，不会在下文继续介绍辗转相除法，若需要了解更多信息，请参阅其他大佬的详细教学

什么是栈？

• 栈是一种数据结构，你可以将它看成是一个与数组一样存储数据的容器，与其他数据类型不同的是，它遵循“后进先出”的原则，即最后进入栈的元素会先被取出。
• 就和糖罐一样，最后放进去的糖永远在糖堆的最上面，所以将会最先被从糖罐中取出来。

优势：

1. 栈的基本操作非常简单，只需要考虑元素的入栈和出栈即可，因此实现起来相对容易。
2. 栈的插入和删除操作（即入栈和出栈）都可以在常数时间内完成，无论栈的规模有多大，这使得栈在特定场景下非常高效。
3. 由于栈采用后进先出的原则，栈上的数据可以自动释放，因此不会出现内存泄漏的问题。

缺点：

1. 栈的容量是有限的，一旦达到最大容量，就无法再添加新的元素，这可能会导致栈上溢（Stack Overflow）的问题。
2. 栈中的元素只能按照先入后出的顺序访问，没有提供随机访问的能力，因此无法直接获取栈中间的元素。

• 此外，使用栈还要导入以下头文件：

#include <stack>

声明一个栈（ stack ）

• 我们可以直接在函数中使用 stack<T> name 声明一个栈，其中T表示栈中存放数据的类型，name表示栈的名字。在本文中，我们使用名为sk的整型栈来举例：

stack<int> sk;  //声明一个名为sk的int类型栈

数据入栈（ push ）

• 现在我们已经有了一个空的栈，我们可以用 sk.push(val) 来向栈顶放入元素，这个操作称为入栈，最后放入的元素将会被最先取出，在本文中，我们只向栈内放入大于0的整数：

while (x > 0) {
    sk.push( x );  //将x放入栈中
}

获取栈顶值（ top ）和出栈（ pop ）

• 现在我们的栈中已经有了元素，我们可以通过 sk.top() 来获取栈顶元素的值。通常来说，我们获取了它的值以后，他就没有在栈中的必要了（坏笑），所以我们可以通过 sk.pop() 来删除栈顶元素，这个操作通常被称为出栈或弹出。
• top 只能获取值，pop 只能删除元素，所以不难看出， top 和 pop 常常 搭配使用：

cout << sk.top();  //输出sk栈顶元素的值
sk.pop();  //然后再将其从栈中删除（出栈）

判断是否空栈（ empty ）

• 在实际操作中，我们往往不知道栈内会出现多少元素，所以在进行出栈操作时，我们可以用 sk.empty() 判断这个栈是否是空栈。此方法会返回一个bool值，如果栈内是空的，则返回true，如果栈内还有元素，就返回false。通常会用此作为循环的条件来将栈内元素全部弹出：

while (!sk.empty()) {  //如果不是空栈就继续循环
    cout << sk.top();  //输出栈顶元素值
    sk.pop();  //弹出栈顶元素
}

完整的代码演示如下：

题目：使用栈完成以下功能：输入一个十进制数，由用户选择将它转换为2、4、8进制数的其中一种。

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

//这里我将栈的相关操作单独写在changeBase方法中，以便读者单独理解
void changeBase(int x, int base) {
    stack<int> sk;  //声明一个存储数据类型为int的栈sk
    while (x > 0) {
        sk.push(x % base);  //入栈
        x /= base;
    }
    while (!sk.empty()) {  //判断栈是否为空
        cout << sk.top();  //输出栈的值
        sk.pop();  //出栈
    }
    cout << endl;
}

int main()
{
    while (true) {
        cout << "请输入十进制数（输入0退出）：";
        int x; cin >> x;
        if (x == 0)
            break;
        cout << "请输入要转换的进制（2、4、8）：";
        int base; cin >> base;
        cout << "转换后的数为：";
        changeBase(x, base);  //传入两个参数，一个是十进制数x，一个是要转换的进制base
    }
    return 0;
}