栈这东西学的时候觉得抽象写的时候觉得别扭但真正把一道题做透之后你会发现它其实特别“接地气”。就拿PTA上这道 Dec2Bin(顺序栈) 来说题目本身不复杂——把十进制整数转换成二进制输出但要求用栈来实现。很多同学第一反应是直接除2取余倒着输出不就行了吗为什么非得用栈等你真按题目要求写完、提交、调试、通过再回头看这一圈绕得特别值。这篇就按我的实际做题过程把顺序栈实现 Dec2Bin 的来龙去脉、踩坑点、调试技巧完整聊一遍适合正在学数据结构、刷PTA栈相关题目、或者对“栈到底有什么用”还不太有感觉的同学参考。1. 十进制转二进制为什么偏偏要绕一圈用栈1.1 除2取余法的执行顺序天然就和输出顺序“对着干”先回顾一下十进制转二进制的手算方法。比如要把 13 转成二进制13 ÷ 2 6 余 16 ÷ 2 3 余 03 ÷ 2 1 余 11 ÷ 2 0 余 1从下往上读余数1101这就是 13 的二进制表示。注意关键词从下往上读。可计算的时候是自上而下产生余数的。人脑可以等算完再倒着看但机器不行——它得先把算出来的每个余数存起来到最后再逆序取出。存储时是正序先算的余数先存取用时却要逆序后算的余数先取这不就是活脱脱的**后进先出LIFO**吗刚好这就是栈的定义。所以这道题的核心逻辑就一句话把“除2取余”产生的余数依次压栈所有余数都算完之后再依次出栈输出用栈天然解决了“先产生的余数最后输出”这个反转问题。1.2 栈在这里到底扮演了什么角色理解栈的作用别把它想得多高深。你就把栈想象成一摞盘子你只能从最上面拿盘子也只能往最上面放盘子。Dec2Bin 场景里余数就是一个一个往这摞盘子上放最后取的时候最晚放上去的最先被拿走——也就是最高位最先被输出完美还原“从下往上读余数”的手算过程。栈在计算机里就是为这类“反转序列”场景准备的。类似的还有括号匹配最晚遇到的左括号要先被匹配、浏览器的后退键最后访问的页面先回退、函数调用栈最后调用的函数先返回。Dec2Bin 可以说是了解“栈到底能解决什么实际问题”最直观的入门案例。PTA 把它单独拎出来作为顺序栈的实验题目的不是考你会不会进制转换而是考你有没有理解栈的“LIFO”特性并能在真实任务里主动使用它。1.3 顺序栈和链栈这道题里为什么建议选顺序栈栈有两种常见实现方式顺序栈用数组模拟和链栈用链表模拟。PTA 题目明确要求“顺序栈”说明考察重点就是数组 栈顶指针的配合。这道题用顺序栈有几个实打实的理由栈的最大深度是确定的。一个 int 类型的十进制数最多 32 位转换出的二进制位数不会超过 32 位不算符号位的话。栈容量只需要开 32 或 50 就绝对够用顺序栈不用担心“放不下”。顺序栈实现简单、直观。数组下标就是栈的位置栈顶指针 top 整数一加一减就完成入栈出栈比链表节点的动态分配、指针指来指去省心得多。评测环境更友好。在线判题系统对内存、时间都有要求顺序栈空间连续、随机访问快、没有动态内存管理的开销性能上更稳妥。链栈的优势在于栈深不确定、需要频繁增删的时候。但这道题栈深不但确定而且很小用链表反而有点“杀鸡用牛刀”。做题时心里要有数不是每一种栈实现都适合所有场景选型本身就是算法设计的一部分。2. 顺序栈的核心设计结构定义和基础操作细节2.1 顺序栈的结构定义先搞清楚几个关键字段写顺序栈第一步是定义结构体。常见定义方式如下#define MAXSIZE 100 // 栈的最大容量 typedef struct { int data[MAXSIZE]; // 用数组存放栈元素 int top; // 栈顶指针 } SqStack;这里有几个细节值得琢磨。数据类型题目只要求转二进制用 int 就够。但如果你想把代码复用到八进制、十六进制转换data 类型依然用 int 没问题因为余数就是整数。真正要换的是进制基数和输出格式。MAXSIZE 取多大很多人随手写 100其实这道题转换 int 范围内的十进制数二进制位数最多也就 32给 50 绰绰有余。写 100 完全没有问题但我个人建议养成“按需分配”的习惯容量开多大取决于栈内最多可能有多少个元素。以后做表达式求值、迷宫求解这类题时预估栈深度是非常重要的设计步骤提前养成估算的习惯能避免不少“段错误”。top 的含义一定要界定清楚。这是整个顺序栈里最容易出 bug 的地方。2.2 top 的两种约定指向栈顶元素还是指向栈顶元素的下一个位置很多教材和网课里 top 的初始化和入栈出栈写法都不一样原因就是 top 的含义有两种约定约定Atop 指向栈顶元素所在位置。栈空时 top -1。入栈时先 top再 data[top] x。出栈时 x data[top]再 top--。约定Btop 指向栈顶元素的下一个空位。栈空时 top 0。入栈时 data[top] x再 top。出栈时 top--再 x data[top]。两种写法都能用但混用就会出大问题。一旦你把 A 的初始化配 B 的入栈逻辑第一次入栈就会丢数据把 B 的初始化配 A 的出栈逻辑读到的永远是错误位置。这道题我用的是约定A栈空 top -1。因为我个人觉得 -1 作为栈空标识更直觉而且判断栈满的条件 top MAXSIZE - 1 也很清晰。但这纯粹是个人习惯关键是整套逻辑内部统一。你写代码前先问自己一句“我现在这个 top 到底指哪”写清楚后面能省一堆调试时间。// 初始化 void InitStack(SqStack *S) { S-top -1; } // 判空 int StackEmpty(SqStack *S) { return S-top -1; } // 入栈 int Push(SqStack *S, int x) { if (S-top MAXSIZE - 1) { return 0; // 栈满入栈失败 } S-data[S-top] x; return 1; } // 出栈 int Pop(SqStack *S, int *x) { if (StackEmpty(S)) { return 0; // 空栈出栈失败 } *x S-data[S-top--]; return 1; }2.3 入栈出栈的边界条件到底要不要判满判空这里有个很多新手会忽略的细节判满和判空不是可写可不写的。这道题的栈深很小有人觉得栈根本不会满于是 Push 不判满。但假设你的 MAXSIZE 开的是 32而输入的十进制数恰好是 2 的 31 次方级别二进制位数就是 31 位加符号位处理时可能会多一位一个不留神就溢出了。数组越界写入在 C 语言里不会立刻报错它会悄悄覆盖栈旁边的内存表现可能是数据错乱也可能是段错误排查起来特别费劲。Pop 也一样。如果出栈前不判空遇到空栈还继续 top--top 会一路跌到 -2、-3下一次 Push 的时候直接破坏数据。这类内存类错误在PTA评测里最常见的反馈就是“段错误”或者“答案错误”有时候一次测试过、另一次挂掉非常恶心。提示养成“操作前先检查状态”的习惯。Push 前判满Pop 前判空这是顺序栈代码最基本的安全保障。3. 核心实现Dec2Bin 完整流程与代码落地3.1 从十进制到二进制主流程的完整推演用栈实现十进制转二进制整体流程可以拆成四个阶段第一阶段初始化栈。调用 InitStack让 top -1确保栈是干净的。第二阶段循环取余、依次压栈。只要 N 不为 0就反复执行余数 N % 2把余数 Push 进栈然后 N N / 2。这里注意这个循环的条件是 N 不等于 0因为 N 整除到 0 时所有二进制位都已经生成完毕。第三阶段出栈输出。只要栈不为空就 Pop 一个元素输出。出栈顺序就是二进制从高位到低位的正确顺序。第四阶段特判 N 0。这是个最容易丢分的地方。如果输入的十进制数本身就是 0第二步的循环一次都不会执行栈是空的第三步也输出不了任何内容。可 0 的二进制就是 0必须单独处理。最简单的办法是开头判断 N 0 就直接输出 0 并返回。3.2 可提交的完整代码以 C 语言为例下面给出一份完整的代码可以直接参考或提交到 PTA 的编程题模式中。#include stdio.h #define MAXSIZE 50 typedef struct { int data[MAXSIZE]; int top; } SqStack; void InitStack(SqStack *S) { S-top -1; } int StackEmpty(SqStack *S) { return S-top -1; } int Push(SqStack *S, int x) { if (S-top MAXSIZE - 1) { return 0; } S-data[S-top] x; return 1; } int Pop(SqStack *S, int *x) { if (StackEmpty(S)) { return 0; } *x S-data[S-top--]; return 1; } void Dec2Bin(int n) { SqStack S; InitStack(S); if (n 0) { printf(0); return; } while (n ! 0) { Push(S, n % 2); n n / 2; } int x; while (!StackEmpty(S)) { Pop(S, x); printf(%d, x); } } int main() { int n; scanf(%d, n); Dec2Bin(n); return 0; }这段代码有几个地方值得展开讲讲。为什么 while 循环用n ! 0而不是n 0因为负数在 C 语言里的除法取余行为和正数不同。C99 标准规定整数除法向零取整余数的符号和被除数相同。如果 n 是负数比如 -13-13 % 2的结果是 -1-13 / 2的结果是 -6继续循环依然会产生负数余数最后输出出来是一串 -1 和 0 的混合根本对不上。但 PTA 这道题默认输入是非负整数所以n ! 0和n 0效果相同。如果你想严谨处理负数需要先取绝对值或者改用无符号整数接收输入。为什么最后用 Pop 边取边打印理论上也可以先全部 Pop 到一个数组里再倒着输出但那样就多了一个数组多了一层中转完全没必要。栈的作用就是替我们记住顺序出栈的瞬间正是需要输出的顺序直接打印最干净。3.3 边界情况和测试用例动手之前先把这些想清楚写这种算法题能不能一次 AC 往往不取决于主流程而是取决于边界情况。Dec2Bin 的边界测试我建议至少覆盖这几种输入期望输出说明00最容易被忽略栈空时必须有特判11最小正整数210产生第一位是 0 的二进制131101经典手算用例255111111118 位全 11024100000000002 的幂二进制是 1 后跟一串 02147483647111111111111111111111111111111131个1int最大值检查栈容量尤其是“2 的幂”这类输入它产生的二进制是“1 后面全是 0”如果出栈顺序错一位结果就完全不对用来验证栈的“反转”功能特别有效。3.4 复杂度分析这几分不能丢很多同学做 PTA 只看对错不看复杂度但数据结构课程的实验题面试笔试也经常追问复杂度还是要习惯性分析一下。时间复杂度十进制数 n 转成二进制二进制位数大约是 log₂(n1) 位。循环里的除法和取余各执行约 log₂ n 次出栈也约 log₂ n 次所以整体是O(log n)。空间复杂度栈的大小也随着位数增长约 log₂ n所以是O(log n)。这个复杂度并不是这道题的重点考点但“因为每除 2 一次位数减少一半”这个思考过程能帮你建立对数复杂度的直觉。以后学归并排序、二分查找时间复杂度 O(log n) 就不再是一个抽象概念了。4. PTA 提交实战最容易踩的坑和排查方法4.1 拿到题先分清模块化设计函数题还是编程题PTA 上的栈题有两种常见形式。一种是函数题平台已经给了主函数和部分接口只要求你补全Dec2Bin或Push/Pop几个函数另一种是完整编程题整个程序含 main、结构体定义、所有函数都要你自己写。这两种模式的代码组织方式差别很大。函数题要注意你不能随便改平台给定的函数签名。比如平台要求void Dec2Bin(int n)你却写了个返回类型是 int 的int Dec2Bin(int n)编译直接报错。平台要求的Push可能带SqStack *S, int e如果你擅自改成SqStack S值传递那所有栈的修改都不会生效逻辑必错。完整编程题就自由多了你可以自己决定结构体细节但也意味着初始化、判空、判满统统要自己负责少一个环节程序就出问题。提示提交前先看清楚题目给的代码框架是在“补全”还是“白手起家”。这是个很低级但每年都有不少人踩的坑。4.2 经典报错逐条解读段错误、答案错误和格式错误PTA 的评测结果一般有几种答案正确、部分正确、答案错误、格式错误、段错误、编译错误、运行超时。在 Dec2Bin 这道题里常见情况如下。段错误最常见的原因就是数组越界。比如 MAXSIZE 开得太小或者入栈时没判满数据写到了数组边界以外。另一个原因是用野指针操作栈比如声明了SqStack *S但没有分配内存就直接S-top -1。记住栈结构用局部变量声明即可SqStack S;然后取地址S传递根本不需要 malloc。答案错误的最常见原因就是 top 约定混乱。你初始化是 -1入栈却写成data[top] x这其实是先赋值再自增等效于把 x 放到了 data[0] 对了但如果 top 初始为 0 时这样写就出问题。还有 Pop 写成x data[--top]或x data[top--]不加区分只要约定统一写法就有唯一正确答案。用几个手算用例跑一遍基本就能定位。格式错误也很常见于这类输出题。PTA 对空格、换行非常敏感。如果题目要求输出所有二进制位后换行而你最后没有printf(\n)就会报格式错误。还有如果有多组测试数据每组之间要不要换行、末尾要不要多一个空格都要严格按题目描述来。4.3 调试技巧写几个小用例用 printf 大法快速定位有些人调试喜欢用 IDE 的断点但 PTA 做题场景下我更推荐直接在代码里加 printf 观察中间状态。比如在入栈后加一行printf(push: %d, top: %d\n, n % 2, S.top);在出栈时加一行printf(pop: %d, top: %d\n, x, S.top);然后输入 13观察输出序列。如果看到的输出是 3 1 1 0那就说明你输出的不是余数而是把中间计算过程也输出了问题出在循环体没写对。如果看到的是 1 1 0 1说明栈的功能正常。还有个更快的定位思路先不写栈直接除2取余逆序输出确认进制转换算法本身没毛病再替换成栈实现。这样就把问题缩小到了“栈实现是否可靠”而不是“进制转换是否理解错了”。我调试这类题时习惯先手算一遍预期结果再让程序输出中间值对比基本上一轮就能找到 bug。4.4 二次调用和多组数据栈的“复位”问题不能疏忽PTA 的测试用例往往是多组数据同一个测试点可能会多次调用 Dec2Bin。这时候如果函数内部每次都重新声明SqStack S;并调用InitStack(S)那没问题每次都是全新栈。但如果你把栈声明成全局变量初始化只做一次第二次调用前没把 top 重置回 -1就会出现“上次遗留的数据还在栈里”的问题。输出结果会莫名多出一串数字看起来特别诡异。我见过有同学把一个全局栈用在多个函数里第一组数据跑完没重置第二组数据直接把第一组的二进制串也输出了怎么都对不上。以后但凡涉及状态型的数据结构栈、队列、链表头节点只要函数可能被多次调用进入函数后第一件事就是把结构重置干净。5. 这道题做完之后还可以往哪几个方向延伸5.1 通用进制转换把 Dec2Bin 轻松改成 Oct2Bin、Dec2Hex这道题叫 Dec2Bin但核心思路稍微改一行就能变成任意进制转换。把取余和除的基数从 2 改成 8 就是八进制改成 16 就是十六进制。唯一多出来的是十六进制需要处理 10~15 对应的 A~F 字符这时栈里存的不再是整数而是字符或字符串结构体里的 data 类型要改成 char 数组。如果让你实现一个BaseConversion(int n, int r)函数输入十进制数和目标进制输出对应进制表示你会发现代码框架和 Dec2Bin 几乎一模一样。Dec2Bin 是理解通用进制转换的模板学一次就能通一片PTA 后续经常会有这种变形题。5.2 中缀表达式转后缀表达式同一个栈换个场景继续用栈的应用不止“反转”这一种。表达式求值里中缀表达式1 2 * 3转后缀表达式1 2 3 * 用到的也是栈但规则不再是简简单单的先入后出而是按运算符优先级动态决定入栈还是出栈。那个过程就比 Dec2Bin 复杂多了。但你要理解Dec2Bin 里熟悉的那套 Push/Pop/判空/判满基本功到表达式求值里一样要用。甚至可以说表达式求值的难度不是栈操作本身而是“什么时候入栈、什么时候出栈”的决策逻辑。先把 Dec2Bin 的栈操作练熟后面学表达式求值、括号匹配、迷宫求解至少代码层面不会慌。5.3 递归和栈本质上是一回事还有一个很有意思的观察角度十进制转二进制的递归写法极其简洁。递归版本大致是void Dec2BinRec(int n) { if (n 0) return; Dec2BinRec(n / 2); printf(%d, n % 2); }注意到没有递归本身也利用了系统调用栈的 LIFO 特性——先递进到最深层再在回溯时依次输出。递归的隐式调用栈和手写的显式栈原理完全一样。这也是为什么数据结构课上老师总说“递归转非递归时经常要引入栈”。如果你能把 Dec2Bin 的栈实现和递归实现放在一起对比对“程序运行时发生了什么”会有更具体的感受。最后聊几句我的实际操作体会我自己最开始做这道题的时候曾经因为 top 初始化从 1 开始而不是 -1导致入栈第一个数据存到了 data[1]输出时从 data[top] 开始读前一位变成随机值后一位又对不上。折腾了好一阵子才意识到是约定不一致。后来总结出一个办法每次写栈的代码前先在注释里写清楚 top 的含义比如“top 指向栈顶元素位置空栈时为 -1”。这一行注释后来帮我避开了无数低级错误。另外建议你在本地把 0、1、2、13 这样的小用例都跑一遍再提交。很多同学喜欢直接提交然后看评测反馈但 PTA 每次提交间隔和测试点反馈都有限自己本地跑一遍往往几秒钟就能发现问题比反复提交、猜评测结果高效得多。栈这个东西光看永远觉得抽象真正动手写完三道题心里就会踏实很多。