栈的经典应用：判断形如“序列1序列2”的镜像逆序序列

如果你在准备数据结构考试或者刷算法题，大概率会遇到这样一道经典题：识别一个以@结尾的字符序列，是否形如序列1&序列2的形式，其中序列2是序列1的逆序列。我第一次看到这个题目时觉得特别绕，明明每个字都懂，组合起来却不知道从哪下手。后来想明白了一个关键点——它本质上就是判断字符串是否以&为对称轴的镜像结构，而这恰好是栈这个数据结构最擅长的场景。

这篇文章会把题目拆开讲透，包括三个容易被忽略的约束条件、为什么栈是天然解法、完整代码实现、边界条件测试，以及如何把这个思路扩展到回文判断、括号匹配等更复杂的场景。不管你是刚学数据结构的学生，还是准备算法面试的开发者，都能从中拿到可以直接复用的思路和代码。

1. 先把题面翻译成人话：三个隐藏约束

1.1 核心结构：以&为轴的镜像匹配

题目给出的模式是序列1&序列2，要求序列1和序列2都不含&字符，并且序列2是序列1的逆序列。举个例子，a+b&b+a就是合法的，因为a+b倒过来是b+a，而中间的&正好把两个序列分隔开。

我刚开始接触这类题的时候，第一反应是"这不就是判断回文吗？"其实不完全一样。回文是正着读和倒着读完全相同，比如abcba，它以中间字符为中心左右对称；而这道题是以&为对称轴，左边和右边镜像对应。换句话说，如果序列1是c1 c2 c3 ... cn，那么序列2必须是cn ... c3 c2 c1，逐位对应相等，长度也必须完全一致。

这里还有一个容易忽略的细节：空串也参与讨论。如果输入是&@，序列1是空串，序列2也是空串，空串的逆序仍然是空串，所以按数学定义它属于合法模式。很多初写实现的人会把这种用例漏掉，后面我会在测试用例部分专门讲。

1.2 "依次读入"才是真正的限制条件

注意题目里的"依次读入"四个字，这是整个题目的灵魂。这意味着你不能先把完整字符串存下来再慢慢分析，必须在读入的过程中实时处理。打个比方，这就像你站在传送带旁边，零件一个一个送到你面前，你必须立刻决定怎么处理，不能等全部零件到齐后再回头检查。

为什么要强调这一点？因为如果允许先读入全部字符再判断，解法就太多了。你可以把整个字符串截成两段，把第二段反转后和第一段比较；也可以用双指针从两端向中间走。但"依次读入"这个约束把所有这些"事后处理"的路都堵死了。你必须在读到&之前，就把序列1的内容保存在某个地方；一旦读到&，后面每来一个字符，你都必须立刻判断它是否等于"应该出现的下一个逆序字符"。这个"先存起来，后拿出来比对"的过程，直接指向了栈这种数据结构。

1.3 @的真正角色：不是字符，是终止信号

最后一个隐藏约束是@。很多初学者会把@当成普通字符参与匹配，甚至把它压入栈中，导致最后栈里多出一个字符，怎么调都是错的。实际上@和&一样不参与业务比较，它扮演的是"输入结束标志"的角色，告诉程序：到此为止，请钩出结论。

处理@有两种常见方式。第一种是先把整行输入读进来，手动去掉末尾的@再走算法；第二种是在读入循环里遇到@就退出循环，然后根据当前状态给出判断。第二种更贴合原题"依次读入"的意图，我后面给的参考代码也是这个思路。核心口诀是：@只负责结束，不负责比较。

2. 为什么栈是天选之子：逆序匹配与后进先出

2.1 逆序是什么？就是"先进去，后出来"

拿一个日常场景来类比：假设你有一个窄口箱子，把书一本一本地放进去，然后一本一本地拿出来。拿出来的顺序会和放进去的顺序完全相反——最后放进去的那本最先被拿出来。这个过程就是栈的行为，专业说法叫"后进先出"。

