栈与进制转换：顺序栈和链栈实现十进制转二/八/十六进制

简介：栈是数据结构中最基础也最实用的线性结构之一，其“后进先出”（LIFO）特性为很多逆序处理问题提供了天然解法。进制转换中的“除基取余”算法会依次产生从低位到高位的余数，而输出结果却需要从高位到低位，这种顺序反转恰好与栈的弹出顺序完美契合。顺序栈基于数组实现，访问高效、容量固定，适合元素个数可预估的场景；链栈利用链表头插法实现，支持动态分配内存，适合元素数量不确定的工程环境。在C语言工程实践中，通过接口解耦、边界条件处理（零、负数、非法进制）以及动态扩容扩展，可以将课程作业级的代码提升为可上线的通用工具。该技术广泛应用于进制转换、括号匹配、表达式求值、函数调用栈等经典场景。本文以十进制转2进制、8进制、16进制为例，给出顺序栈与链栈的完整源码与对比，强调内存管理和接口分层的重要性，帮助开发者建立“识别逆序需求、选择合适栈结构”的数据结构直觉。 这道题我太熟了。学数据结构的时候，老师一定会布置一次“用栈做进制转换”的作业，十个人里有八个直接写数组，剩下两个写完之后没想明白为什么非要用栈。刷到这道题的读者，大概率也是在准备考试、赶课程设计，或者想把手里的代码写得漂亮一点。

先把目标说清楚：顺序栈和链栈是两个实现载体，核心要解决的问题只有一个——把十进制整数按“除基取余”的方式，转换成2进制、8进制、16进制并输出。这个场景非常典型，因为它恰好踩中了栈这个结构最核心的特性：后进先出。你算余数的顺序是从低位到高位，而读结果的顺序是从高位到低位，中间差了一个“反转”。反转这件事，用栈做是最顺手的。

下面我把完整源码、实现思路、以及我当年踩过的各种坑一并写出来，代码可以直接抄，原理部分多花两分钟看，后面做其它栈的应用你会轻松很多。

1. 短除法与栈的“翻转”宿命：为什么这道题非用栈不可

1.1 除基取余法的输出顺序问题

先回顾一下进制转换的基础算法。把十进制数除以目标进制，取余数，再用商继续除，直到商为0。所有的余数从后往前拼接，就是转换结果。

拿255转二进制举例：

• 255 ÷ 2 = 127 余 1
• 127 ÷ 2 = 63 余 1
• 63 ÷ 2 = 31 余 1
• 31 ÷ 2 = 15 余 1
• 15 ÷ 2 = 7 余 1
• 7 ÷ 2 = 3 余 1
• 3 ÷ 2 = 1 余 1
• 1 ÷ 2 = 0 余 1

余数依次是：1, 1, 1, 1, 1, 1, 1, 1，最后结果是11111111，恰好一样，所以这个例子完全看不出翻转的意义。换一个数，255转16进制：

• 255 ÷ 16 = 15 余 15
• 15 ÷ 16 = 0 余 15

余数依次是15, 15，需要映射成F，结果FF，还是对称的。这就是初学时的迷惑点：很多测试用例“碰巧”是对称的，导致你根本意识不到栈的必要性。

看个不对称的例子，十进制10转二进制：

• 10 ÷ 2 = 5 余 0
• 5 ÷ 2 = 2 余 1
• 2 ÷ 2 = 1 余 0
• 1 ÷ 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操作分三步：

1. malloc一个新节点。
2. 把新节点的next指向当前的栈顶。
3. 更新栈顶指针，让它指向这个新节点。

第三步很容易和第二步搞反。如果先把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的逆过程：

1. 先用临时指针保存当前栈顶节点。
2. 取出栈顶节点的data。
3. 更新top指针为top->next。
4. 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对应A，15对应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_SIZE=128，测试到int最大值2147483647转二进制也不会溢出。

5.3 顺序栈与链栈的对比结论

从功能上讲，两者在这个场景下完全等价。但选择哪一种取决于你的具体场景：

我个人的建议是，在做课程设计或考试时，顺序栈足够；如果你准备把这个栈用在项目里，链栈或者动态扩容的顺序栈会更稳妥。

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函数千万别忘。小程序跑完操作系统会回收内存，所以看起来没事；但在嵌入式设备或长期运行的服务里，内存只会越积越多。写完一份栈，请顺手把释放内存的出口补齐，这个习惯比任何技巧都值钱。

本文还有配套的精品资源，点击获取