数据结构与算法之-----栈的应用（一）

前言

写在前面的话：数据结构与算法。

1. 对于初识数据结构的小伙伴们，鉴于后面的数据结构的构建会使用到同tag前面的内容，包括具体数据结构的应用，所使用到的数据结构，也是自己构建的，未使用系统的库文件，因此，建议这类小伙伴们按顺序进行学习；

2. 对于想查询有关资料的小伙伴们，可以选择性地浏览。希望大家都能有所收获～

栈的应用（一）

上一章我们简单的介绍了栈这种数据结构，下面，我们来看看它的第一个应用：

问题：如何将一个十进制数转化为n进制数？

代码实现较为容易：

/*
 * 作者：易果啥笔
 * 时间：2021.8.20
 * 内容：栈的应用一： 任给一个十进制数n，将其转换为某进制的表示形式
 *
 */

#ifndef STACK_BASECONVERSION_H
#define STACK_BASECONVERSION_H
#include "Stack.h"

//递归实现

//    void convert(Stack<char>& S,__int64_t n,int base){
//        static char digit[]
//            ={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
//        if(n<0){
//            convert(S,n/base,base);
//            S.push(digit[n/base]); //输出低位
//        }
//    }


//迭代实现
void convert(Stack<char>& S,int n,int base){
    static char digit[]
            ={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    while(n>0){
        int remainder = (int) (n%base);
        S.push(digit[remainder]);
        n /= base;
    }
}

//新进制下，出栈的元素与真实结果的方向相反，故Stack.h的父类Vector类里需修改traverse的输出方向

#endif //STACK_BASECONVERSION_H

笔者提供了两种实现方式，递归和迭代，两种方式各有优点：

• 递归能使代码变得更简洁，但内存开销相对较大；

• 迭代代码虽相对复杂，但内存开销相对较小。

此应用相对比较容易实现，无需过多的解释。