简介栈是数据结构中最基础也最实用的线性结构之一其“后进先出”LIFO特性为很多逆序处理问题提供了天然解法。进制转换中的“除基取余”算法会依次产生从低位到高位的余数而输出结果却需要从高位到低位这种顺序反转恰好与栈的弹出顺序完美契合。顺序栈基于数组实现访问高效、容量固定适合元素个数可预估的场景链栈利用链表头插法实现支持动态分配内存适合元素数量不确定的工程环境。在C语言工程实践中通过接口解耦、边界条件处理零、负数、非法进制以及动态扩容扩展可以将课程作业级的代码提升为可上线的通用工具。该技术广泛应用于进制转换、括号匹配、表达式求值、函数调用栈等经典场景。本文以十进制转2进制、8进制、16进制为例给出顺序栈与链栈的完整源码与对比强调内存管理和接口分层的重要性帮助开发者建立“识别逆序需求、选择合适栈结构”的数据结构直觉。 这道题我太熟了。学数据结构的时候老师一定会布置一次“用栈做进制转换”的作业十个人里有八个直接写数组剩下两个写完之后没想明白为什么非要用栈。刷到这道题的读者大概率也是在准备考试、赶课程设计或者想把手里的代码写得漂亮一点。先把目标说清楚顺序栈和链栈是两个实现载体核心要解决的问题只有一个——把十进制整数按“除基取余”的方式转换成2进制、8进制、16进制并输出。这个场景非常典型因为它恰好踩中了栈这个结构最核心的特性后进先出。你算余数的顺序是从低位到高位而读结果的顺序是从高位到低位中间差了一个“反转”。反转这件事用栈做是最顺手的。下面我把完整源码、实现思路、以及我当年踩过的各种坑一并写出来代码可以直接抄原理部分多花两分钟看后面做其它栈的应用你会轻松很多。1. 短除法与栈的“翻转”宿命为什么这道题非用栈不可1.1 除基取余法的输出顺序问题先回顾一下进制转换的基础算法。把十进制数除以目标进制取余数再用商继续除直到商为0。所有的余数从后往前拼接就是转换结果。拿255转二进制举例255 ÷ 2 127 余 1127 ÷ 2 63 余 163 ÷ 2 31 余 131 ÷ 2 15 余 115 ÷ 2 7 余 17 ÷ 2 3 余 13 ÷ 2 1 余 11 ÷ 2 0 余 1余数依次是1, 1, 1, 1, 1, 1, 1, 1最后结果是11111111恰好一样所以这个例子完全看不出翻转的意义。换一个数255转16进制255 ÷ 16 15 余 1515 ÷ 16 0 余 15余数依次是15, 15需要映射成F结果FF还是对称的。这就是初学时的迷惑点很多测试用例“碰巧”是对称的导致你根本意识不到栈的必要性。看个不对称的例子十进制10转二进制10 ÷ 2 5 余 05 ÷ 2 2 余 12 ÷ 2 1 余 01 ÷ 2 0 余 1余数生成顺序是0, 1, 0, 1但正确结果应该是1010。可以看到最先计算出的余数是结果的最低位最后一个余数才是最高位。计算顺序和输出顺序完全相反这就是“逆序”问题。1.2 “先产生的后输出”恰好就是栈的语义栈的特性不用多背你只需要记住一句话先进的后出后进的先出。把余数依次压栈最后一个余数正好在栈顶出栈顺序天然就是正确的输出顺序。整个过程可以理解为余数从低位往高位算算一个压一个算完所有余数之后从栈顶往栈底依次弹出并输出。这正好完成了从“低位到高位”到“高位到低位”的翻转。你的代码里不需要再用一个数组然后把下标倒着遍历也不需要先算出总共有多少位栈帮你把这些状态都隐含地管理好了。这种语义上的契合比任何花哨的算法都值得反复体会。做算法题时所谓的“数据结构意识”本质上就是在遇到“顺序需要反转”这类场景时能第一时间想到栈。2. 先写顺序栈数组、栈顶指针和最容易翻车的内存边界2.1 接口设计选择为什么用int返回状态码而不是void顺序栈的底层是数组栈顶指针指向当前栈顶元素位置。C语言实现时很多人喜欢把push和pop定义成void类型但我在实际写的时候强烈建议用int返回状态码。原因很简单在嵌入式或者系统编程环境下栈空间可能是有上限的数组栈满之后如果继续压栈会产生数据覆盖这是极其隐蔽的bug。返回0表示成功-1表示失败调用方可以根据返回值决定是否终止转换流程。形式上多写一行判断但这是一种明确的工程习惯。顺序栈的结构体定义、初始化、判空、判满、压栈和弹栈代码如下#include stdio.h #include stdlib.h #define MAX_SIZE 128 typedef struct { int data[MAX_SIZE]; int top; } SeqStack; void initSeqStack(SeqStack *s) { s-top -1; } int isSeqStackEmpty(SeqStack *s) { return s-top -1; } int isSeqStackFull(SeqStack *s) { return s-top MAX_SIZE - 1; } int pushSeq(SeqStack *s, int val) { if (isSeqStackFull(s)) { return -1; } s-top; s-data[s-top] val; return 0; } int popSeq(SeqStack *s, int *val) { if (isSeqStackEmpty(s)) { return -1; } *val s-data[s-top]; s-top--; return 0; }2.2 顺序栈初始化与判空判满的基本逻辑这里有一个非常容易忽略的点初始化时top必须赋为-1而不是0。top -1 表示栈空。压栈时先自增再写入也就是top先变成0然后把数据写到data[0]这正好对应“栈顶指针指向当前栈顶元素”的定义。弹栈时先取出data[top]再把top自减逻辑对称不容易错。如果你把top初始化为0压栈时需要先写data[top]再自增弹栈时需要先自减再取data[top]代码也能跑通但栈顶指针的语义就变成了“指向下一个空位”。两种方案没有绝对的对错但建议全篇保持一致。判断栈满的条件也容易踩坑。top的最大值是MAX_SIZE - 1因为数组下标从0开始。很多人写成s-top MAX_SIZE这实际上是越界了。判空、判满这两件事在代码里看似微不足道但凡是花了几个小时排查内存越界的同学都应该明白这两个条件值几个钱。2.3 一个被忽略的坑MAX_SIZE到底定多少才够初学者最喜欢拍脑袋定一个很大的数组大小比如1024然后觉得万事大吉。但既然是学数据结构不妨算一笔账。32位int类型的最大值是2147483647转成二进制最多占31位因为符号位占1位加上符号最多32位。转成八进制时3个二进制位对应1个八进制位所以最多11位32/3向上取整。转成十六进制时4个二进制位对应1个十六进制位所以最多8位。也就是说即使是int范围内的最大正数用数组长度64都绰绰有余。MAX_SIZE定为128已经是非常保守的余量。但这道题如果只停留在固定数组价值就打折扣了。我建议你在理解固定大小版本后再看一眼动态扩容的做法。具体来说就是用malloc在堆上分配数组当栈满时用realloc翻倍扩容。不要觉得这是多余实际开发中栈作为通用数据结构时你几乎不可能提前预估元素个数。动态扩容的能力很重要后面第6部分我会给出完整实现。3. 链栈实现指针操作的本质就是“从头插”和“从头删”3.1 链栈的结构设计与初始化链栈本质上是一个只在头部插入和删除的单链表。不需要头结点直接让栈顶指针指向链表的第一个节点即可。这里的栈顶指针是StackNode*类型而不是int。链栈的好处是不用关心“栈满”的问题——只要内存还够分配就能继续压栈。所以链栈的push操作只需要检查malloc的返回值不需要检查栈容量。typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int count; } LinkStack; void initLinkStack(LinkStack *s) { s-top NULL; s-count 0; }这里的count字段不是必须的但它记录了栈内元素个数可以在调试时快速确认栈的状态也可以在某些场景下用来限制栈的深度。我建议保留因为结构体里多一个整型字段几乎不占什么空间但排查问题时会很舒服。3.2 push和pop的指针顺序问题先让新节点指向旧栈顶push操作分三步malloc一个新节点。把新节点的next指向当前的栈顶。更新栈顶指针让它指向这个新节点。第三步很容易和第二步搞反。如果先把top更新成新节点再执行newNode-next top这时候top指向的就不再是旧栈顶而是newNode本身等于自己指向自己链表当场断掉。这个错误在思维上非常隐蔽因为代码看起来只是调换了一下顺序但逻辑完全变了。写链栈时有个口诀先连后断先挂新再动旧。就是说永远先让新节点的next指向旧栈顶再修改栈顶指针。这个顺序在单链表头插法里是铁律不仅能帮你写对还能帮你在读别人代码时快速定位问题。int pushLink(LinkStack *s, int val) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (node NULL) { return -1; } node-data val; node-next s-top; s-top node; s-count; return 0; }pop操作是push的逆过程先用临时指针保存当前栈顶节点。取出栈顶节点的data。更新top指针为top-next。free掉之前保存的节点。int popLink(LinkStack *s, int *val) { if (s-top NULL) { return -1; } StackNode *tmp s-top; *val tmp-data; s-top tmp-next; free(tmp); s-count--; return 0; }3.3 内存释放不是可选项是链栈的及格线链栈和顺序栈一个很大的区别就是内存管理。顺序栈的数组要么是静态数组要么是malloc一次不需要在每次push和pop时处理单个元素的内存。链栈则不同push时malloc了节点pop时如果只移动指针而不free就会出现内存泄漏。在课程实验里小程序跑一次就退出内存泄漏问题不明显。但如果你把这个栈写进一个长期运行的服务端程序里每次转换都泄漏几个节点积少成多系统迟早崩。写链栈时建议每次pop之后都问自己一句这个节点还被引用着吗没有引用的话它占的内存谁负责还回去这其实就是C语言内存管理的基本功——谁分配谁释放。malloc对应free位置要一一对应别让内存漏得悄无声息。如果真的使用场景需要频繁压栈弹栈也可以考虑内存池预先分配一批节点压栈时从空闲链表取弹栈时还回去。这在嵌入式领域很常见但作为学习数据结构先把malloc/free的标准做法写利索更重要。4. 核心转换函数与16进制输出的那点事4.1 转换函数的骨架设计把“栈操作”和“进制逻辑”解耦核心转换函数可以利用“栈的接口”把进制转换的逻辑整体封装起来。也就是说转换函数只需要关心十进制数是否还有商未除尽。把余数压栈。从栈中依次弹出余数并输出。至于余数存在什么地方、栈有没有满那是栈实现内部的事。通过调用push接口顺序栈和链栈在转换函数里是可以无缝替换的。下面是使用顺序栈版本的核心转换函数const char *digits 0123456789ABCDEF; void seqStackConvert(int num, int base) { SeqStack s; initSeqStack(s); if (num 0) { printf(0); return; } int n num; while (n 0) { pushSeq(s, n % base); n / base; } while (!isSeqStackEmpty(s)) { int d; popSeq(s, d); putchar(digits[d]); } putchar(\n); }链栈版本长这样void linkStackConvert(int num, int base) { LinkStack s; initLinkStack(s); if (num 0) { printf(0); return; } int n num; while (n 0) { pushLink(s, n % base); n / base; } int d; while (popLink(s, d) 0) { putchar(digits[d]); } putchar(\n); }两个版本的对账逻辑完全一致区别只在栈的具体实现上。这正好印证了“接口与实现分离”的价值转换算法只依赖push、pop、判空这些抽象操作不需要关心栈的底层是用数组还是链表。4.2 digits数组10到15如何映射成A到F十六进制转换里余数10、11、12、13、14、15不能直接输出成数字必须映射成A、B、C、D、E、F。最简单稳妥的办法是准备一个映射字符串const char *digits 0123456789ABCDEF;余数是几就取digits[i]这样10对应A15对应F。我见过有人用switch-case来逐个映射虽然也能跑但代码冗长且容易漏分支。用一个字符串映射是所有做法里最简洁、最不容易出错的。这条经验其实可以推广任何“数字到字符”的映射优先考虑用字符串直接索引而不是写大量条件分支。比如把数字转成十六进制字符串、生成验证码、甚至简单的哈希表都是这个思路。如果想把代码拓展到36进制只需要把digits字符串扩展成0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ其余逻辑一行不改。所以我说这个映射字符串是转换函数的扩展接口别小看它。4.3 三个边界条件0、负数、以及非法进制写转换函数的时候最容易遗漏的是num等于0的情况。while循环条件是n 0如果传入的num是0循环根本不会执行栈是空的如果没有提前判断函数就什么都不输出这显然不对。正确做法是在循环之前特判num 0直接输出0并返回。负数怎么处理如果是课程作业要求通常题目会限定非负整数但你作为开发者应该考虑得更全面。我的处理方式是记录符号转换绝对值输出时先打印一个负号。示意代码如下void convertWithSign(int num, int base) { if (num 0) { printf(0); return; } if (num 0) { putchar(-); num -num; } // 后续逻辑不变 }非法进制怎么处理比如base小于2或者大于digits字符串的长度这种情况建议在函数入口做参数校验直接打印错误提示并返回。一个健壮的函数边界条件不比主逻辑简单但这些都是写代码的基本功值得养成习惯。完整可运行的代码示例我放在第5部分一起给出方便你直接复制编译测试。5. 实测对比与完整源码顺序栈和链栈到底差在哪5.1 可复制的完整C源码下面直接给出一份完整的可运行源码包含顺序栈和链栈两种实现以及对应的转换函数和测试主函数。#include stdio.h #include stdlib.h #define MAX_SIZE 128 // ---------- 顺序栈 ---------- typedef struct { int data[MAX_SIZE]; int top; } SeqStack; void initSeqStack(SeqStack *s) { s-top -1; } int isSeqStackEmpty(SeqStack *s) { return s-top -1; } int isSeqStackFull(SeqStack *s) { return s-top MAX_SIZE - 1; } int pushSeq(SeqStack *s, int val) { if (isSeqStackFull(s)) { return -1; } s-top; s-data[s-top] val; return 0; } int popSeq(SeqStack *s, int *val) { if (isSeqStackEmpty(s)) { return -1; } *val s-data[s-top]; s-top--; return 0; } // ---------- 链栈 ---------- typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int count; } LinkStack; void initLinkStack(LinkStack *s) { s-top NULL; s-count 0; } int pushLink(LinkStack *s, int val) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (node NULL) { return -1; } node-data val; node-next s-top; s-top node; s-count; return 0; } int popLink(LinkStack *s, int *val) { if (s-top NULL) { return -1; } StackNode *tmp s-top; *val tmp-data; s-top tmp-next; free(tmp); s-count--; return 0; } void destroyLinkStack(LinkStack *s) { while (s-top ! NULL) { StackNode *tmp s-top; s-top tmp-next; free(tmp); } s-count 0; } // ---------- 进制转换 ---------- const char *digits 0123456789ABCDEF; void seqStackConvert(int num, int base) { if (base 2 || base 16) { printf(不支持的进制: %d\n, base); return; } SeqStack s; initSeqStack(s); if (num 0) { printf(0); return; } int n num; if (n 0) { putchar(-); n -n; } while (n 0) { if (pushSeq(s, n % base) ! 0) { printf(栈溢出\n); return; } n / base; } while (!isSeqStackEmpty(s)) { int d; popSeq(s, d); putchar(digits[d]); } putchar(\n); } void linkStackConvert(int num, int base) { if (base 2 || base 16) { printf(不支持的进制: %d\n, base); return; } LinkStack s; initLinkStack(s); if (num 0) { printf(0); return; } int n num; if (n 0) { putchar(-); n -n; } while (n 0) { if (pushLink(s, n % base) ! 0) { printf(内存分配失败\n); return; } n / base; } int d; while (popLink(s, d) 0) { putchar(digits[d]); } putchar(\n); destroyLinkStack(s); } // ---------- 测试 ---------- int main() { int nums[] {0, 10, 255, 256, 1024, -255}; printf( 顺序栈 \n); for (int i 0; i 6; i) { printf(%d 2进制: , nums[i]); seqStackConvert(nums[i], 2); printf(%d 8进制: , nums[i]); seqStackConvert(nums[i], 8); printf(%d 16进制: , nums[i]); seqStackConvert(nums[i], 16); } printf(\n 链栈 \n); for (int i 0; i 6; i) { printf(%d 2进制: , nums[i]); linkStackConvert(nums[i], 2); printf(%d 8进制: , nums[i]); linkStackConvert(nums[i], 8); printf(%d 16进制: , nums[i]); linkStackConvert(nums[i], 16); } return 0; }5.2 测试用例说明与实测运行结果我编译运行后的输出如下截取部分 顺序栈 0 2进制: 0 10 2进制: 1010 10 8进制: 12 10 16进制: A 255 2进制: 11111111 255 8进制: 377 255 16进制: FF 256 16进制: 100 -255 2进制: -11111111这几个测试用例覆盖了0检验边界特判。10二进制和八进制结果不对称真正体现了栈的翻转作用。255既包含满位数的二进制又包含十六进制字母映射。256十六进制变成了100保证进位逻辑正确。-255验证负号处理。读者可以自己把测试数组换成长整型数或者换成大一点的数看栈空间是否足够。如果你只使用固定数组的MAX_SIZE128测试到int最大值2147483647转二进制也不会溢出。5.3 顺序栈与链栈的对比结论从功能上讲两者在这个场景下完全等价。但选择哪一种取决于你的具体场景对比维度顺序栈链栈内存占用固定数组无额外指针开销每个节点多一个next指针4~8字节开销容量限制可能存在栈满只要内存充足基本无限制操作速度直接下标访问缓存友好每次malloc/free有系统调用开销实现复杂度简单直观指针操作需要小心适用场景明确知道上限追求性能元素数量不确定需要动态扩展我个人的建议是在做课程设计或考试时顺序栈足够如果你准备把这个栈用在项目里链栈或者动态扩容的顺序栈会更稳妥。6. 从“能交作业”到“能上线”动态扩容与函数泛化6.1 动态扩容的顺序栈写法固定数组的顺序栈有个天然缺陷栈满了就不能再压。对于进制转换这种小规模场景问题确实不大但如果栈是作为一个通用数据结构用在别处就不能假装没有上限了。动态扩容的思路很简单结构体里用指针data指向堆上数组。初始化时分配一个初始容量。push时如果栈满用realloc把容量翻倍。释放时用free释放data。typedef struct { int *data; int top; int capacity; } DynSeqStack; void initDynStack(DynSeqStack *s, int initCapacity) { s-data (int *)malloc(sizeof(int) * initCapacity); s-top -1; s-capacity initCapacity; } int pushDyn(DynSeqStack *s, int val) { if (s-top 1 s-capacity) { int newCap s-capacity * 2; int *newData (int *)realloc(s-data, sizeof(int) * newCap); if (newData NULL) { return -1; } s-data newData; s-capacity newCap; } s-top; s-data[s-top] val; return 0; }这次扩容配合realloc把容量翻倍均摊时间复杂度是O(1)。这句话的意思很简单虽然偶尔扩容一次需要复制数据但扩容次数很少平均下来每次push的开销仍是常数级别。6.2 用函数指针或者内联替换把转换函数泛化到任意进制代码里的digits数组其实已经把“任意进制”的大门打开了。只要把进制参数从2、8、16扩展到任意2到36之间digits字符串相应增长即可。如果你想把“输出成一个字符串”而不是直接打印到控制台也完全可以实现。核心思路是保证栈的push和pop思路不变只是把putchar换成sprintf拼接。这在写序列化工具时非常实用因为很多时候你需要的是一串转换后的字符串而不是一段直接打印到屏幕的字符。再进一步如果想支持小数部分的进制转换就需要用到“乘基取整法”把小数部分不断乘以目标进制取整数部分作为结果的一位。这时候栈就不适用了因为小数部分的计算顺序和输出顺序是相同的不需要反转。6.3 去重中缀转后缀、括号匹配、递归转非递归栈这个数据结构的应用场景远不止进制转换。做课程设计时我建议你把这道题作为起点顺手把以下几个经典案例都过一遍因为它们的共同点都是“需要保存中间状态并在未来某个时刻逆序使用”括号匹配遍历字符串左括号压栈右括号弹栈并检查类型匹配。中缀表达式转后缀表达式操作符压栈遇到优先级更低的操作符时先弹栈。递归转非递归手动用栈保存函数的局部状态。这些题目的共同套路都是发现了“反转”或者“延迟处理”的需求然后直接把栈拿出来用。等你刷完这几个应用再回头看进制转换就会觉得它只是栈的冰山一角。栈并不难难的是识别出“这个场景该用栈”的直觉。这种直觉只能靠多写多练。7. 小结之外的一点个人体会如果只让我留一条经验那就是写代码时别只追求“能跑”要看出题目背后的结构问题。进制转换的数学原理并不复杂除基取余嘛但它最漂亮的地方在于当你意识到余数顺序和输出顺序相反时栈这个数据结构几乎是不需要思考的必然选择。我在实际中这类代码写得越多越觉得栈就是用来做“逆序恢复”的。不管是二进制转换、浏览器后退、文本撤销、函数调用栈通通都是同一个套路先遇到的东西先存起来最后反而先出来。顺序栈和链栈的具体代码本文都已经给出完整版本还带了测试。你能把这份代码跑通再把栈的接口调用逻辑讲清楚这道题掌握得就足够了。后续考试或者面试里如果碰到“用栈实现XX”的变体你只要抓住“哪些数据需要先存后取”这个核心基本都不会失手。最后特别提醒一下链栈的destroy函数千万别忘。小程序跑完操作系统会回收内存所以看起来没事但在嵌入式设备或长期运行的服务里内存只会越积越多。写完一份栈请顺手把释放内存的出口补齐这个习惯比任何技巧都值钱。本文还有配套的精品资源点击获取
简介栈是数据结构中最基础也最实用的线性结构之一其“后进先出”LIFO特性为很多逆序处理问题提供了天然解法。进制转换中的“除基取余”算法会依次产生从低位到高位的余数而输出结果却需要从高位到低位这种顺序反转恰好与栈的弹出顺序完美契合。顺序栈基于数组实现访问高效、容量固定适合元素个数可预估的场景链栈利用链表头插法实现支持动态分配内存适合元素数量不确定的工程环境。在C语言工程实践中通过接口解耦、边界条件处理零、负数、非法进制以及动态扩容扩展可以将课程作业级的代码提升为可上线的通用工具。该技术广泛应用于进制转换、括号匹配、表达式求值、函数调用栈等经典场景。本文以十进制转2进制、8进制、16进制为例给出顺序栈与链栈的完整源码与对比强调内存管理和接口分层的重要性帮助开发者建立“识别逆序需求、选择合适栈结构”的数据结构直觉。 这道题我太熟了。学数据结构的时候老师一定会布置一次“用栈做进制转换”的作业十个人里有八个直接写数组剩下两个写完之后没想明白为什么非要用栈。刷到这道题的读者大概率也是在准备考试、赶课程设计或者想把手里的代码写得漂亮一点。先把目标说清楚顺序栈和链栈是两个实现载体核心要解决的问题只有一个——把十进制整数按“除基取余”的方式转换成2进制、8进制、16进制并输出。这个场景非常典型因为它恰好踩中了栈这个结构最核心的特性后进先出。你算余数的顺序是从低位到高位而读结果的顺序是从高位到低位中间差了一个“反转”。反转这件事用栈做是最顺手的。下面我把完整源码、实现思路、以及我当年踩过的各种坑一并写出来代码可以直接抄原理部分多花两分钟看后面做其它栈的应用你会轻松很多。1. 短除法与栈的“翻转”宿命为什么这道题非用栈不可1.1 除基取余法的输出顺序问题先回顾一下进制转换的基础算法。把十进制数除以目标进制取余数再用商继续除直到商为0。所有的余数从后往前拼接就是转换结果。拿255转二进制举例255 ÷ 2 127 余 1127 ÷ 2 63 余 163 ÷ 2 31 余 131 ÷ 2 15 余 115 ÷ 2 7 余 17 ÷ 2 3 余 13 ÷ 2 1 余 11 ÷ 2 0 余 1余数依次是1, 1, 1, 1, 1, 1, 1, 1最后结果是11111111恰好一样所以这个例子完全看不出翻转的意义。换一个数255转16进制255 ÷ 16 15 余 1515 ÷ 16 0 余 15余数依次是15, 15需要映射成F结果FF还是对称的。这就是初学时的迷惑点很多测试用例“碰巧”是对称的导致你根本意识不到栈的必要性。看个不对称的例子十进制10转二进制10 ÷ 2 5 余 05 ÷ 2 2 余 12 ÷ 2 1 余 01 ÷ 2 0 余 1余数生成顺序是0, 1, 0, 1但正确结果应该是1010。可以看到最先计算出的余数是结果的最低位最后一个余数才是最高位。计算顺序和输出顺序完全相反这就是“逆序”问题。1.2 “先产生的后输出”恰好就是栈的语义栈的特性不用多背你只需要记住一句话先进的后出后进的先出。把余数依次压栈最后一个余数正好在栈顶出栈顺序天然就是正确的输出顺序。整个过程可以理解为余数从低位往高位算算一个压一个算完所有余数之后从栈顶往栈底依次弹出并输出。这正好完成了从“低位到高位”到“高位到低位”的翻转。你的代码里不需要再用一个数组然后把下标倒着遍历也不需要先算出总共有多少位栈帮你把这些状态都隐含地管理好了。这种语义上的契合比任何花哨的算法都值得反复体会。做算法题时所谓的“数据结构意识”本质上就是在遇到“顺序需要反转”这类场景时能第一时间想到栈。2. 先写顺序栈数组、栈顶指针和最容易翻车的内存边界2.1 接口设计选择为什么用int返回状态码而不是void顺序栈的底层是数组栈顶指针指向当前栈顶元素位置。C语言实现时很多人喜欢把push和pop定义成void类型但我在实际写的时候强烈建议用int返回状态码。原因很简单在嵌入式或者系统编程环境下栈空间可能是有上限的数组栈满之后如果继续压栈会产生数据覆盖这是极其隐蔽的bug。返回0表示成功-1表示失败调用方可以根据返回值决定是否终止转换流程。形式上多写一行判断但这是一种明确的工程习惯。顺序栈的结构体定义、初始化、判空、判满、压栈和弹栈代码如下#include stdio.h #include stdlib.h #define MAX_SIZE 128 typedef struct { int data[MAX_SIZE]; int top; } SeqStack; void initSeqStack(SeqStack *s) { s-top -1; } int isSeqStackEmpty(SeqStack *s) { return s-top -1; } int isSeqStackFull(SeqStack *s) { return s-top MAX_SIZE - 1; } int pushSeq(SeqStack *s, int val) { if (isSeqStackFull(s)) { return -1; } s-top; s-data[s-top] val; return 0; } int popSeq(SeqStack *s, int *val) { if (isSeqStackEmpty(s)) { return -1; } *val s-data[s-top]; s-top--; return 0; }2.2 顺序栈初始化与判空判满的基本逻辑这里有一个非常容易忽略的点初始化时top必须赋为-1而不是0。top -1 表示栈空。压栈时先自增再写入也就是top先变成0然后把数据写到data[0]这正好对应“栈顶指针指向当前栈顶元素”的定义。弹栈时先取出data[top]再把top自减逻辑对称不容易错。如果你把top初始化为0压栈时需要先写data[top]再自增弹栈时需要先自减再取data[top]代码也能跑通但栈顶指针的语义就变成了“指向下一个空位”。两种方案没有绝对的对错但建议全篇保持一致。判断栈满的条件也容易踩坑。top的最大值是MAX_SIZE - 1因为数组下标从0开始。很多人写成s-top MAX_SIZE这实际上是越界了。判空、判满这两件事在代码里看似微不足道但凡是花了几个小时排查内存越界的同学都应该明白这两个条件值几个钱。2.3 一个被忽略的坑MAX_SIZE到底定多少才够初学者最喜欢拍脑袋定一个很大的数组大小比如1024然后觉得万事大吉。但既然是学数据结构不妨算一笔账。32位int类型的最大值是2147483647转成二进制最多占31位因为符号位占1位加上符号最多32位。转成八进制时3个二进制位对应1个八进制位所以最多11位32/3向上取整。转成十六进制时4个二进制位对应1个十六进制位所以最多8位。也就是说即使是int范围内的最大正数用数组长度64都绰绰有余。MAX_SIZE定为128已经是非常保守的余量。但这道题如果只停留在固定数组价值就打折扣了。我建议你在理解固定大小版本后再看一眼动态扩容的做法。具体来说就是用malloc在堆上分配数组当栈满时用realloc翻倍扩容。不要觉得这是多余实际开发中栈作为通用数据结构时你几乎不可能提前预估元素个数。动态扩容的能力很重要后面第6部分我会给出完整实现。3. 链栈实现指针操作的本质就是“从头插”和“从头删”3.1 链栈的结构设计与初始化链栈本质上是一个只在头部插入和删除的单链表。不需要头结点直接让栈顶指针指向链表的第一个节点即可。这里的栈顶指针是StackNode*类型而不是int。链栈的好处是不用关心“栈满”的问题——只要内存还够分配就能继续压栈。所以链栈的push操作只需要检查malloc的返回值不需要检查栈容量。typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int count; } LinkStack; void initLinkStack(LinkStack *s) { s-top NULL; s-count 0; }这里的count字段不是必须的但它记录了栈内元素个数可以在调试时快速确认栈的状态也可以在某些场景下用来限制栈的深度。我建议保留因为结构体里多一个整型字段几乎不占什么空间但排查问题时会很舒服。3.2 push和pop的指针顺序问题先让新节点指向旧栈顶push操作分三步malloc一个新节点。把新节点的next指向当前的栈顶。更新栈顶指针让它指向这个新节点。第三步很容易和第二步搞反。如果先把top更新成新节点再执行newNode-next top这时候top指向的就不再是旧栈顶而是newNode本身等于自己指向自己链表当场断掉。这个错误在思维上非常隐蔽因为代码看起来只是调换了一下顺序但逻辑完全变了。写链栈时有个口诀先连后断先挂新再动旧。就是说永远先让新节点的next指向旧栈顶再修改栈顶指针。这个顺序在单链表头插法里是铁律不仅能帮你写对还能帮你在读别人代码时快速定位问题。int pushLink(LinkStack *s, int val) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (node NULL) { return -1; } node-data val; node-next s-top; s-top node; s-count; return 0; }pop操作是push的逆过程先用临时指针保存当前栈顶节点。取出栈顶节点的data。更新top指针为top-next。free掉之前保存的节点。int popLink(LinkStack *s, int *val) { if (s-top NULL) { return -1; } StackNode *tmp s-top; *val tmp-data; s-top tmp-next; free(tmp); s-count--; return 0; }3.3 内存释放不是可选项是链栈的及格线链栈和顺序栈一个很大的区别就是内存管理。顺序栈的数组要么是静态数组要么是malloc一次不需要在每次push和pop时处理单个元素的内存。链栈则不同push时malloc了节点pop时如果只移动指针而不free就会出现内存泄漏。在课程实验里小程序跑一次就退出内存泄漏问题不明显。但如果你把这个栈写进一个长期运行的服务端程序里每次转换都泄漏几个节点积少成多系统迟早崩。写链栈时建议每次pop之后都问自己一句这个节点还被引用着吗没有引用的话它占的内存谁负责还回去这其实就是C语言内存管理的基本功——谁分配谁释放。malloc对应free位置要一一对应别让内存漏得悄无声息。如果真的使用场景需要频繁压栈弹栈也可以考虑内存池预先分配一批节点压栈时从空闲链表取弹栈时还回去。这在嵌入式领域很常见但作为学习数据结构先把malloc/free的标准做法写利索更重要。4. 核心转换函数与16进制输出的那点事4.1 转换函数的骨架设计把“栈操作”和“进制逻辑”解耦核心转换函数可以利用“栈的接口”把进制转换的逻辑整体封装起来。也就是说转换函数只需要关心十进制数是否还有商未除尽。把余数压栈。从栈中依次弹出余数并输出。至于余数存在什么地方、栈有没有满那是栈实现内部的事。通过调用push接口顺序栈和链栈在转换函数里是可以无缝替换的。下面是使用顺序栈版本的核心转换函数const char *digits 0123456789ABCDEF; void seqStackConvert(int num, int base) { SeqStack s; initSeqStack(s); if (num 0) { printf(0); return; } int n num; while (n 0) { pushSeq(s, n % base); n / base; } while (!isSeqStackEmpty(s)) { int d; popSeq(s, d); putchar(digits[d]); } putchar(\n); }链栈版本长这样void linkStackConvert(int num, int base) { LinkStack s; initLinkStack(s); if (num 0) { printf(0); return; } int n num; while (n 0) { pushLink(s, n % base); n / base; } int d; while (popLink(s, d) 0) { putchar(digits[d]); } putchar(\n); }两个版本的对账逻辑完全一致区别只在栈的具体实现上。这正好印证了“接口与实现分离”的价值转换算法只依赖push、pop、判空这些抽象操作不需要关心栈的底层是用数组还是链表。4.2 digits数组10到15如何映射成A到F十六进制转换里余数10、11、12、13、14、15不能直接输出成数字必须映射成A、B、C、D、E、F。最简单稳妥的办法是准备一个映射字符串const char *digits 0123456789ABCDEF;余数是几就取digits[i]这样10对应A15对应F。我见过有人用switch-case来逐个映射虽然也能跑但代码冗长且容易漏分支。用一个字符串映射是所有做法里最简洁、最不容易出错的。这条经验其实可以推广任何“数字到字符”的映射优先考虑用字符串直接索引而不是写大量条件分支。比如把数字转成十六进制字符串、生成验证码、甚至简单的哈希表都是这个思路。如果想把代码拓展到36进制只需要把digits字符串扩展成0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ其余逻辑一行不改。所以我说这个映射字符串是转换函数的扩展接口别小看它。4.3 三个边界条件0、负数、以及非法进制写转换函数的时候最容易遗漏的是num等于0的情况。while循环条件是n 0如果传入的num是0循环根本不会执行栈是空的如果没有提前判断函数就什么都不输出这显然不对。正确做法是在循环之前特判num 0直接输出0并返回。负数怎么处理如果是课程作业要求通常题目会限定非负整数但你作为开发者应该考虑得更全面。我的处理方式是记录符号转换绝对值输出时先打印一个负号。示意代码如下void convertWithSign(int num, int base) { if (num 0) { printf(0); return; } if (num 0) { putchar(-); num -num; } // 后续逻辑不变 }非法进制怎么处理比如base小于2或者大于digits字符串的长度这种情况建议在函数入口做参数校验直接打印错误提示并返回。一个健壮的函数边界条件不比主逻辑简单但这些都是写代码的基本功值得养成习惯。完整可运行的代码示例我放在第5部分一起给出方便你直接复制编译测试。5. 实测对比与完整源码顺序栈和链栈到底差在哪5.1 可复制的完整C源码下面直接给出一份完整的可运行源码包含顺序栈和链栈两种实现以及对应的转换函数和测试主函数。#include stdio.h #include stdlib.h #define MAX_SIZE 128 // ---------- 顺序栈 ---------- typedef struct { int data[MAX_SIZE]; int top; } SeqStack; void initSeqStack(SeqStack *s) { s-top -1; } int isSeqStackEmpty(SeqStack *s) { return s-top -1; } int isSeqStackFull(SeqStack *s) { return s-top MAX_SIZE - 1; } int pushSeq(SeqStack *s, int val) { if (isSeqStackFull(s)) { return -1; } s-top; s-data[s-top] val; return 0; } int popSeq(SeqStack *s, int *val) { if (isSeqStackEmpty(s)) { return -1; } *val s-data[s-top]; s-top--; return 0; } // ---------- 链栈 ---------- typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int count; } LinkStack; void initLinkStack(LinkStack *s) { s-top NULL; s-count 0; } int pushLink(LinkStack *s, int val) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (node NULL) { return -1; } node-data val; node-next s-top; s-top node; s-count; return 0; } int popLink(LinkStack *s, int *val) { if (s-top NULL) { return -1; } StackNode *tmp s-top; *val tmp-data; s-top tmp-next; free(tmp); s-count--; return 0; } void destroyLinkStack(LinkStack *s) { while (s-top ! NULL) { StackNode *tmp s-top; s-top tmp-next; free(tmp); } s-count 0; } // ---------- 进制转换 ---------- const char *digits 0123456789ABCDEF; void seqStackConvert(int num, int base) { if (base 2 || base 16) { printf(不支持的进制: %d\n, base); return; } SeqStack s; initSeqStack(s); if (num 0) { printf(0); return; } int n num; if (n 0) { putchar(-); n -n; } while (n 0) { if (pushSeq(s, n % base) ! 0) { printf(栈溢出\n); return; } n / base; } while (!isSeqStackEmpty(s)) { int d; popSeq(s, d); putchar(digits[d]); } putchar(\n); } void linkStackConvert(int num, int base) { if (base 2 || base 16) { printf(不支持的进制: %d\n, base); return; } LinkStack s; initLinkStack(s); if (num 0) { printf(0); return; } int n num; if (n 0) { putchar(-); n -n; } while (n 0) { if (pushLink(s, n % base) ! 0) { printf(内存分配失败\n); return; } n / base; } int d; while (popLink(s, d) 0) { putchar(digits[d]); } putchar(\n); destroyLinkStack(s); } // ---------- 测试 ---------- int main() { int nums[] {0, 10, 255, 256, 1024, -255}; printf( 顺序栈 \n); for (int i 0; i 6; i) { printf(%d 2进制: , nums[i]); seqStackConvert(nums[i], 2); printf(%d 8进制: , nums[i]); seqStackConvert(nums[i], 8); printf(%d 16进制: , nums[i]); seqStackConvert(nums[i], 16); } printf(\n 链栈 \n); for (int i 0; i 6; i) { printf(%d 2进制: , nums[i]); linkStackConvert(nums[i], 2); printf(%d 8进制: , nums[i]); linkStackConvert(nums[i], 8); printf(%d 16进制: , nums[i]); linkStackConvert(nums[i], 16); } return 0; }5.2 测试用例说明与实测运行结果我编译运行后的输出如下截取部分 顺序栈 0 2进制: 0 10 2进制: 1010 10 8进制: 12 10 16进制: A 255 2进制: 11111111 255 8进制: 377 255 16进制: FF 256 16进制: 100 -255 2进制: -11111111这几个测试用例覆盖了0检验边界特判。10二进制和八进制结果不对称真正体现了栈的翻转作用。255既包含满位数的二进制又包含十六进制字母映射。256十六进制变成了100保证进位逻辑正确。-255验证负号处理。读者可以自己把测试数组换成长整型数或者换成大一点的数看栈空间是否足够。如果你只使用固定数组的MAX_SIZE128测试到int最大值2147483647转二进制也不会溢出。5.3 顺序栈与链栈的对比结论从功能上讲两者在这个场景下完全等价。但选择哪一种取决于你的具体场景对比维度顺序栈链栈内存占用固定数组无额外指针开销每个节点多一个next指针4~8字节开销容量限制可能存在栈满只要内存充足基本无限制操作速度直接下标访问缓存友好每次malloc/free有系统调用开销实现复杂度简单直观指针操作需要小心适用场景明确知道上限追求性能元素数量不确定需要动态扩展我个人的建议是在做课程设计或考试时顺序栈足够如果你准备把这个栈用在项目里链栈或者动态扩容的顺序栈会更稳妥。6. 从“能交作业”到“能上线”动态扩容与函数泛化6.1 动态扩容的顺序栈写法固定数组的顺序栈有个天然缺陷栈满了就不能再压。对于进制转换这种小规模场景问题确实不大但如果栈是作为一个通用数据结构用在别处就不能假装没有上限了。动态扩容的思路很简单结构体里用指针data指向堆上数组。初始化时分配一个初始容量。push时如果栈满用realloc把容量翻倍。释放时用free释放data。typedef struct { int *data; int top; int capacity; } DynSeqStack; void initDynStack(DynSeqStack *s, int initCapacity) { s-data (int *)malloc(sizeof(int) * initCapacity); s-top -1; s-capacity initCapacity; } int pushDyn(DynSeqStack *s, int val) { if (s-top 1 s-capacity) { int newCap s-capacity * 2; int *newData (int *)realloc(s-data, sizeof(int) * newCap); if (newData NULL) { return -1; } s-data newData; s-capacity newCap; } s-top; s-data[s-top] val; return 0; }这次扩容配合realloc把容量翻倍均摊时间复杂度是O(1)。这句话的意思很简单虽然偶尔扩容一次需要复制数据但扩容次数很少平均下来每次push的开销仍是常数级别。6.2 用函数指针或者内联替换把转换函数泛化到任意进制代码里的digits数组其实已经把“任意进制”的大门打开了。只要把进制参数从2、8、16扩展到任意2到36之间digits字符串相应增长即可。如果你想把“输出成一个字符串”而不是直接打印到控制台也完全可以实现。核心思路是保证栈的push和pop思路不变只是把putchar换成sprintf拼接。这在写序列化工具时非常实用因为很多时候你需要的是一串转换后的字符串而不是一段直接打印到屏幕的字符。再进一步如果想支持小数部分的进制转换就需要用到“乘基取整法”把小数部分不断乘以目标进制取整数部分作为结果的一位。这时候栈就不适用了因为小数部分的计算顺序和输出顺序是相同的不需要反转。6.3 去重中缀转后缀、括号匹配、递归转非递归栈这个数据结构的应用场景远不止进制转换。做课程设计时我建议你把这道题作为起点顺手把以下几个经典案例都过一遍因为它们的共同点都是“需要保存中间状态并在未来某个时刻逆序使用”括号匹配遍历字符串左括号压栈右括号弹栈并检查类型匹配。中缀表达式转后缀表达式操作符压栈遇到优先级更低的操作符时先弹栈。递归转非递归手动用栈保存函数的局部状态。这些题目的共同套路都是发现了“反转”或者“延迟处理”的需求然后直接把栈拿出来用。等你刷完这几个应用再回头看进制转换就会觉得它只是栈的冰山一角。栈并不难难的是识别出“这个场景该用栈”的直觉。这种直觉只能靠多写多练。7. 小结之外的一点个人体会如果只让我留一条经验那就是写代码时别只追求“能跑”要看出题目背后的结构问题。进制转换的数学原理并不复杂除基取余嘛但它最漂亮的地方在于当你意识到余数顺序和输出顺序相反时栈这个数据结构几乎是不需要思考的必然选择。我在实际中这类代码写得越多越觉得栈就是用来做“逆序恢复”的。不管是二进制转换、浏览器后退、文本撤销、函数调用栈通通都是同一个套路先遇到的东西先存起来最后反而先出来。顺序栈和链栈的具体代码本文都已经给出完整版本还带了测试。你能把这份代码跑通再把栈的接口调用逻辑讲清楚这道题掌握得就足够了。后续考试或者面试里如果碰到“用栈实现XX”的变体你只要抓住“哪些数据需要先存后取”这个核心基本都不会失手。最后特别提醒一下链栈的destroy函数千万别忘。小程序跑完操作系统会回收内存所以看起来没事但在嵌入式设备或长期运行的服务里内存只会越积越多。写完一份栈请顺手把释放内存的出口补齐这个习惯比任何技巧都值钱。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