题目要求序列2等于序列1的逆序，而栈弹出的天然顺序恰好是"后进先出"，两者正好咬合。不管你用什么样的序列1，只要按照从左到右的顺序把每个字符压入栈，之后在序列2部分遇到的每个字符，都只需要和栈顶弹出的字符比对一次。如果相等就继续，如果不相等就说明不是逆序列。整个匹配过程不需要回退，也不需要额外标记，逻辑天然闭合。

2.2 为什么不用数组反转或双指针？

有人会问：我用数组把序列1存下来，然后从后往前遍历，效果不是一样吗？确实一样，但前提是你需要知道序列1的长度，或者允许预先读入全部内容。在"依次读入"的限制下，你读到&的那一刻，并不清楚后面还有多长，也就是说你不知道这个数组应该多长才算完，也不知道什么时候该停。你当然可以用动态数组，但那本质上是在手动模拟栈。

再看双指针方案。双指针要求字符串可随机访问，也就是能通过下标直接跳到任意位置。但输入流是一个字符接一个字符地到来，根本没有"跳到任意位置"的渠道。所以栈在数据结构层面具备两个不可替代的优势：不需要预知长度，不需要随机访问。它只需要两个操作——压栈和弹栈，而这两个操作恰好都能在读入过程中即时完成。

2.3 时空复杂度与实现选择

每个字符只会被压栈一次、弹栈最多一次，因此时间复杂度和空间复杂度都是O(n)，n是序列1的长度。这个复杂度是所有线性解法的最优水平，没有多余的开销。

实现层面可以分三种：直接用语言自带的栈接口（如Python的列表、Java的Stack、C++的std::stack）；用数组模拟栈，自己维护栈顶指针；用链表模拟栈。实际刷题时我最推荐数组模拟，因为逻辑透明、不受栈接口细节干扰，也方便在调试时打印整个栈的内容。用数组模拟栈时，你只需要一个一维数组和一个整型变量top，压栈就是stack[++top] = ch，弹栈就是ch = stack[top--]，判断空栈就是top == -1。这套写法在各类数据结构题里通用，建议直接背下来。

3. 核心算法：状态机视角下的一次扫描

3.1 状态划分：读&之前和读&之后

整个算法可以看作一个两状态的状态机：

• 状态0，也就是读到&之前：每个非分隔符字符都压入栈中，作为序列1的"存档"。
• 状态1，也就是读到&之后：每个读到的字符都要和栈顶字符比对，比对一笔就弹栈一笔。

为什么要用状态变量而不是简单地在循环里判断"是否遇到过&"？因为这里还有一个隐藏问题：如果输入中出现两个&，比如a&b&c@，该怎么处理？按题目要求，序列1和序列2都不能含有&，所以第二个&出现时可以直接判定输入非法。用状态变量的话，读到&时先检查当前状态，如果已经是1，就说明出现了重复分隔符，直接返回失败；如果不是1，把状态切到1。这样状态转移的逻辑非常干净。

3.2 代码实现与逐行讲解

下面这个版本用类似C的伪代码，栈用数组模拟，翻译成其他语言也很容易。

