讲数据结构的栈那章时我每届都要花不少时间讲这道 Dec2Bin 顺序栈题。题目本身不复杂就是把一个十进制数转成二进制限定用顺序栈实现但恰恰是这种“看起来简单”的题最能暴露大家对栈的理解是不是停留在背代码层面。很多同学能背出 InitStack、Push、Pop 的函数体但一问他“为什么这里非得用栈数组不也能逆序输出吗”就答不上来了。这篇文章就把这个题目从算法原理到 OJ 提交完整拆一遍适合正在学数据结构、准备机试或者刷 PTA 题库的朋友对照着看尤其是对栈部分“会抄代码但没想透”的读者应该能补上最关键的那层理解。1. 为什么十进制转二进制这道题偏偏要考栈1.1 除2取余法的输出顺序悖论先回到最基本的问题十进制怎么转二进制。教科书上写的是“除2取余倒序排列”。以 13 为例13 除以 2商 6余 16 除以 2商 3余 03 除以 2商 1余 11 除以 2商 0余 1。计算过程中得到的余数序列是 1、0、1、1但 13 的二进制是 1101正好是余数序列的反向。这就是“倒序排列”的含义余数是一个一个算出来的先算出来的是低位后算出来的是高位而二进制书写习惯正好是高位在前。这个顺序上的矛盾看着不起眼却是整个题目的题眼。如果只是拿数组存余数存完再逆序输出当然也能得到正确答案但这时候你是在用“额外的一次反方向遍历”去抵消计算顺序和输出顺序的差异。而栈这个数据结构天生就是干这个事的。1.2 栈恰好是“反着存、正着取”的天然工具栈的特点就一句话后进先出LIFO。后放进去的元素反而先被取出来这和我们刚才遇到的问题严丝合缝。算出来的余数依次压进栈里先进栈的是低位余数后进栈的是高位余数出栈的时候后进的高位余数先出来低位余数最后出来。一进一出之间顺序被自动翻正了。拿 13 来说余数序列 1、0、1、1 依次入栈后栈底到栈顶是 1、0、1、1。出栈时依次弹出的是 1、1、0、1拼起来就是 1101。整个过程不需要额外记录“我现在存了几个数”也不需要写一个 for 循环从后往前遍历栈结构本身就替你完成了逆序。生活里最直观的类比就是一叠盘子你洗完一个盘子摞在顶上后面洗的永远在上面真正要用的时候你先拿到的总是最后洗的那个。除2取余法产生的余数就像洗完的盘子天然具有“后来居上”的顺序而栈正是为这种场景准备的工具。1.3 不借助栈也能做三种替代方案的对比既然题目点名要用栈那就有必要搞清楚栈相对其他方案到底强在哪否则以后换一个不限定数据结构的题目你可能还是不会选栈。我见过不少同学用数组、递归、甚至字符串拼接来做都能得到正确答案但各自都有代价。数组逆序输出的问题在于你需要自己维护一个下标计数器知道余数存到了第几个位置最后还得记得从后往前输出。这相当于把“逆序”这个逻辑用手工方式做了一遍代码多几行倒是小事关键是这种写法没有体现算法结构纯粹是在堆过程。递归方案本质上是在用函数调用栈代替显式栈思路是先递归到商为 0然后回溯时输出余数。代码确实简洁但有两个隐患一是递归深度受系统栈限制遇到大一点的数风险更高二是如果题目明确要求“用栈实现”递归等于换了个方式绕过考察点在严格判题的场景下可能直接算不合法。还有一个很隐蔽的错误方案有人想直接从最高位开始填但十进制数转二进制时你根本没提前知道二进制最高位在哪一位除非先做一次对数运算或者移位估算反而把问题搞复杂了。三种方案放在一起对比就很清楚了方案思路缺点数组 逆序输出存余数后反向遍历需额外维护下标和逆序逻辑递归利用调用栈回溯输出深度受限可能偏离题意顺序栈入栈存余数出栈即逆序完全匹配本题语义栈方案的精髓在于你不需要“想办法”去逆序它天然就是逆序的。这才是数据结构选型应该有的思考方式。2. 顺序栈与链式栈的选择题目点名顺序栈的合理性2.1 顺序栈和链式栈的本质差异栈只有两种主流实现方式顺序栈和链式栈。顺序栈底层用一块连续的内存配合一个动态数组来存元素链式栈底层则用链表节点每个节点存一个数据和指向下一个节点的指针。两者的核心差异在于存储结构。顺序栈的元素在物理内存里是挨着的栈顶指针可以直接通过数组下标访问入栈出栈都是 O(1) 并且常数极小缺点是容量固定后一旦装满就需要扩容扩容涉及申请新内存和整体搬移。链式栈的每个节点是单独申请的元素分散在内存各处通过指针串起来理论上不会出现“栈满”的情况缺点是每个节点都多存一个指针空间上有额外开销而且频繁申请释放节点效率不如连续内存访问来得稳定。这个区分在 Dec2Bin 这个具体题目里非常明显这个程序里栈最多需要存多少元素一个 int 范围内的十进制数二进制位最多也就 32 位左右。你甚至可以在心里预估这个栈的容量上限完全没必要为了这种规模的数据去搞链式节点。2.2 为什么 PTA 这类题目偏爱顺序栈观察一下 PTA 和其他 OJ 平台上数据结构部分的题目凡是考栈的大多数默认顺序栈实现。这不是出题人偷懒而是由教学和判题双重因素决定的。教学内容上顺序栈是栈的基础形态。教科书讲栈的时候通常先用顺序表引出静态数组实现让你理解栈顶指针的移动逻辑然后再讲链式实现作对比。题目顺序也通常是把顺序栈作为第一个要求掌握的实现方式。链式栈考察的其实是链表能力属于另一组知识点如果题目没有特别说明或者直接写着“顺序栈”那就应该按顺序栈来做。判题环境上顺序栈代码更短、运行更快。OJ 系统对运行时间和内存都有上限顺序栈的连续内存访问对缓存更友好入栈出栈不涉及指针跳转。而链式栈每操作一次就要走一次指针在这个题目反复入栈出栈的场景下虽然复杂度同样是 O(1)但常数时间明显更大。2.3 顺序栈在 Dec2Bin 中的特殊优势Dec2Bin 这个应用场景里顺序栈还有一个链式栈给不了的便利你可以提前精确预估需要的栈空间。一个 int 最大值二进制不超过 32 位所以栈深最多 32。这意味着大多数情况下栈永远不会满扩容逻辑甚至只是“写了个但根本没触发”。正因为如此这道题非常适合用来练习顺序栈的完整生命周期初始化时分配空间、入栈时检查容量、出栈时判断栈空、最后释放空间。一套流程走完顺序栈的所有核心接口都被覆盖了。如果换成链式栈反而要额外处理节点申请失败、节点回收这些问题对初学者来说干扰项太多。所以题目点名“顺序栈”本质上是在帮你划重点这一章你只需要把连续存储结构下的栈操作练熟就够了链式栈留给别的题目。3. 顺序栈四件套从空栈判断到动态扩容的完整实现3.1 结构体定义与 base/top 指针约定顺序栈的一个核心约定是top 指针到底指向栈顶元素还是指向栈顶元素的下一个位置。这个约定不同空栈判断和入栈出栈的写法就完全不同。国内教材最常用的约定是 top 指向栈顶元素的下一个位置空栈时 top base入栈时先存值再移动指针出栈时先移动指针再取值。结构体方面顺序栈需要三个成员base 指向栈底top 指向栈顶stacksize 记录当前容量。类型上我习惯给元素类型和函数返回值各起一个别名方便以后切换元素类型。#include stdio.h #include stdlib.h #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status; typedef int SElemType; typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack;base 指针是整个栈的生命线。栈空时 top 指向 base栈满时 top - base 等于 stacksize。后面所有接口都是围绕这三个成员之间的数量关系展开的只要把 base/top 的语义搞明白栈的其他操作都不会写错。3.2 初始化、入栈与动态扩容最容易写错的三行代码初始化就是给 base 分配一块连续的初始空间把 top 指向 basestacksize 设为初始容量。这一步的坑主要是没检查 malloc 的返回值分配失败还继续往下走程序直接段错误。Status InitStack(SqStack *S) { S-base (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if (!S-base) { exit(0); } S-top S-base; S-stacksize STACK_INIT_SIZE; return 1; }入栈操作里有一个很经典的写法先判断栈是否已满满则扩容然后执行*(S-top) e。注意这个表达式是“先给 top 当前指向的位置赋值再把 top 向后移动一位”对应的是 top 指向栈顶元素下一个位置这个约定。Status Push(SqStack *S, SElemType e) { if (S-top - S-base S-stacksize) { int oldSize S-stacksize; SElemType *newbase (SElemType *)realloc(S-base, (oldSize STACKINCREMENT) * sizeof(SElemType)); if (newbase NULL) { return 0; } S-base newbase; S-top S-base oldSize; S-stacksize oldSize STACKINCREMENT; } *(S-top) e; return 1; }扩容的部分我特别提一下很多人在这里直接写S-base (SElemType *)realloc(...)realloc 返回 NULL 时就会把原来的 base 指针覆盖掉旧内存既没释放也找不回来了。正确做法是先用临时变量接收 realloc 的返回值确认非空后再赋给 base。还有一点容易错扩容后必须重新计算 top 的位置。新申请的连续空间里已有元素都在 base 到 base 旧容量之间所以S-top S-base oldSize。如果漏掉这一步top 还指着旧地址整个栈就散了。3.3 判空、取栈顶与销毁三个容易被忽略的细节判空就一行判断S-top S-base。注意这里用的是相等比较不是大于等于或者小于。曾经有同学写成top base结果空栈时明明相等也判定为“非空”出栈函数里直接对空栈执行取值运行结果完全不可控。出栈操作是入栈的逆过程先判断栈空然后把 top 向前移动一位取出移动后指向位置的值。写成*e *(--S-top)。这个式子和入栈的*(S-top) e正好凑成一对建议连着记忆不容易混。Status Pop(SqStack *S, SElemType *e) { if (S-top S-base) { return 0; } *e *(--S-top); return 1; } Status StackEmpty(SqStack S) { return S.top S.base ? 1 : 0; } Status GetTop(SqStack S, SElemType *e) { if (S.top S.base) { return 0; } *e *(S.top - 1); return 1; }取栈顶 GetTop 和出栈 Pop 的区别也要分清Pop 会真正把元素弹出Top 只是看一眼栈顶元素栈的结构不变。在 Dec2Bin 主流程里我们用不到 GetTop但很多其他题目会用到顺手写在这里方便以后复用。最后是销魂的一步释放内存。链式栈清空要逐个节点释放顺序栈简单得多只要 free 一次 base 就完事了但很多人写完整段程序根本想不起来还有这一步。OJ 不会因为你内存泄漏就报错但养成释放的习惯以后写大程序能少掉很多莫名其妙的毛病。void DestroyStack(SqStack *S) { if (S-base) { free(S-base); S-base NULL; S-top NULL; S-stacksize 0; } }4. Dec2Bin 主流程从除2取余到逆序输出的完整链路4.1 核心函数完整代码与逐行说明把栈的接口写完Dec2Bin 本身反而变得很简单。核心逻辑就是三步初始化栈反复取余入栈再反复弹出输出。我把主流程封装成一个 Dec2Bin 函数输入十进制数 n直接输出对应的二进制字符串。void Dec2Bin(int n) { SqStack S; SElemType e; InitStack(S); if (n 0) { printf(0\n); DestroyStack(S); return; } while (n 0) { Push(S, n % 2); n / 2; } while (!StackEmpty(S)) { Pop(S, e); printf(%d, e); } printf(\n); DestroyStack(S); } int main() { int n; while (scanf(%d, n) ! EOF) { Dec2Bin(n); } return 0; }主流程里第一个 while 是在不断产生余数并压栈模拟的是除2取余的过程第二个 while 是在不断弹栈输出利用栈的 LIFO 特性把顺序翻过来。这两步之间没有任何多余操作整个算法的复杂度也是 O(log n)栈的最大深度对 int 范围内输入不超过 32。main 里用 while 循环读入是为了处理多组测试数据。OJ 平台上很多题目都是“多组输入直到文件结束”用scanf(%d, n) ! EOF是通行写法能同时应付单组和多组输入。4.2 n 0 这种边界情况十个人有八个会漏如果你直接拿上面的代码去掉 n 0 那个分支去测输入 0 时程序一行输出都没有结果直接判错。原因很直白0 除以 2 商 0 余 0但 while (n 0) 这个循环是从一开始就进不去的栈里一个元素都没有自然什么都输出不出来。正确的处理方式就是在入栈之前单独判断if (n 0) { printf(0\n); return; }。这个分支看起来多余却是一道最常见的送分变送命题。我改作业时发现每届总有学生卡在这个测试点上而且几乎都是在本地测试时只测了正整数从来没拿 0 去试过。4.3 测试用例设计与结果验证写完了代码最后一步是用测试数据验证。我习惯先列一组覆盖边界的用例再逐个核对输出输入十进制数期望二进制输出说明00边界情况最容易漏11最小正整数210进位发生311连续进位131101经典教学用例25511111111满 8 位方便人工核对1024100000000002 的整数次幂手工验证时拿 13 当例子走一遍第一次取余得 1 入栈第二次得 0 入栈第三次得 1 入栈第四次得 1 入栈栈内从底到顶是 1、0、1、1出栈时先取 1 再取 1 再取 0 再取 1输出拼起来就是 1101。这个逐步验证的过程建议自己亲手在纸上画一遍光看不画很容易以为自己懂了实际一写代码就露馅。这套流程不仅限于二进制。只要把除以 2 的模数改成 8 或者 16代码就变成了十进制转八进制、十六进制原理完全一致。这也是为什么很多题目把 Dec2Bin 当模板题它就是栈应用最基础的一个范例。5. 在 PTA 平台提交时最容易翻车的几个点5.1 编译层面的低级错误先排除环境问题代码逻辑再对编译不通过也拿不到分。我在平台上帮学生看提交记录最常见的是三类编译问题缺头文件、main 函数返回类型不合法、提交语言选错。用了 malloc 和 free 却没有#include stdlib.h编译器会警告隐式声明在某些严格的编译选项下直接报错写了 void main() 在 C 标准里不合法OJ 的后台编译器可能直接拒绝还有的同学本地用的 C 编译器写的是 C 风格的代码提交时语言选了 C 或者反过来导致代码因为 printf 未声明之类的问题编译失败。一个稳妥的自查方式是把代码复制到草稿纸级别的纯文本编辑器里看一眼确认没有中文字符混入有些编辑器会自动把引号替换成全角再确认 include 完整最后提交前看看语言选项有没有选对。5.2 功能正确却拿不到分输出格式的隐性扣分很多题目的样例输出里带了换行于是有人就只给最后一个输出加换行中间的不加判题系统按行比对直接判错。还有人在调试时顺手写了printf(请输入一个整数)这种提示语本地跑着很好拿到 OJ 上就是多出的输出照样判错。OJ 的判题逻辑很简单比对你的程序输出和标准答案输出要求逐字一致多一个空格、少一个换行都不行。所以 Dec2Bin 最好是每个结果单独一行也就是每组输出结束都要打印一次换行。主流程里我在第二个 while 结束后单独写了printf(\n)就是为了让每个二进制数独占一行避免多个测试数据连在一起没法分辨。调试用的 printf 一定要在提交前删干净或者在调试完成后注释掉。最保险的做法是提交前重新读一遍题目描述里的输出格式部分照着样例格式逐字符检查。5.3 逻辑正确但栈写崩了内存和指针层面的坑还有一类提交错误既不是编译问题也不是输出格式问题而是代码在本地跑得好好的一交上去就运行时错误。这种绝大多数是指针或者内存出问题导致的。举个例子如果 Pop 函数里没有做空栈判断而主流程因为边界情况处理不当对空栈执行了 Pop那就会访问到非法内存轻则返回值不对重则直接崩溃。虽然 Dec2Bin 主流程里第二个 while 有条件判断但这种依赖“调用方保证参数合法”的写法很脆弱Pop 内部自己检查空栈才可靠。还有一个隐蔽问题是整数类型范围。如果题目改成了十进制长整数转二进制输入的 n 用 int 接收超出 int 范围的数据一进来就被截断了后续所有计算都基于一个错误的值。遇到这种题应该第一时间把 n 的类型改成 long long同时注意取余和除法的操作数类型保持一致。5.4 一个实用的自查顺序刷这种带数据结构的 OJ 题我自己的习惯是先按这个顺序把代码过一遍再提交先检查边界条件有没有覆盖尤其 0 和最大值再从编译依据上确认头文件和 main 形式然后检查所有输出是否严格匹配示例格式最后跑一遍本地测试数据对照期望结果逐项核对。四步走完这类基础题基本上一次就能过。调试的时候我还特别喜欢用手工模拟法就是拿一张纸画一个栈的示意图把测试数据一步步往里填、往外取每次入栈出栈都更新一遍图。这个方法看起来笨但对理解和排查那种“为什么我的输出反了”的问题特别有效。栈这个结构抽象程度比较高光靠脑子转很容易漏步落到纸上基本一眼就能看出问题在哪。