刚开始看到“行编辑程序——栈和队列”这个题目时我愣了几秒。三个词摆在一起栈是后进先出队列是先进先出规则完全相反硬塞进一个项目里总觉得有点拧巴。等真的把需求拆开把字符处理流程画出来我才发现这个组合一点都不牵强行编辑程序天生就需要“反悔”和“排队”两套机制栈负责给用户一条往回走的路队列负责让多行文本按顺序走完整个流程。这篇文章就从我实际动手做的版本出发把设计思路、核心代码、调试过程里踩过的坑都梳理一遍希望对正在啃数据结构、做类似练习的朋友有点用。这个项目并不复杂核心是做一个控制台下的行编辑工具用户逐行输入文本输入过程中支持退格、删行、多行保存。它解决的是“一边编辑一边回退同时还要保证多行文本不乱序”的问题。适合刚开始学栈和队列、想找一个小而完整的练手场景的人参考也适合准备课程设计或面试前想快速复习数据结构应用的人看一看。1. 行编辑程序到底在解决什么问题1.1 先拆标题三样东西各司其职“行编辑程序”听起来很古老其实它对应的是一类非常具体的工具你在一行里输入字符按回车确认这一行然后继续下一行。早年终端环境下的文本编辑器大多是这样的工作方式不像现在打开一个可视化编辑器就能满屏移动光标行编辑器的基本单位就是“行”。既然是逐行编辑就难免有输错的时候。最常见的两个需求很朴素一是输错了一个字希望退回去重打二是整行都乱了希望把这一行清空重新来。对应到数据结构上“退回重打”正好是栈的拿手好戏因为最近输入的字符应该最先被删掉“清空重来”也可以靠栈实现把栈整个清掉就行。那队列在哪用我设计的时候把“已经编辑完成的整行文本”放进队列里由程序按顺序取出来写入文件或者回显到屏幕。这样生产者和消费者可以不完全同步先完成的行先进队列后完成的行后进队列取出来时依然保持原来的顺序。一个项目同时用上两种结构并不是为了炫技而是它们分别承担了不同维度的职责一个是时间上的逆序回退一个是空间和时间上的顺序流转。1.2 需求清单与课本原型如果你翻过一些数据结构教材大概率见过这个经典原型从终端接收一串字符遇到#表示退格遇到表示删除当前整行遇到换行符\n表示这一行输入结束然后把这行写入文件。这是练习“栈的典型应用”时非常经典的一道题。我做这版项目时在这个基础上又加了一层需求多行输入时不能丢顺序而且最好能看到最近处理过的几行内容。这就引出了队列的作用。我整理了一份需求清单每一项都对应一个明确的数据结构选择需求数据结构原因输入普通字符存入当前行栈当前行内容是后进先出的编辑现场方便回退遇到#退格栈弹出栈顶元素正好删除最近一个字符遇到删除整行栈清空当前栈即可一行输入结束进入多行流水队列已完成的行按顺序入队保证落盘顺序回显最近若干行队列从队头向后遍历天然按时间顺序保存到文件队列从队头逐一取出先编辑的先写入这种拆法让整个程序的结构很清爽当前编辑行内部用栈已完成行之间用队列。很多人一开始会纠结“栈和队列能不能互替”其实在这个项目里它们根本不在同一个层级一个是单行内部的操作逻辑一个是多行之间的传输逻辑互替反而会让代码绕远路。2. 数据结构设计与核心原理2.1 栈为什么适合“退格”和“撤销”要理解栈在这个项目里的价值先得理解“行编辑时的撤销顺序”。用户输入字符的顺序是从左到右的比如先后输入了a、b、c那么屏幕上显示的是abc。如果发现最后一个字母c打错了要删掉它操作顺序是从右往左先删除c再删除b最后才轮到a。这是一种严格的“后进先出”关系。栈的接口恰好就长这样。入栈对应输入一个字符出栈对应退格一次栈的基本操作不需要任何额外判断就能还原用户的编辑路径。我最初也想过用数组加下标来做后来发现那就是拿数组手写栈不如直接用栈的语义去描述代码更直白测试时也更不容易出错。还有一个细节容易被忽略退格符号本身也是输入流里的字符。程序读到#时要把它当成“指令”而不是普通文本。这就是为什么不能在读到#时直接入栈必须单独判断。如果读到的字符既不是#也不是、\n才把它当作普通字符压栈。这个逻辑看起来简单却是我前期调试时最常出问题的地方。2.2 队列为什么适合“按顺序缓冲”队列的存在是为了处理“多行文本的流向”。假设用户连续输入了三行第一行是hello第二行是world第三行是done。这三行最终写入文件时必须保持hello、world、done的顺序不能因为写入时机不同而乱掉。如果不用队列而是一行编辑完立刻直接写文件看起来也没什么问题因为编辑完一行本来就可以立即落盘。但我这版程序里刻意做了一个“缓冲后再统一保存”的设计目的是模拟更真实的生产者消费者模型编辑行是一个生产速度不稳定的过程用户可能打一行停下来想半天也可能瞬间输入好几行而文件写入是一个相对独立的消费动作。用队列在中间承接生产端不用等消费端消费端也不用一次次打断编辑过程。队列的“先进先出”规则在这里就是刚需。先完成的行先入队后完成的行后入队从队头取出时自然先取出先完成的行。这个特性和栈的“后进先出”恰好互补一个负责挽回过去一个负责稳定未来。2.3 栈和队列的分工边界做这个项目时我给自己定了一条规则不在同一个环节里混用两种结构。怎么判断某个环节该用哪种我总结了一个很朴素的标准——如果处理顺序需要“逆着来”用栈如果处理顺序必须“顺着来”用队列如果既要逆序又要顺序那就把流程拆成两个阶段每个阶段用各自合适的结构。3. 核心实现一个能跑起来的行编辑器3.1 整体架构与运行流程我这版用 C 语言实现主要考虑是 C 对结构的控制更直接数组栈、循环队列写起来都不绕。整体流程可以概括为初始化一个字符栈用于保存当前正在编辑的一行。初始化一个行队列用于保存已经确认完成的若干行。程序循环读取用户输入的一个字符。如果是普通字符压入字符栈。如果是#检查栈是否为空非空则弹出栈顶。如果是清空整个字符栈。如果是\n把字符栈里的内容拼成一行按顺序取出所有字符组装成字符串然后让这行字符串入队。当用户输入结束指令比如CtrlZ或单独的保存指令时把队列里的所有行按顺序写入文件。这里有个关键点第 7 步从字符栈里取出字符拼成一行时不能改变字符原本的顺序。因为栈是后进先出直接弹出得到的字符串是倒序的所以要先全部弹到一个临时数组里再逆序组装或者用另一个栈倒一次手。这个“栈到队列之间的顺序转换”是整个程序里最容易出 bug 的地方之一。3.2 关键数据结构定义我用的是数组实现的顺序栈容量设为单行最大长度。为什么不直接用链表因为在这个场景里单行文本长度可控数组栈缓存友好代码也更短足够应付课程设计和日常练习。如果以后要处理无限长的行再改成链式栈也不迟。#define MAX_LINE 1024 #define MAX_QUEUE 256 typedef struct { char data[MAX_LINE]; int top; } CharStack;队列方面我用的是循环队列每个元素是一行字符串。注意队列容量要足够容纳“在落盘前积累的行数”如果同时编辑很多行又迟迟不保存队列满了就会丢数据。我预留了 256 个槽位实际使用时先做容量判断。typedef struct { char data[MAX_QUEUE][MAX_LINE]; int front; int rear; } LineQueue;这里的front指向队头rear指向下一个可写入位置。判空条件是front rear判满条件我用的是(rear 1) % MAX_QUEUE front也就是故意留一个空位来区分空和满。这个细节很重要否则很容易出现“队列明明满了看起来却像空队列”的诡异问题。3.3 处理普通字符、退格、删行的核心逻辑核心的字符处理函数可以写成下面这种形式。每次读一个字符根据字符类型决定是压栈、弹栈、清空栈还是结束当前行。void process_char(CharStack *stack, LineQueue *queue, char ch) { if (ch #) { if (stack-top 0) { stack-top--; } } else if (ch ) { stack-top -1; } else if (ch \n) { char line[MAX_LINE]; int len 0; while (stack-top 0) { line[len] stack-data[stack-top--]; } // 刚才得到的是倒序需要反转 for (int i 0; i len / 2; i) { char tmp line[i]; line[i] line[len - 1 - i]; line[len - 1 - i] tmp; } line[len] \0; enqueue_line(queue, line); } else { if (stack-top MAX_LINE - 1) { stack-top; stack-data[stack-top] ch; } } }这里特别说明一下为什么拼行时要反转。用户输入hello虽然表面上是从左到右但压栈后栈里从底到顶也是h、e、l、l、o。当回车时如果直接弹栈弹出的顺序是o、l、l、e、h这显然不是我们想要的字符串。所以要先弹出到临时数组再左右反转。我最初省略了反转步骤保存出来的文件全是倒序的第一次测试时看到olleh还以为是文件写入写反了调了半天才发现是栈语义没转过来。3.4 队列落盘与文件保存当队列里积累了已经编辑好的行就可以统一写入文件。这一步我放在主循环之外由用户输入一个保存指令触发这样可以控制落盘时机也避免了每输入一行就去写一次磁盘的低效操作。void save_queue_to_file(LineQueue *queue, const char *filename) { FILE *fp fopen(filename, w); if (fp NULL) { perror(open file failed); return; } while (!is_queue_empty(queue)) { char line[MAX_LINE]; dequeue_line(queue, line); fprintf(fp, %s\n, line); } fflush(fp); fclose(fp); }用fflush是有讲究的后面调试部分我会详细说。这里先强调一个容易忽略的点队列里保存的每一行字符串我都没有带换行符换行符是在写入文件时统一补上的。如果把换行符也存进队列后续处理字符串时就会遇到多余的空行或截断问题排查起来很费劲。3.5 单行编辑的扩展用栈模拟光标左右移动基础版做好之后我又顺手加了一个更像真实编辑器的功能用两个栈模拟光标左右移动。具体做法是把当前行拆成左右两个栈光标左侧的内容放在左栈光标右侧的内容放在右栈。按左方向键时把左栈栈顶字符弹出来压入右栈相当于光标左移按右方向键时把右栈栈顶字符弹出来压入左栈相当于光标右移。在光标位置输入字符时只往左栈压栈。删除键则分成两种情况如果要退格弹出左栈栈顶如果要删除光标右侧的字符弹出右栈栈顶。这个双栈模型在真实编辑器里很经典本质还是“编辑操作需要逆序回退”这一思想。栈和队列练熟之后再去理解编辑器底层实现会感觉很多概念是相通的。4. 调试阶段踩过的坑4.1#在空栈时的越界问题第一个坑非常基础如果用户在一行开头就连按退格栈顶可能是-1这时候直接执行top--会让数组下标变成负数程序直接崩溃。解决办法就是弹栈前先判断top 0。这个判断虽然简单但一开始很容易因为“想当然”而漏掉。我后来用的测试用例是连续输入###a预期结果是只输出a。实际调试时程序在第三个#处崩了才意识到空栈退格的问题。我把这类边界条件整理成一组小用例每次改完代码都跑一遍非常省心。4.2 队列判满与丢行问题队列部分我踩过一个比较隐蔽的坑用front rear同时判断空和满。第一次实现时我天真地以为只要判断front rear就能知道队满了结果写入 256 行之后就开始丢数据。原因很简单对于循环队列空和满都可能满足front rear必须借助“预留一个空位”或者“增加一个计数器”来区分。我选择了预留空位方案把实际可用容量变成MAX_QUEUE - 1。这样判满条件就比较可靠了。如果你的程序需要完全用满每一个槽位可以考虑在结构体里加一个count字段入队时count出队时count--用count 0判空、count MAX_QUEUE判满更直观一些。4.3 文件缓冲导致数据丢失最开始保存文件时我写完数据直接调fclose以为数据已经落盘了。测试时程序在保存过程中异常退出再打开文件发现一行都没写进去或者只写了后半部分。这是因为标准库的文件流有缓冲区数据还在内存缓冲里没有真正写到磁盘。解决办法是在写完数据后、关闭文件前显式调用fflush(fp)。如果是边写边观察日志类的场景还可以在每写完几行后就刷新一次这样即使程序中途挂了至少已经刷盘的部分不会丢。这个小细节在正式项目里关系到数据可靠性在练习项目里也值得养成习惯。4.4 Windows 换行带来的多余字符另一个让人头大的问题是换行符差异。在 Linux 下用\n结尾很干净但在 Windows 下文本模式打开文件时\n会变成\r\n落盘。我当时用一个在 Linux 下正常工作的版本换到 Windows 上编译运行保存出来的文件每行末尾多了一个\r用其他文本工具打开时总带着一个奇怪的符号。这不是栈和队列的问题但实际项目里遇到时很干扰调试。解决方法有两个方向一是统一使用二进制模式打开文件比如fopen(filename, wb)让\n保持原样二是在读取文本时过滤\r。具体选哪种要看目标平台。如果是跨平台项目更要在一开始就把这个问题纳入设计。4.5 超长输入行被静默截断单行缓冲区长度是 1024如果用户输入超过这个长度我的第一版实现选择直接忽略后续字符。这带来一个很隐蔽的问题用户看不到报错但保存出来的行少了一截而且很难排查。后来我改成“超长时向终端输出一行提示并丢弃超出的部分”至少让用户知道发生了什么。更完善的方案是动态扩容的栈一旦接近容量上限就自动增长。动态扩容需要处理内存重分配和拷贝作为练习项目来说是个很好的进阶题目但作为基础版本提示加截断已经足够。5. 项目扩展思路与个人复盘5.1 从行编辑器到真实编辑器的距离这个练习做完之后很容易产生一个疑问真实编辑器里是不是也是这么用栈和队列的其实真实编辑器更复杂但核心思想没有变。光标左侧和右侧用两个栈来维护就是 3.5 节提到的模型撤销历史用命令栈每执行一次操作就压栈撤销时弹栈需要重做时再用另一个栈接住弹出内容。我后来尝试给程序加了简单的撤销功能每次输入一个普通字符先把当前整行状态压入撤销栈撤销时把当前行弹出来再从撤销栈恢复上一行状态。这个版本虽然是“整行级撤销”但已经能感受到栈在编辑器撤销体系里的重要性。队列部分也可以扩展到命令队列把用户操作按顺序记录下来之后批量回放或者异步处理。5.2 栈和队列的选择在实际开发中的影响做这个项目之前我对栈和队列的认知停留在“一个后进先出一个先进先出背下来就行”。真正写代码时才发现数据结构的选择会直接影响程序的容错能力、扩展成本和调试难度。比如在行编辑场景里如果用数组直接实现“删除最近字符”你得记录当前光标位置删除后还要把后面的字符整体前移代码量明显更大而栈结构天然把“当前位置”隐藏在了栈顶接口很简单出错概率也低。队列也是如此如果没有队列而是用一个数组去存多行入队出队时就要频繁移动元素而且很难优雅地区分“空了”和“满了”。5.3 我的几点实操心得第一点数据结构练习千万别只看代码能跑。我第一版程序跑通后给室友A演示输入ab#cd能正确保存成acd输入abcdef也能保存成def。看起来没问题但如果我不用##、、空栈退格这些边界用例去压测根本发现不了数组越界和队列满的问题。做这类练习建议至少准备一组正常用例、一组边界用例、一组异常用例。第二点栈和队列的代码要分开封装不要揉在一起。我刚开始图省事直接在process_char里操作数组下标结果后面想加双栈光标移动时几乎重写了一遍。把栈的压入、弹出、判空、清空队列的入队、出队、判空、判满都封装成独立函数之后主流程读起来非常清爽测试时也能针对单个函数单独验证。第三点顺着“数据流向”去理解整个程序比死记结构定义有用得多。字符先进入当前行的栈一行确认后进入队列队列再进入文件整个流向非常清晰栈管“行内”队列管“行间”。理解了这个流向以后再看到“为什么这里要用栈”“为什么那里不能省队列”之类的问题基本不用多想就能判断。这套代码做完之后我又把它扩展成支持双栈光标移动和撤销历史的版本虽然还没到真正编辑器的程度但作为一个数据结构的综合练手项目覆盖的知识点已经很扎实了。如果你也在做类似的题目我建议不要急着把代码堆完交差多花点时间在边界测试和扩展改造上收获会大很多。
