简介数据结构中的栈是一种后进先出的线性表其独特的操作顺序使它在解决逆序输出问题时具有天然优势。进制转换作为栈的经典应用场景通过除基取余法产生的余数顺序与书写顺序相反而栈的压栈与弹栈恰好能自动完成这一逆序过程。无论是顺序栈还是链栈都能以O(1)时间复杂度的入栈出栈操作实现高效转换同时覆盖二进制、八进制与十六进制输出。理解这一原理不仅有助于掌握栈的核心特性还能为实际工程中封装自定义进制转换工具提供思路。本文从顺序栈与链栈两种实现出发详细讲解数据结构设计、核心代码与边界处理并结合常见Bug排查帮助读者彻底掌握这一经典算法。顺序栈与链栈实现十进制转二/八/十六进制从思路到源码一次讲透栈这种数据结构平时看起来不起眼但真正用在合适的地方效率高得离谱。进制转换就是一个最典型的例子——你如果去翻任何一本《数据结构》教材讲到栈的应用进制转换基本是必举的例子和括号匹配并列的地位。原因很简单短除法求余出来的数字是逆序的而栈恰好就是后进先出天然帮你把逆序结果倒回来。这周我在整理自己的一套进制转换源码把顺序栈和链栈各写了一遍顺便把二、八、十六进制全部覆盖踩了些细节坑也理清了不少关键点干脆完整复盘一遍。这篇博文适合谁正在学数据结构、被栈的应用题折磨的学生复习考研机试、刷算法题但总是想不起栈怎么用的同学以及工作中需要自己封装进制转换工具、不想用现成库函数的开发者。我会把原理讲明白把代码给全把坑点标清楚你照着敲一遍以后这种题就是送分题。先回答一个最核心的问题为什么偏偏是栈你可以暂时忘掉栈这个概念只记住一件事——短除法的余数是从低位到高位产生的而我们写数字时是从高位往低位读的。这个先后颠倒的问题用数组也能处理存下来再倒序输出但栈结构把这个过程变直觉化了算一个余数压栈算完所有余数一路弹栈出来的就正好是正确顺序。下面我就以这个核心逻辑为线索把两种栈的实现方式完整拆开。1. 整体设计与思路拆解1.1 进制转换的本质除基取余法任何进制转换问题核心都是同一个数学操作不断地用目标进制数去除十进制数取余数再用商继续除直到商为0。这句话看着简单但里面藏着一个非常关键的细节余数的产生顺序和书写顺序是相反的。我拿一个具体例子走一遍。把十进制数 13 转成二进制13 ÷ 2 6 余 1这是最低位6 ÷ 2 3 余 03 ÷ 2 1 余 11 ÷ 2 0 余 1这是最高位从下往上读余数1101这就是 13 的二进制。你看最后一个算出来的余数反而是最前面的数字。如果我们按计算顺序把余数依次写出来1、0、1、1那是反的。栈就是为了解决这个反而存在的。1.2 为什么栈结构和进制转换完美匹配栈的核心理念只有八个字后进先出先进后出。你往栈里压入元素取出来的时候一定是反过来的。这个特性和短除法的需求完全对上入栈顺序低位 → 高位也就是计算产生的顺序出栈顺序高位 → 低位也就是书写展示的顺序中间的转换过程你完全不用管栈内部帮你把顺序倒好了。这也解释了为什么几乎每本数据结构教材都把进制转换放在栈的应用章节——不是偶然是这个例子太能体现栈的抽象价值了。从时间复杂度的角度也能看出这个思路的优势无论是入栈还是出栈单个操作的时间复杂度都是 O(1)整个进制转换过程的时间复杂度就是 O(logₙN)n 是目标进制N 是待转换的十进制数空间复杂度同样是 O(logₙN)用于存储余数。这个效率已经是最优的了——因为你至少要产生这么多位数字才能表示结果。1.3 顺序栈与链栈的选择逻辑明确了用栈之后下一个问题就是用哪种栈两种方案各有千秋不存在谁绝对优于谁只看你的使用场景顺序栈底层是连续数组内存紧凑CPU 缓存友好访问速度快。缺点是栈大小固定除非你自己写动态扩容一旦栈满就寸步难行。适合你已经能预估数据规模、或者栈的最大容量可控的场景。链栈底层是链表结点每个结点单独分配内存理论上只受堆内存限制几乎不会栈满。缺点是每个结点有额外的指针开销且频繁 malloc 会带来性能损耗。适合数据规模不确定、或者对内存利用要求高的场景。我在这次实现里选择两种都写正是因为这是一个绝佳的对比学习机会。你可以在同一份源码里看到同一个算法逻辑如何用两种底层存储结构分别落地。而在实际面试或机试中你至少需要熟练掌握一种同时能说清楚另一种的差异。2. 顺序栈实现固定数组 栈顶指针的完整方案2.1 顺序栈的核心结构定义顺序栈的本质是数组 栈顶指针。我见过不少初学者把栈顶指针初始化为 0 或者 1后面判断栈空栈满很容易混乱。这里我采用的是最主流的约定栈顶指针初始化为 -1指向当前栈顶元素的位置。这个约定下栈空就是 top -1栈满就是 top MAX_SIZE - 1。#include stdio.h #include stdlib.h #define MAX_SIZE 100 // 假设最大容量为100 typedef struct { int data[MAX_SIZE]; int top; // 栈顶指针初始为 -1 } SeqStack; // 初始化栈 void initStack(SeqStack *S) { S-top -1; } // 判断栈空 int isEmpty(SeqStack *S) { return S-top -1; } // 判断栈满 int isFull(SeqStack *S) { return S-top MAX_SIZE - 1; } // 入栈 int push(SeqStack *S, int x) { if (isFull(S)) { printf(错误栈满无法入栈 %d\n, x); return 0; } S-data[S-top] x; return 1; } // 出栈返回栈顶元素 int pop(SeqStack *S, int *result) { if (isEmpty(S)) { printf(错误栈空无法出栈\n); return 0; } *result S-data[S-top--]; return 1; }2.2 进制转换核心函数核心转换函数的设计思路是外部传入一个十进制数 N 和目标进制 base函数内部用除基取余法依次把余数压栈最后再依次弹栈并输出。这里有一个细节极其容易出错余数可能是 10 到 15但 10 以上的数字在进制表示里应该是字母 A 到 F。所以输出的时候不能只打印数字要做一层10 以上转字母的映射。// 将十进制数 N 转换为 base 进制并输出base 2, 8, 16 void convert(SeqStack *S, int N, int base) { if (N 0) { printf(0\n); return; } // 第一步除基取余余数入栈 while (N 0) { int remainder N % base; push(S, remainder); N N / base; } // 第二步依次出栈并输出 int digit; while (!isEmpty(S)) { pop(S, digit); if (digit 10) { printf(%d, digit); } else { printf(%c, A (digit - 10)); } } printf(\n); }注意这里先把 N 0 的情况单独处理了。为什么因为 0 的二进制/八进制/十六进制仍然是 0如果走循环第一次循环 N % base 0压栈然后 N 0循环结束弹栈输出 0其实也能得到正确答案。但问题是——如果 N 是负数呢这版代码会陷入死循环。所以先把 0 单独处理是一个防御性编程的习惯。2.3 完整测试代码与运行结果主函数里我做了一个比较全面的测试覆盖 0、正小数、较大整数同时验证 2、8、16 三种进制。int main() { SeqStack S; initStack(S); printf( 顺序栈进制转换测试 \n); printf(十进制 0 → 二进制); convert(S, 0, 2); printf(十进制 13 → 二进制); convert(S, 13, 2); printf(十进制 255 → 八进制); convert(S, 255, 8); printf(十进制 255 → 十六进制); convert(S, 255, 16); printf(十进制 2024 → 十六进制); convert(S, 2024, 16); printf(十进制 12345 → 二进制); convert(S, 12345, 2); return 0; }输出结果 顺序栈进制转换测试 十进制 0 → 二进制0 十进制 13 → 二进制1101 十进制 255 → 八进制377 十进制 255 → 十六进制FF 十进制 2024 → 十六进制7E8 十进制 12345 → 二进制11000000111001我手动验证过这些结果都没问题。其中 2024 转十六进制是 7E8这里 7E8 的 E 就是余数 14 对应的字母。如果你看到的输出是7148那说明你的代码漏了字母映射这一步或者映射公式写错了。2.4 顺序栈的踩坑点栈满与内存浪费顺序栈最大的隐患是栈满。MAX_SIZE 定义成 100理论上最多存 100 个余数2 进制的 100 位对应的十进制数大约是 2¹⁰⁰ ≈ 1.27 × 10³⁰常规测试根本碰不到这个上限。但问题在于这是一个固定容量你无法保证所有场景都安全。实际开发中我更推荐给顺序栈加上动态扩容能力。具体做法是入栈时如果发现栈满就用 realloc 把数组容量扩大一倍并拷贝原有数据。这样既保留了顺序栈的连续内存优势又避免了容量瓶颈。不过在本例这种教学场景下固定容量就够了——重点是理解栈的逻辑而不是过早开始性能优化。3. 链栈实现不限定容量结点即栈元素3.1 链栈的结构与指针操作细则链栈的底层是单链表但和普通链表的区别在于你只在头部插入、删除结点头结点本身就可以充当栈顶。也就是说链栈的栈顶就是链表的第一个结点。这个设计让入栈和出栈操作都不需要遍历链表时间复杂度都是 O(1)。链栈结点定义typedef struct Node { int data; // 存储余数 struct Node *next; // 指向下一个结点 } LinkNode; typedef struct { LinkNode *top; // 栈顶指针 } LinkStack;我特意把栈和结点分成了两个结构体而不是直接用 LinkNode* 当栈。这样做的原因是如果你直接用 LinkNode* 表示栈初始化的时候只需要置为 NULL但出栈、判断栈空等操作都要双重指针LinkNode**才能改到调用者的指针变量。封装成 LinkStack 结构体之后操作函数只需要传 LinkStack*语义更清晰也不容易写错。3.2 链栈的核心操作实现链栈操作的几个关键点入栈就是在链表头部插入新结点新结点的 next 指向原栈顶出栈就是保存原栈顶的值让栈顶指针向后移一位然后释放原栈顶结点释放结点分配的内存是链栈和顺序栈最大的区别——顺序栈不需要手动释放链栈如果不 free程序跑久了必然内存泄漏#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } LinkNode; typedef struct { LinkNode *top; } LinkStack; // 初始化栈 void initStack(LinkStack *S) { S-top NULL; } // 判断栈空 int isEmpty(LinkStack *S) { return S-top NULL; } // 入栈头插法 void push(LinkStack *S, int x) { LinkNode *node (LinkNode *)malloc(sizeof(LinkNode)); if (node NULL) { printf(错误内存分配失败\n); exit(1); } node-data x; node-next S-top; S-top node; } // 出栈 int pop(LinkStack *S, int *result) { if (isEmpty(S)) { printf(错误栈空无法出栈\n); return 0; } LinkNode *temp S-top; *result temp-data; S-top temp-next; free(temp); return 1; }3.3 链栈的进制转换实现进制转换的核心逻辑和顺序栈完全一样区别只是在栈的操作方式上。这也正好验证了抽象的好处——上层的算法逻辑不依赖底层实现你只需要保证所有栈都提供 push、pop、isEmpty 这几个接口。// 将十进制数 N 转换为 base 进制并输出 void convert(LinkStack *S, int N, int base) { if (N 0) { printf(0\n); return; } while (N 0) { push(S, N % base); N N / base; } int digit; while (!isEmpty(S)) { pop(S, digit); if (digit 10) { printf(%d, digit); } else { printf(%c, A (digit - 10)); } } printf(\n); }这个函数和顺序栈版本的 convert 几乎一模一样。读者可以做一个实验你把顺序栈版本的 convert 函数体复制过来只把传参类型从 SeqStack* 改成 LinkStack*其他地方一行都不用改就能跑。这就是栈的抽象带来的威力。3.4 链栈的内存管理最容易忽略的细节链栈最容易栽跟头的地方不是逻辑而是内存。我在第一次写链栈的时候就漏了 free结果程序跑了几百次转换之后内存占用肉眼可见地飙升。排查了半天才发现是出栈操作没释放结点。这里有一个经验性的教训凡是用了 malloc 的地方程序里必须有对应的 free。写链栈代码时入栈有一个 malloc出栈就必须有一个 free成对出现。如果发现出栈函数里没有 free基本可以断定会有内存泄漏。另外如果一个程序使用完整个链栈之后还想复用应该写一个 destroyStack 函数把栈里剩余的所有结点逐一释放避免残留的内存占用// 销毁整个栈 void destroyStack(LinkStack *S) { while (S-top ! NULL) { LinkNode *temp S-top; S-top temp-next; free(temp); } }4. 顺序栈与链栈的选型对比同一道题两种答案4.1 关键维度横向对比我在开发这个源码时把两种实现摆在桌面上做了一次系统对比。下面是整理的维度表格可以帮你在不同的产品场景里快速做选型判断对比维度顺序栈链栈底层结构连续数组链表结点内存分配方式一次性分配固定大小每入栈一个元素动态分配栈满情况可能栈满需扩容内存足够时不栈满空间利用率固定容量可能浪费按需分配利用率高节点内存开销无额外指针内存紧凑每个结点多一个 next 指针入栈/出栈时间复杂度O(1)O(1)内存连续性连续缓存友好离散缓存不友好是否需手动释放不需要出栈或销毁时必须 free适用场景数据规模可控、追求性能数据不可控、追求灵活4.2 实际项目里我选哪个如果是在嵌入式设备或者性能敏感的服务端代码里做进制转换我优先选顺序栈。理由很直接它的内存是连续的遍历和随机访问都快而且不需要频繁调用 malloc/free避免了内存碎片问题。数据规模这种东西你在写代码的时候基本能估算出来——一个 int 最大也就 2³²转成 2 进制最多 32 位用一个 64 容量的数组绰绰有余。如果是写一个通用工具库或者你要转换的数字范围不确定比如可能处理大整数那链栈更合适。因为你不需要预设容量只要堆内存够它就能一直入栈。代价是每个结点要多花 4 字节指针大小存储 next 指针以及 malloc 调用本身的耗时。我的建议是学生阶段两种都要会写但实际工作里如果没有特殊需求直接顺序栈就完了——简单、高效、不容易出内存问题。链栈的价值更多在于让你理解栈这个抽象概念可以不依赖数组存在加深对数据结构的认识。4.3 这个设计还能怎么扩展这套栈进制转换的代码框架扩展空间其实不小。我顺便列几个可以直接在这个基础上改的方向当你需要应付更复杂的场景时会很有用支持负数转换先取绝对值做转换最后在输出前手动加负号支持任意进制比如 3、7、12 进制只需要修改 base 参数但注意 10 以上的数字都要走字母映射支持大数转换把 int 换成 long long或者直接用字符串模拟除法支持浮点数转换整数部分走这套逻辑小数部分用乘基取整法单独处理5. 常见问题与排查技巧实录5.1 从调试中总结的 7 个高频 Bug写这套源码的过程中我遇到了不少问题。这里挑出最有代表性的 7 个按出现频率从高到低排问题现象根因分析解决方法输出的余数是倒序的没有用栈存余数直接用数组存后顺序输出先压栈再弹栈利用后进先出自动倒序十六进制输出出现 10、11、14 这样的数字漏了字母映射判断余数 digit 10 时输出A (digit - 10)栈空时调用 pop 导致程序崩溃没有判断 isEmpty 就出栈pop 函数入口先判空空栈返回错误码顺序栈 MAX_SIZE 设得不够大数转换时溢出栈容量不足预估值设为 64int 二进制最多 32 位或实现动态扩容链栈程序运行多次后内存一直涨出栈时没有 free 结点检查 pop 函数释放 temp 结点输入 0 时输出为空没做特殊处理循环直接跳过转换函数开头判断 N 0 直接输出 0传入负数导致死循环负数对正数取模结果还是负数N 永远无法归零转换函数开头取绝对值或直接拒绝负数输入5.2 最隐蔽的一个坑字母映射的范围十六进制的字母映射我自己就踩过一次。当时只觉得A (digit - 10)这行代码理所当然却没想过如果 base 超过 16digit 可能直接是 16、17那输出就会变成 G、H完全乱套。所以在通用版本里对 base 必须做校验。至少在进入转换函数之前加一个判断// 只支持 2-16 进制 if (base 2 || base 16) { printf(错误不支持的进制 %d\n, base); return; }这个限制不是多余的——它保证了字母映射只在 0-15 的范围内生效。如果你要支持 16 进制以上的输出比如 36 进制那要把字母映射扩展到 Z不过用 ASCII 码连续性来映射的方式依然成立。5.3 一个容易被面试官追问的问题为什么余数要倒序输出面试官如果在代码题之后追一句为什么用栈做进制转换很多人会突然卡壳。我的建议是用一句话回答因为短除法是按从低位到高位的顺序产生余数的而我们输出数字的顺序是从高位到低位栈的后进先出特性恰好把这个逆序过程天然地完成了。如果再深一层你可以补充其实不用栈也可以实现用一个数组存余数再倒序遍历输出效果是一样的。但栈把逆序输出这件事抽象成了结构化的操作代码更简洁、逻辑更清晰也更符合我们对这类问题的思考方式。这也是数据结构的意义——它不仅是一种存储方式更是一种思维模式。6. 一些实战心得与后续建议这套代码我前后调试了两天写完那一刻最大的感受是数据结构这东西光看理论不出真知亲手实现一遍才能把抽象概念长成自己脑子里的肌肉记忆。顺序栈和链栈各有各的脾气顺序栈要时刻盯着栈顶指针别踩到边界链栈则要小心每一个 malloc 对应的 free。但如果只是跟着教材抄一遍收获很有限我建议你改两个地方再敲一遍一是把固定容量的顺序栈改成动态扩容版本用 realloc 实现内存翻倍体会一下扩容这个操作到底做了什么以及为什么扩容时要注意数据拷贝。二是把进制从 2、8、16 扩展到任意进制比如 7 进制、12 进制强迫自己面对字母映射的正确性、边界条件的判断这套处理能力对你的编程功底提升非常明显。另外如果你想把这个小工具推向真实场景我推荐一个方向把输出结果从 printf 改成字符串缓冲区拼接或者直接返回一个 char* 字符串。这样你的 convert 函数就能嵌入到任何工程里而不只是控制台玩具。栈的核心操作 push、pop 不依赖任何库代码搬到哪里都能跑。这套源码我放在本地一个叫 stack-conversion 的目录里顺序栈和链栈各一个文件互不依赖。你拿到代码后可以先跑一遍测试用例再故意引入几个 bug 观察现象比如去掉 isEmpty 判断、把字母映射删掉看程序会怎么崩溃——这种主动制造故障的练习方式比闷头写十遍都管用。本文还有配套的精品资源点击获取