★ FEATURED ARTICLE 当我在整理NOIP2012初赛题的时候第一次看到“新壳栈”这三个字。第一反应是这不就是给栈换了个名字吗直到把题目给出的存储模型读完才发现它考察的其实是一种“双端栈”——两个栈底分别固定在数组两端、栈顶向中间生长的栈共享同一块连续内存空间。这个结构在初赛阅读题和“完善程序”题里非常经典也特别喜欢用来当考点集中营数组下标、指针移动、判空判满、边界重叠全都能塞进去。本文就从这道题出发把新壳栈的存储布局、四类核心操作、判满判空的边界条件拆开揉碎再聊聊它在现代算法里的延伸形态。不管你是正在备战NOIP初赛的选手还是想把栈和数组的关系彻底弄明白的同学这篇文章应该能帮你少走不少弯路。1. “新壳栈”到底在考什么先别把它当成普通栈1.1 初见题名容易误判方向“新壳栈”这个叫法很有迷惑性。很多选手第一眼看到它脑海里浮现的是普通栈的经典画面一个数组一个栈顶指针从某一端压入和弹出。但读完题目给出的操作说明才发现这里要维护的是两个方向相反的栈而且它们居然共用同一个数组“外壳”。于是问题就来了一个数组怎么同时装下两个栈如果左边的栈向右生长、右边的栈向左生长那它们最终会不会撞在一起撞在一起之后到底算满还是算空这一连串问题恰恰就是新壳栈题目的核心考察点。在初赛笔试题的背景下题目不会要求你写一个完整可运行的工程代码而是给你一个经过简化的数据结构模型然后让你做三件事手工模拟若干次操作、判断某个条件下指针的位置、或者补全一段残缺的代码。新壳栈最典型的形态是这样的设数组大小为 N下标从 0 到 N-1左栈的栈底固定在 data[0]右栈的栈底固定在 data[N-1]左栈的栈顶指针 leftTop 从 -1 开始向右移动右栈的栈顶指针 rightTop 从 N 开始向左移动。两个栈共用同一段数组空间谁也不能越界。这个模型在数据结构教材里通常被称为“双栈共享空间”竞赛题目则给它起了个更生动的名字——“新壳栈”。提示初赛阶段碰到陌生数据结构先别急着套模板把题目给出的存储布局画在草稿纸上往往比直接盯代码更有效。1.2 考点并不超纲核心是栈的物理存储为什么NOIP初赛要拿这样一个看起来有点“怪”的结构出题因为教材里讲栈的时候通常默认用一段连续空间存数据栈顶指针负责维护“当前栈顶在哪”。这种实现方式本身没问题但放在实际应用里有个很尴尬的场景如果你需要在程序里同时维护两个栈并且每个栈的数据量是动态变化的你会怎么分配空间最朴素的想法是直接把数组一分为二前半段给左栈后半段给右栈。假如左栈数据爆炸、右栈数据很少左栈很快就溢出了右栈这边却空着大片区域空间利用率极低。双栈共享空间就是针对这个问题的经典优化把两个栈的栈底放在数组两端让它们向中间“对向生长”。这样一来只有当两个栈的元素总数达到 N 时数组才会真正存满。换句话说只要左右两栈加起来的元素不超过数组容量任何一个栈都能继续压入不会被预先划定的“领地”限制住。对参赛者而言这道题考察的并不是让你发明新的数据结构而是你能不能把一个数组当作两个栈的公共存储介质并且准确维护两个方向相反的栈顶指针。题目里常见的操作无非是 pushL、popL、pushR、popR 四类偶尔还会加一个“查询某端栈顶元素”的变体。表面上看这些操作和普通栈的 push、pop 没什么区别但细节在于两个指针的移动方向完全相反而且判满的条件不是看某一个栈的长度而是看两个栈的总长度。这个“总长度”意识恰恰是新壳栈题目里最容易出错的地方。2. 双端栈共享空间的实现推演每一步操作都算清楚2.1 存储布局与两个栈顶指针先约定一种最常见的实现方式。数组下标从 0 到 N-1左栈的栈底固定在 data[0]右栈的栈底固定在 data[N-1]。用 leftTop 表示左栈当前栈顶元素的下标用 rightTop 表示右栈当前栈顶元素的下标。初始状态下左栈是空的leftTop -1右栈也是空的rightTop N。请注意rightTop 初始值不是 N-1而是 N因为右栈还没有任何元素它的“下一个可压入位置”应该是最右端再往左一个也就是从 N-1 开始。这里如果用 N-1 初始化就会导致压入第一个元素时把 data[N-1] 覆盖成新元素逻辑上并不算错但边界判断会变得很别扭。下面给出一个标准的 C 框架const int N 100005; int data[N]; int leftTop -1; int rightTop N; bool emptyL() { return leftTop -1; } bool emptyR() { return rightTop N; } bool full() { return leftTop 1 rightTop; }这个 full() 函数是整个结构最微妙的地方。它判断的不是 leftTop rightTop而是 leftTop 1 rightTop。为什么因为左栈实际占用的区间是 [0, leftTop]右栈实际占用的区间是 [rightTop, N-1]。当数组满的时候左右两栈已经把中间的空隙填完了此时 leftTop 和 rightTop 应该相邻也就是 leftTop 指向的位置和 rightTop 指向的位置之间没有空位。用公式表达就是 leftTop 1 rightTop。如果写成 leftTop rightTop那意味着同一个下标被左栈和右栈同时占用这在物理上已经越界了属于错误状态。很多阅读题专门在这个判断上做文章选项里会同时出现这两种写法就看你有没有想清楚指针的语义。2.2 四个基本操作的完整实现确定了存储布局四个操作就顺理成章了。左栈压入时先把 leftTop 向右移动一位再把值写进新位置void pushL(int x) { if (full()) { // 栈满无法压入 return; } data[leftTop] x; }右栈压入时指针移动方向相反是向左移动void pushR(int x) { if (full()) { return; } data[--rightTop] x; }左栈弹出时取出当前 leftTop 指向的元素然后把 leftTop 向左回退一位int popL() { if (emptyL()) { // 栈空无法弹出 return -1; } return data[leftTop--]; }右栈弹出时取出 rightTop 指向的元素然后 rightTop 向右回退一位int popR() { if (emptyR()) { return -1; } return data[rightTop]; }看到这里你可能觉得这跟普通栈实现没什么两样。对思路确实完全一致唯一要记住的就是右栈的指针运动和左栈镜像对称。真正容易出问题的不是代码本身而是在纸笔模拟时连续执行一长串操作之后你还能不能准确说出每个位置上的值、每个指针到底指向哪里。2.3 手工模拟实例一轮操作看指针变化纸上谈兵不如手算一遍。假设 N 6也就是 data[0] 到 data[5] 共 6 个位置。初始时 leftTop -1rightTop 6。执行下面这一组操作pushL(1)pushR(2)pushL(3)pushR(4)popL()popR()pushL(5)我们一步步看。初始状态数组下标 0 到 5 全部为空。leftTop -1rightTop 6。pushL(1)leftTop 变 0data[0] 1。此时数组为 [1, -, -, -, -, -]。leftTop 0rightTop 6。pushR(2)rightTop 变 5data[5] 2。数组为 [1, -, -, -, -, 2]。leftTop 0rightTop 5。pushL(3)leftTop 变 1data[1] 3。数组为 [1, 3, -, -, -, 2]。leftTop 1rightTop 5。pushR(4)rightTop 变 4data[4] 4。数组为 [1, 3, -, -, 4, 2]。leftTop 1rightTop 4。popL()弹出 data[leftTop] data[1] 3leftTop 变 0。数组为 [1, -, -, -, 4, 2]。leftTop 0rightTop 4。popR()弹出 data[rightTop] data[4] 4rightTop 变 5。数组为 [1, -, -, -, -, 2]。leftTop 0rightTop 5。pushL(5)leftTop 变 1data[1] 5。数组为 [1, 5, -, -, -, 2]。leftTop 1rightTop 5。注意此时中间下标 2、3、4 仍然是空的leftTop 1rightTop 5两者之间隔了 2、3、4 三个空位。为什么 rightTop 5 却还有空位因为右栈当前只有 data[5] 一个元素它的下一个压入位置是 4也就是 rightTop - 1。而 data[4] 刚才被弹出后并没有被“清空”只是不再属于任何栈。这里有一个关键认知物理数组里的残留值不影响逻辑正确性我们只通过指针来界定哪些位置属于左栈、哪些位置属于右栈。这个例子想说明的是双栈共享空间的“满”不是看单个栈的长度而是看两个栈的总元素数。假设 N 6即使左栈只有 1 个元素右栈却有 5 个元素总数到 6数组就满了此时再执行 pushL 或 pushR 都会失败。初赛题特别喜欢在这个地方埋坑比如给你一个数组当前状态问你还能不能压入如果你只盯着其中一个栈的长度很容易掉进去。提示笔试模拟时每执行一步就在数组上方标出 leftTop 和 rightTop 的位置能避免一半以上的低级错误。3. 边界条件与易错点阅读程序题的常见埋雷位置3.1 满栈判断的歧义leftTop 1 rightTop 还是 leftTop rightTop我在前面已经强调了 full() 的写法但这里值得再展开说因为这是新壳栈题目的“高频考点”。很多选手会把 leftTop rightTop 当作满栈条件这其实是受了普通栈“top 数组长度”这种思维的影响。在新壳栈里leftTop 和 rightTop 分别表示“左栈栈顶元素下标”和“右栈栈顶元素下标”。当 leftTop rightTop 时数组中间只剩下一个空位但左栈的栈顶和右栈的栈顶都指向同一个位置这代表什么代表那个位置上既有左栈元素又有右栈元素这显然是逻辑错误状态。真正合法的满状态是左右两栈的边界紧挨着即 leftTop 1 rightTop此时数组里没有空闲位置两个栈也互不侵犯。还有一种边界写法是判断 leftTop rightTop - 1效果一样。在完善程序题里出题人经常在 this 位置挖空让你选择正确的判满表达式。我的建议是不要背公式而是从“区间”的角度理解。左栈区间是 [0, leftTop]右栈区间是 [rightTop, N-1]当这两个区间之间没有空隙时数组满等价于 leftTop 1 rightTop。3.2 元素搬移与“扩容”数组满了之后怎么办初赛题目偶尔会进一步追问如果数组满了还有一个元素需要压入怎么办或者反过来能不能通过某种方式腾出空间这就涉及到元素搬移也就是“扩容策略”的雏形。一种最简单的方案是把整个数组扩大一倍把旧数据复制过去。但初赛代码通常不会真的开新数组因为它考察的是你在固定数组里“挪”数据的思路。常见的做法是如果左栈元素比较多就整体向右搬动左栈元素腾出左侧空间作为新的空隙如果右栈元素比较多就整体向左搬动右栈元素腾出右侧空间。搬移的目的是让中间的空隙向某一侧集中这样另一侧就能获得新的可压入空间。举个例子假设数组长度为 8当前左栈占了 data[0] 和 data[1]右栈占了 data[5]、data[6]、data[7]中间空闲的是 data[2]、data[3]、data[4]。现在左栈又要压入一个新元素但 leftTop 1 2rightTop 5中间还有空位所以仍然可以压入不需要搬移。但如果数组状态是左栈占了 data[0] 到 data[3]右栈占了 data[4] 到 data[7]这时 leftTop 3rightTop 4数组已经满了。此时再压入就必须搬移。如果把右栈整体向右搬结果会变成左栈 data[0] 到 data[3]中间 data[4] 空出来右栈 data[5] 到 data[7]。虽然浪费了 data[4] 这个空隙但至少腾出了一个位置而且搬移过程中必须保证左右两栈的相对顺序不变。这类搬移逻辑在“完善程序”题里很常见出题人会在循环边界上挖空让你补全从哪个下标搬到哪个下标。我的经验是碰到搬移题先在草稿纸上画出搬移前和搬移后的两个数组状态用箭头标出每个元素的移动方向然后再去对照代码里的循环变量这样可以避免搞错移动顺序。3.3 三个容易错的手工模拟场景我在带学生刷题时总结了三个高频错误场景这里列出来供你自查。第一个是“同侧压入直到满”连续向左侧压入 N 个元素左栈占满整个数组leftTop N-1rightTop N。此时 rightTop 其实还等于初始值 N右栈为空。如果此时执行 pushL判断 full() 会发现 leftTop 1 rightTop也就是 N N确实满了于是压入失败。但如果执行 pushR由于 rightTop 还是 NemptyR() 为真无法弹出但压入倒是可以注意full() 为真时任何压入都会失败所以 pushR 同样失败。这个场景说明即使一个栈是空的只要另一个栈占满了全部空间整个双栈系统依然处于满状态。第二个是“多次弹出后栈空但继续弹出”假设左栈有三个元素连续 popL 三次后 leftTop 回到 -1。第四次 popL 时 emptyL() 为真于是判 underflow。很多同学在模拟到第四步时会不自觉地把 leftTop 减成 -2这就是没有在操作前判空的后果。一个健壮的结构必须在每次弹出前检查空状态而不是等指针已经越界才去补救。第三个是“交替操作导致中间出现空洞”比如先压入左栈两个元素再压入右栈三个元素然后弹出左栈一个元素。此时左栈区间和右栈区间之间会出现一个空洞空洞里的残留值是之前压入后被弹出的旧数据。在某些变体题目里出题人会在空洞中故意保留旧值然后问“数组中某个位置的值为多少”如果不小心把空洞中的旧值当成有效数据就会算错。记住在栈结构里一个位置是否有效取决于它是否落在 [0, leftTop] 或 [rightTop, N-1] 这两个区间内而不是看它是否非空。4. 从初赛到实战新壳栈思维在算法题中的延伸4.1 现代形态环形缓冲区与双端队列新壳栈看起来像是初赛专用模型但它背后“两端操作 共享空间”的思想在现代软件开发里无处不在。最典型的例子就是环形缓冲区Ring Buffer它在音频采集、网络收发、日志写入等场景里被广泛使用。环形缓冲区的核心是一个定长数组和头尾两个指针写入数据时尾指针前进读取数据时头指针前进。当两个指针相遇时缓冲区要么满、要么空具体取决于你采用的策略。这和双栈共享空间里“两个指针从两端向中间生长”的模型本质上是同一类思维用指针去界定数据的有效边界而不是每操作一次就搬一次数据。再比如 C STL 里的 deque双端队列它支持 push_back、push_front、pop_back、pop_front 四种操作和前面提到的 pushL、pushR、popL、popR 一一对应。deque 的内部实现通常采用分段连续空间加上一个中控器每一段空间本身是连续的段与段之间通过指针连接。虽然它不一定共享一个数组但对外表现的“两端都可操作”的语义和新壳栈完全一致。如果你能把新壳栈的四类操作练熟再去理解 deque 的接口和复杂度会顺畅很多。4.2 可反转栈的懒惰标记新壳栈还有一种在竞赛里更实用的变体支持反转Reverse操作的栈。假设一个普通栈除了 push 和 pop 之外还有一个 reverse 操作每次 reverse 会把栈内元素顺序倒过来。如果每次都真的把数组里的元素逐个搬移一次 reverse 的代价是 O(N)在频繁反转的场景下会非常慢。经典解法是维护两个栈顶指针分别指向当前“逻辑栈底”和“逻辑栈顶”反转时只需要交换左右两个指针的角色并不需要真正移动数据。这就是所谓“懒惰标记”或者“翻转标记”。具体来说你可以维护一个布尔变量 rev表示当前栈是否处于反转状态。压入时如果 rev 为 false就在右端压入如果 rev 为 true就在左端压入。弹出时也按照同样的逻辑判断该从哪端弹出。每次 reverse 操作只需要把 rev 取反复杂度 O(1)。这个技巧在很多字符串处理题、编辑器模拟题里都会用到。它和新壳栈的关系也很直接新壳栈本来就是双端可操作的天然适合承载懒惰反转。4.3 复杂度与适用场景对比为了帮你把新壳栈放进整个数据结构体系里看我做了一张对比表结构支持的操作单次操作复杂度空间利用特点典型场景普通栈单数组push、popO(1)只能单端生长空间固定括号匹配、表达式求值、递归模拟双栈共享数组新壳栈pushL、popL、pushR、popRO(1)两个栈共享空间总容量用尽才算满两栈动态分配、初赛模型题环形缓冲区头尾读写O(1)定长复用指针绕回音频流、日志、生产者消费者双端队列dequepush_front、push_back、pop_front、pop_backO(1)分段连续空间支持扩容滑动窗口、双向搜索、编辑操作带反转标记的双端栈push、pop、reverseO(1)同双栈共享空间编辑器撤销重做、字符串变换这张表想说明的是新壳栈不是一个孤立的偏题怪题它在空间复用、双端操作、指针边界处理这三个方面和许多高级数据结构是相通的。掌握了新壳栈的推演方式后面学环形缓冲区、学 deque、学懒惰标记都会轻松不少。4.4 一道延伸思维题如何用新壳栈实现文本编辑器的光标操作最后留一个值得自己推演的思考方向。假设你维护一段文本文本被光标分成左右两半光标左边的字符存在左栈里光标右边的字符存在右栈里但两栈的栈顶都朝向光标。当敲入一个字符时相当于在光标位置插入也就是往左栈压入一个字符当按退格键时相当于从左栈弹出一个字符当按方向键左移光标时相当于从左栈弹出一个字符然后压入右栈当方向键右移光标时相当于从右栈弹出一个字符然后压入左栈。你会发现这个模型完全就是新壳栈的双端操作而且任何一步操作都是 O(1)。文本编辑器的“光标移动插入删除”问题用这个思路可以实现得非常优雅。这也解释了为什么很多算法题喜欢用“双栈模拟编辑器”本质上就是新壳栈的应用。5. 备考NOIP初赛的一点个人经验新壳栈这类题目在初赛里并不是为了难倒你而是为了考察你是否真正理解了栈的本质它只不过是一段连续空间加上一个边界指针。所谓“新壳”就是把这段连续空间从“一个栈用”变成“两个栈共用”把边界从一个变成两个。理解了这一层后面所有指针操作都能推导出来。我自己在刷这类题时有一个习惯拿到题目先不看选项也不急着读代码而是先用几分钟把题目描述的数据结构画成图。画什么画数组的下标方向画两个指针的初始位置然后用箭头标出每次操作后指针的运动方向。等到指针的运动规律完全清晰了再去阅读代码基本一眼就能看出哪个地方是正确选项、哪个地方是干扰项。另外做手工模拟题时我强烈建议你在草稿纸上列一张表每执行一步操作就记录当前操作leftTop 的新值rightTop 的新值数组关键位置的变化。只要这张表能一路保持整洁不涂改你的模拟过程就稳定了。很多选手在考场上不是不会而是草稿纸太乱把自己绕进去。初赛的时间比较充裕慢一点、写清楚一点远比追求速度划算。还有一个实战细节如果你的省份初赛采用笔试方式记得带好直尺和铅笔。画数组格子的时候用直尺比着画能让你在操作多轮之后依然看清楚每个位置对应哪个下标。当年我就是靠这个笨办法把双栈共享空间这类题目从易错题变成了送分题。最后再分享一个小技巧。如果你在完善程序题里遇到“判断空栈”和“判断满栈”两个空可以先判断哪个空的位置靠前然后反向推导。出题人通常会把最基础的操作放在前面把容易混淆的边界判断放在后面。你先把前面已经补全的部分当作已知条件代入数据跑一遍往往就能推出后面空格的正确写法。这个技巧不局限于新壳栈对所有完善程序题都通用。新壳栈看着陌生拆开之后就是老朋友一个数组、两个指针仅此而已。把它的逻辑彻底吃透你收获的不只是一道题的正确解法更是一种用“指针界定边界”的底层思维。这份思维在后续刷题和工程实践中比题目本身值钱得多。
阅读完成 · 觉得有帮助？
