栈与队列受限线性表的逻辑、存储与典型题型这一部分的核心不在于把代码模板一行不落地背下来而在于真正理解“受限”二字。栈和队列都属于线性表但它们不是对任意位置都开放操作的普通线性结构而是只允许在特定位置插入或删除数据。正因为这种限制它们在逻辑特征、存储设计和题目分析上都形成了鲜明规律。材料虽然以“栈、队列和数组”为章名展开但这一份内容实际重点落在栈与队列上数组更多体现在顺序存储、共享空间和循环数组这些具体组织方式之中。一、先把本质抓住它们都是“操作受限”的线性表栈只允许在同一端进行插入和删除因此这一端既是数据进入的位置也是数据离开的位置。栈顶是允许操作的一端栈底是相对固定的一端空栈则表示其中没有任何元素。由于后进入的数据总是先被取出栈的基本特征就是后进先出也就是 LIFO。围绕栈最基础的操作包括初始化、判空、入栈、出栈、读取栈顶元素以及销毁栈其中“读取栈顶”只读不删这一点经常和“出栈”混淆。队列则把插入和删除分散到两端进行。允许删除的一端叫队头也叫队首允许插入的一端叫队尾。这样的结构决定了最早进入队列的元素会最先离开因此队列体现的是先进先出也就是 FIFO。它的基本操作与栈类似也包括初始化、判空、入队、出队和读取队头元素但逻辑特征已经从“一端集中处理”变成了“两端分工处理”。真正理解这两种结构时最重要的一点不是记住术语而是意识到它们对线性表操作范围做了限制。也正因为有了这种限制栈特别适合表达“最近进入、最先处理”的过程队列特别适合表达“先到先服务、顺次推进”的过程。二、栈所有规律都围绕栈顶展开1. 栈的基本逻辑如果一个栈按顺序压入 (a_1,a_2,a_3,a_4,a_5)那么最先弹出的只能是 (a_5)随后才可能是 (a_4)、(a_3) 等元素。也就是说栈的出栈顺序不是任意的而是严格受入栈先后和栈顶位置约束的。凡是题目让你判断某个出栈序列是否合法本质上都在考察你是否真正理解“栈顶唯一可操作”这一点。2. 顺序栈用一组连续存储单元表示栈顺序栈本质上就是用数组来保存栈中元素再额外设置一个栈顶指针top来标识当前栈顶位置。材料中给出了最常见的一种约定初始化时令top-1表示当前没有任何元素入栈时先让top加一再把新元素放到data[top]出栈时先取出data[top]再让top减一。这样一来空栈条件是top-1栈满条件是topMaxSize-1栈长则可以表示为top1。这里有一个很容易被忽视的细节top的含义并不是固定不变的。有些教材把top直接定义为“栈顶元素所在位置”也有些教材把它定义为“栈顶元素的下一个可用位置”。两种设计都可以成立但对应的入栈、出栈、判空和判满写法会随之改变。因此做题时不能只背某个代码模板而要先判断题目中top到底代表什么再决定指针如何移动。顺序栈的优势是结构简单、实现直接、定位迅速栈顶相关操作通常都能在 (O(1)) 时间内完成。它的局限也很明确数组长度固定若最大空间估计不足就会发生真正的上溢若空间估计过大又可能带来浪费。3. 共享栈让两个栈共用一段数组空间共享栈是顺序存储思想的一个很典型的优化。它把两个栈放进同一个一维数组中一个从左向右增长另一个从右向左增长。这样设计的好处是两栈并不是各自死守一半空间而是可以根据实际需要动态“挤占”尚未使用的区域。只有当两个栈顶指针相邻时才说明整个共享空间已经用满。这种设计的价值在于提高空间利用率。若两个栈的使用强度不一致传统做法容易出现一边满、一边空的浪费而共享栈可以让它们自动调剂剩余空间。与此同时它在取数和存数效率上并没有明显下降相关操作仍可保持 (O(1)) 复杂度。4. 链栈把栈建立在链式存储之上当栈的元素个数变化较大或者事先很难估计最大容量时链栈就比顺序栈更自然。链栈通常用单链表实现并让头指针直接指向栈顶。这样一来入栈相当于把新结点插到链表表头出栈相当于删除表头结点。由于所有操作都发生在表头所以它同样可以把基本操作控制在 (O(1)) 时间内。链栈的优点在于不需要预先给定固定容量多个栈之间也更容易共享离散存储空间因此不会出现顺序栈那种“数组长度估计过大或过小”的尴尬。它的代价是每个结点都要额外存放指针域空间组织也没有数组那么紧凑。5. 栈最值得掌握的题型规律材料中把很多重点放在出栈序列分析上这也是栈最有代表性的考法。判断一组入栈、出栈操作是否合法可以抓住两个原则。第一个原则是在任何处理中间状态下出栈次数都不可能超过入栈次数因为栈不可能从空状态继续弹出元素。第二个原则是若题目要求整个操作结束后栈为空那么总入栈次数与总出栈次数必须相等。把入栈记为 (1)、出栈记为 (-1) 来观察前缀和往往会让判断变得更直观任何前缀和都不能小于零最终总和必须回到零。进一步地材料还指出(n) 个不同元素入栈后所有可能合法出栈序列的个数满足卡特兰数规律。这一结论不是为了让人死记公式而是提醒你栈的输出排列数量虽然很多但绝不是任意排列都能出现它背后有严格的组合约束。在综合应用中栈尤其适合处理“逆序比较”问题。材料给出的一个典型思路是把链表前半段元素依次入栈再与后半段逐一比较由此判断链表是否中心对称。这个过程之所以高效恰恰是因为栈能够把“前半段的顺序”自动转换成“从中间向两边回看的逆序”。三、队列所有规律都围绕队头与队尾的分工展开1. 队列的基本逻辑队列和栈一样都属于操作受限的线性表但限制方式不同。栈把插入和删除都限制在同一端队列则要求插入在队尾、删除在队头。这一差别直接决定了两者的行为风格栈偏向“最近优先”队列偏向“到达先后”。也正因为如此队列中的中间元素并不能被随意访问凡是试图跳过队头、直接取走中部元素的做法都违背了队列定义。2. 顺序队列问题不在定义而在空间回收顺序队列同样依赖一段连续存储空间只不过它需要两个指针front指向队头元素rear指向队尾元素的下一个位置。常见初始化方式是frontrear0。入队时把元素写入data[rear]后再让rear加一出队时先取data[front]再让front加一。当frontrear时队列为空。顺序队列最经典的问题是“假溢出”。假设队列前部已经有若干元素出队于是数组左侧出现空位如果此时rear已经移动到数组尾部按照普通顺序队列的定义就无法继续入队看起来像是“满了”但实际上数组前面还有可用空间。这不是存储空间真的耗尽而是因为rear只会向后移动、不会回头复用前部空位。也就是说顺序队列的难点不在于队头和队尾的定义而在于如何有效重复利用已经释放的存储单元。3. 循环队列用“逻辑成环”解决假溢出为了解决顺序队列不能复用前部空位的问题材料引入了循环队列。它并不是把物理存储真的变成圆形而是在逻辑上把数组首尾连接起来。当指针走到数组末端后再前进一步就自动回到零号位置这一过程通常通过取模运算来完成。于是队头和队尾都可以在数组中循环移动原本位于前部的空位也能重新投入使用。循环队列中队头和队尾的移动公式都很重要队头前进通常写作front(front1)%MaxSize队尾前进通常写作rear(rear1)%MaxSize。在这种定义下队列长度可以写成(rear-frontMaxSize)%MaxSize。真正的难点在于区分“空”和“满”因为若不加额外约束两种状态都可能出现frontrear。材料给出了三种常见处理方式。第一种是牺牲一个存储单元把“队尾指针的下一个位置就是队头”规定为队满标志因此队满条件写成(rear1)%MaxSizefront这也是最常见的做法。第二种是在结构中增设size成员直接记录当前元素个数。第三种是增设tag标志位用最近一次操作来区分“相等时到底是空还是满”。这三种方案都值得理解但考试和实际实现中最常见的还是“少用一个单元”的版本。4. 链队让队列更适合规模动态变化的场景链式队列本质上是一个同时维护队头指针和队尾指针的单链表。若不带头结点空队条件通常是frontNULL且rearNULL入队时把新结点接到表尾并更新rear出队时删除表头结点并让front后移。若删除后队列变空还必须把rear一并置空。可以看出不带头结点的链队在判空和边界处理上略显繁琐。因此材料更强调带头结点的链队。带头结点后初始化时让front和rear同时指向头结点空队条件可直接写成frontrear入队时始终在rear后插入新结点再更新rear出队时删除头结点之后的第一个真实数据结点。若删除前队列中只有一个数据结点删除后还需要让rear回到头结点位置。这样的设计使插入和删除逻辑更加统一也更适合编写稳定代码。链队最大的优势是特别适合数据规模波动较大的环境并且不存在顺序队列那种由于固定容量引发的溢出风险。如果系统中要同时维护多个队列链式方案往往也更灵活。5. 双端队列两端都能操作但约束决定能力边界双端队列允许在两端进行插入和删除因此它比普通队列更灵活。为了便于理解可以把左端看作前端、右端看作后端。无论从哪一端删除先被删掉的元素都会排在后删元素之前而从不同端插入时元素在队中的相对位置则由插入端共同决定。在此基础上材料又介绍了两种受限形式。输出受限的双端队列允许在两端插入但只允许在一端删除输入受限的双端队列允许在一端插入和删除而另一端只允许删除。这两种结构都比普通队列灵活又都比完全双端队列受到更多限制因此特别适合用来考查序列构造能力。做这类题时不必陷入抽象推理的迷雾。更有效的方法通常是直接模拟明确哪一端可以插入、哪一端可以删除然后跟着输入序列一步一步推导。材料最后也明确提醒实际考查时双端队列通常不会设计得过于复杂判断某个输出序列是否满足题设约束代入验证往往就足够了。四、这些地方最容易混淆第一读取栈顶元素和出栈不是一回事。前者只把当前栈顶值取出来观察后者会真正删除该元素并改变栈顶指针位置。若在题目里把两者混为一谈后续状态会全部算错。第二top、front、rear的含义必须结合具体定义理解。尤其在不同教材和题目中rear有时表示队尾元素有时表示队尾元素的下一个位置top也有“指向栈顶元素”与“指向下一个空位”两种解释。只有先判断指针语义才能写对判空、判满和移动顺序。第三顺序队列的“满”不一定是真满。看到rear到达数组尾部时要先想一想前面有没有已经释放的空间。如果还有空位却不能继续入队那不是空间真的耗尽而是普通顺序队列没有实现循环利用这正是循环队列要解决的问题。第四链式结构虽然避免了固定容量问题但边界处理比顺序结构更敏感。例如链队删除最后一个结点后若忘记同步修改尾指针就会留下悬空状态链栈和链队在判空条件上也不能直接照搬顺序存储版本。五、把这一章真正学会关键在于“画出指针怎么动”栈和队列之所以看起来概念多、写法多根本原因在于它们既有逻辑层面的限制又有存储层面的实现差别。真正把它们掌握下来不是机械背下若干函数名而是做到两件事其一明确它究竟限制了哪些操作因此具有什么序列规律其二能够在纸上画出指针如何移动因此知道每一步为什么成立。只要把这两件事想清楚顺序栈、共享栈、链栈、顺序队列、循环队列、链队和双端队列其实都会自然地串成一条线它们都是围绕“受限线性表”这一核心思想展开的不同实现与不同变体。六、常见问题