int check() { char stack[MAX]; // 栈数组，MAX根据题目上限设置 int top = -1; // 栈顶指针，-1代表空栈 char ch; int status = 0; // 0 = 读序列1阶段, 1 = 读序列2阶段 while ((ch = getchar()) != '@') { if (ch == '\n') continue; // 忽略换行符，避免输入干扰 if (ch == '&') { if (status == 1) return 0; // 序列2中出现第二个&，直接非法 status = 1; // 切换到匹配阶段 } else { if (status == 0) { stack[++top] = ch; // 序列1的字符，压栈存档 } else { if (top < 0) return 0; // 栈已空但还有字符，说明序列2更长 if (stack[top] != ch) return 0; // 与栈顶不等，逆序匹配失败 top--; // 匹配成功，弹栈 } } } if (status == 0) return 0; // 整个输入中没出现&，不满足模式 if (top != -1) return 0; // 栈还没弹空，说明序列2比序列1短 return 1; }

这个代码有四个关键设计，值得单独说明：

第一，while ((ch = getchar()) != '@')先读后判，@只作为退出条件，完全不进入业务逻辑。这意味着输入a+b&b+a@时，读完最后一个a并匹配成功之后，下一次getchar读到@退出循环，此时栈恰好弹空，返回1。整个过程没有任何一个多余的判断。

第二，if (ch == '\n') continue;这行看起来不起眼，但我在本地调试时被它坑过一次。从键盘敲入字符后，输入流末尾通常跟着一个换行符，如果不过滤，\n会被当成普通字符参与压栈或比较，导致明明正确的输入被判定为失败。加上这行之后，无论你用命令行还是文件输入，结果都更稳定。

第三，读&时只改变status，不入栈，也不参与比较。这一步实际上是把&从有效字符里剔除掉了，序列1和序列2在比较时都不会碰到它。

第四，在stage1阶段读到一个非@字符时，如果栈已经空了，就立刻返回0，不需要继续往下读。这个提前返回既节省时间，也避免了访问空栈造成的数组越界问题。

3.3 为什么最后一定要双条件判断

循环结束后，两个条件缺一不可。

先看status == 0。如果输入是abc@，从头到尾没有出现过&，那就不存在"分隔符把序列分成两段"这件事，整个输入不满足模式要求。即使栈里存了一堆字符，也没有第二段来和它们做逆序匹配。

再看top != -1，对应的是输入ab&a@这种情况。序列1是ab，序列2只有一个a，弹出一个b之后栈里还剩一个b，说明右边比左边短，显然不是完整的逆序关系。只有"出现过&"和"栈恰好弹空"同时成立，才能说明左侧和右侧长度相同，且每一位都镜像相等，此时才算出完整匹配。

4. 边界条件与测试用例：把坑提前踩一遍

4.1 一张表覆盖所有常见情况

我在验证算法时整理了一张测试用例表，每种情况都有明确的预期结果。建议你写完代码后逐行跑一遍，这个习惯能帮你快速暴露隐藏问题。

其中&@这个用例最容易漏。按数学定义，空串的逆序是空串，所以它是合法输入。如果你在最后只判断"栈是否为空"，而忘了检查status == 1，这个用例就会被误判为失败；反过来如果你只判断status，而忘了检查栈空，ab&a@就会被误判为成功。所以最后两个条件必须同时存在。

4.2 换行符与输入格式：最容易被环境坑到的地方

如果你在本地命令行运行程序，从键盘输入ab&ba@再按回车，你以为程序只处理了8个字符，实际上getchar还会读到一个换行符。如果没有过滤逻辑，这个换行符在状态1阶段会被当成一个待匹配字符，而此时栈已经空了，程序立刻返回0——明明正确的输入被判成错误。

我第一次遇到这个问题时，还以为是算法逻辑写错了，花了不少时间排查。后来加了if (ch == '\n') continue;才解决。如果你用文件输入或者管道输入，也可能遇到末尾的\r（回车符）或空格，建议一并过滤。稳妥的做法是在循环开头加一个判断：只要当前字符是空白字符，就跳过不处理。当然，如果题目明确告诉你输入流里只有合法字符，不加也可以，但加了更稳健。

4.3 栈提前弹空意味着什么

在状态1阶段，如果读到一个非@字符但栈已经弹空，说明序列2的长度已经超过了序列1。比如a&ab@，序列1是a，序列2是ab，当你读到第二个a时，栈里唯一的a已经被弹掉了，此时再做任何比较都失去意义。直接返回0即可。

这个提前返回看起来是优化，实际上还是一种保护。用数组模拟栈时，top=-1之后再执行stack[top]就是访问数组的负下标，属于未定义行为，在不同环境下可能得到乱值甚至导致崩溃。所以每次弹栈前判断top < 0是必须的，这不仅是逻辑正确性的需要，也是程序安全性的保障。这个习惯在以后做任何栈相关算法题时都适用。

4.4 如何在本地快速测试

用一个循环把多个用例一次性跑完，比每次都手动敲键盘输入省事得多。我的做法是把测试用例写进一个文本文件，每一行放一个用例，程序从文件中逐行读取并输出判断结果。这样做的好处是，修改代码后可以立刻回归全部用例，确认新改动没有破坏旧的正确行为。

def is_valid(s: str) -> bool: # 去掉末尾的@，然后进入算法逻辑 s = s.rstrip('@') stack = [] status = 0 for ch in s: if ch == '&': if status == 1: return False status = 1 else: if status == 0: stack.append(ch) else: if not stack: return False if stack.pop() != ch: return False return status == 1 and len(stack) == 0 test_cases = [ ("a+b&b+a@", 1), ("ab&ba@", 1), ("abc&cba@", 1), ("&@", 1), ("ab@", 0), ("ab&a@", 0), ("a&ab@", 0), ("a&b&c@", 0), ("a&@", 0), ] for s, expected in test_cases: result = 1 if is_valid(s) else 0 print(f"{s}: {result} (expected {expected})")

Python版本的逻辑和C版本完全一致，只是利用了列表的append和pop方法来实现栈操作。如果想在文件模式下测试，只需要把test_cases换成从文件读取的列表，其他逻辑都不用改。

5. 从这一题延伸出去：回文判断、括号匹配与多分隔符

5.1 回文判断：同一套思路换个轴心

如果题目改成"判断一个字符串是否是回文"，比如abcba，表面看和本题很像，都是对称匹配。区别在哪？回文没有&分隔符，对称中心是一个字符或者两个字符之间的空隙，并不存在显式的分隔标记。

用栈解决回文判断，需要把字符串切成两半，前半段入栈，后半段弹栈比较。麻烦在于，这要求你事先知道字符串的总长度，否则不知道应该在什么位置停下。所以实际工程中大家更习惯用双指针：一个指针从头向右走，一个指针从尾向左走，逐个比较。这正好印证了我前面说的——双指针适合可随机访问的完整字符串，栈适合在线输入流。理解了&镜像匹配这道题，再看回文题就不会再混淆这两类方法了。

5.2 多个分隔符时的状态机扩展

如果题目扩展成序列1#序列2#序列3，其中每个序列都是前一个序列的逆序，栈的做法依然适用，但状态切换需要更精细的管理。你可以把状态改成三档：0代表读序列1，1代表读序列2，2代表读序列3。遇到第一个分隔符#时，从状态0切到1，之后的字符和栈顶比较并弹栈；遇到第二个分隔符#时，从状态1切到2，此时栈已经弹空，需要重新开始压入序列3的字符。

这种多个分隔符的场景在实际开发中很常见，比如解析配置文件、处理协议报文，分隔符就相当于语法标记。状态机的思想用在这里会比叠一堆if判断清晰很多。本质上，每多一个分隔符，就是在状态转移表里多加一列。

5.3 带通配符的不完全匹配版本

还有一类变体：允许序列2在部分位置用通配符?代替任意单个字符。比如ab&?b@，序列2的?可以匹配a，所以这个输入应该合法。改动很小，只需要把比较条件从"完全相等"改成"相等或其中一个是通配符"。

def match(a: str, b: str) -> bool: return a == b or a == '?' or b == '?'

再比如要求奇偶位匹配的变体，也就是只要求序列2在奇数位置与序列1的逆序相等。这种题需要在弹栈时增加一个计数器，记录当前已经匹配了几个字符，只有计数器的奇偶性满足条件时才执行比较。框架不变，加需求而已。这类题目反复出现，恰恰说明一个道理：栈的"逆序匹配"能力是底层骨架，各种花式题目都是在这个骨架上加约束条件。

最后分享一点我在教学和实际项目里的体会。栈这个结构看起来简单，但它的应用场景远比想象中广泛——从函数调用栈到浏览器后退按钮，从括号匹配到逆波兰表达式求值，背后都是同一句话："先发生的事后结束"。这道题最大的价值，不是让我们背下一个"入栈-弹栈-比较"的模板，而是训练一种翻译能力：把"逆序"翻译成"后进先出"，把"依次读入"翻译成"在线处理"，把"以@结束"翻译成"循环终止条件"。一旦习惯了这种翻译方式，以后再遇到任何对称匹配类的题目，第一反应就不会是迷茫，而是会自然地想：这里是不是可以用栈。如果你还在学习数据结构，建议亲手把上面的代码打一遍，再把测试用例表逐行验证，踩过一遍坑之后，你对栈的理解会比看十遍概念都扎实。