每年GESP六级成绩出来之后总会有同学来问我类似的问题“栈和队列看着很简单代码也能默写为什么一到考试就是做不对”这个困惑我特别理解。六级考纲里数据结构部分的核心就那么几个线性表、栈、队列、树和图。栈与队列看起来结构最简单但它恰恰是区分“会写”和“会做”的分界线。原因很简单栈和队列本身的知识点不多但考试从来不直接考“栈是什么”“队列有哪几种操作”——而是把栈和队列当作工具藏在括号匹配、表达式求值、广搜、单调队列这类场景里让你自己判断该用哪种结构、怎么用、边界怎么处理。换句话说栈与队列是六级考试里性价比最高的内容也是丢分最隐蔽的内容。这篇文章我把六级考纲里栈与队列相关的知识点全部拆开从底层原理到数组模拟实现再到经典应用场景、常见陷阱和综合例题一次性捋清楚。不管你现在是刚学完栈和队列想巩固还是马上要考六级想突击这篇都可以直接当复习提纲用。1. 先搞清楚考纲到底要求什么1.1 栈与队列在六级中的定位GESP六级的大纲里栈与队列属于“数据结构”模块。如果你去看官方给出的知识点描述会发现它只列了几个条目栈的基本概念与操作、队列的基本概念与操作、栈与队列的典型应用。每条看起来都很简单但六级考试的题目不会只停留在概念层面。具体来说六级对栈与队列的要求可以拆成三层第一层理解栈和队列的逻辑结构知道它们的操作规则。栈是后进先出队列是先进先出。第二层掌握两种常见实现方式。一是用数组模拟二是用STL容器实现。考试机试环境下数组模拟和STL都得会写。第三层能在具体题目中识别出该用栈还是队列并写出正确的代码。这就要求你不但懂原理还要见过足够多的应用场景。很多同学备考时只盯着第一层觉得“栈和队列我会了”结果一碰到单调栈、循环队列这类变形就傻眼。六级真正考察的恰恰是第二层和第三层。1.2 官方大纲关键词逐条解读大纲里涉及栈与队列的关键词我按自己的理解给你逐条过一遍顺便标注考试中常见的考察方式。第一个关键词是“栈”。基础考察方式是给出一系列的入栈、出栈操作问你某个时刻栈顶元素是什么或者某个元素能否在某个顺序下出栈。这种题考察的是逻辑不涉及代码。第二个关键词是“队列”。基础考察方式是循环队列的队头、队尾指针变化判断队空、队满的条件。六级考试特别喜欢在这里设陷阱因为普通队列和循环队列的判空判满条件不一样。第三个关键词是“典型应用”。这里就开阔了。栈的典型应用包括括号匹配、表达式求值、函数调用模拟、单调栈找最近更大/更小元素。队列的典型应用包括广度优先搜索、单调队列求滑动窗口最值、约瑟夫问题、任务调度模拟。六级的大题、压轴题基本就从这些场景里出。如果你对照考纲再看这篇文章就会发现我下面的内容不是“额外加餐”而就是大纲要求的展开。这也是我写这篇长文的原因——大纲太抽象你需要有人帮你把它翻译成具体的、可执行的复习内容。2. 栈的底层原理与三种实现方式2.1 栈的本质后进先出栈的逻辑结构特别简单你只需要记住一个字“顶”。所有操作都发生在栈顶不能从中间插入也不能从中间删除。入栈是压到栈顶上出栈是把栈顶弹出去。我用一个生活场景帮你建立直觉假如你往一个窄口的箱子里依次放三本书A书先放进去B书放在A上面C书最后放进去。这时候你想把A书拿出来必须先把C和B都拿出来。这个“最后放进去的反而最先拿出来”的过程就是后进先出。在C里栈的核心操作就五个push(x)把x压入栈顶pop()弹出栈顶元素top()读取栈顶元素不弹出empty()判断栈是否为空size()返回栈中元素个数这里有个特别容易混淆的点就是top()和pop()的区别。top()是看一眼栈顶是谁栈本身没变化pop()是把栈顶拿掉栈变小了。很多初学代码的同学写循环取元素时先pop再top结果就会报错或者漏掉元素。后面我会给一个标准模板。2.2 数组模拟栈虽然STL里有现成的stack但六级考试你是可以手写栈的而且手写栈在一些场合更快更灵活。数组模拟栈的核心思想是用一个大数组存数据用一个整型变量topIndex记录当前栈顶的位置。const int MAXN 100005; int stackArr[MAXN]; int topIndex 0; // 约定topIndex表示下一个入栈元素的下标栈顶元素是stackArr[topIndex - 1] void push(int x) { stackArr[topIndex] x; } void pop() { if (topIndex 0) topIndex--; } int top() { return stackArr[topIndex - 1]; } bool empty() { return topIndex 0; }注意这里我把topIndex初始化为0入栈时先赋值后自增这样设计的目的是让“栈顶元素”永远是stackArr[topIndex-1]。这个约定用顺手之后pop和top的代码都不需要特判栈内是否有元素只要调用前保证不为空就行。数组模拟栈最大的好处是可控。你可以直接访问底层数组的任意位置这在做单调栈这类题目时非常必要因为你需要读取栈顶下方元素的下标。还有一个好处是内存连续运行效率比STL的stack稍高一点虽然在六级数据规模下两者差距几乎感觉不到。2.3 链表栈链表栈就是用单链表实现栈。我之所以单独提一嘴是因为六级笔试或者机试里有时会在判断题里出现相关概念。链表栈的思想是头结点作为栈顶。入栈就在头部插入一个新节点出栈就删掉头结点后面的第一个节点。这样所有操作的时间复杂度仍然是O(1)。链表栈的优势是不用提前分配空间内存动态增长适合不确定数据规模的情况。但六级考试当中不建议你实际用链表栈解题。理由有三个第一代码量比数组版大得多写起来容易出错第二每个节点需要额外存指针内存开销大第三动态分配和释放节点在循环里频繁执行容易出问题。真正考试时数组模拟栈永远是首选。2.4 STL stack实战用法C STL的stack用起来非常简单包含头文件后直接声明即可。它的用法和数组模拟栈完全对应只是你不用管底层怎么实现。#include iostream #include stack using namespace std; int main() { stackint s; for (int i 1; i 3; i) s.push(i); while (!s.empty()) { cout s.top() ; s.pop(); } // 输出3 2 1 return 0; }上面这段代码是stack的标准遍历模板。你注意一下这个循环的顺序先取top再pop。这个顺序绝对不能反过来因为先pop的话栈顶元素就丢了你再top就拿到了下一个元素。STL stack的底层容器默认是deque这在绝大多数场景下没有问题。这里有个小细节如果你想追求更高的性能可以用vector作为底层容器写法是stackint, vectorint s;。不过六级题目的数据规模通常不会大到需要你为此优化所以默认写法就够用。2.5 三种实现的选择策略我把三种方式做一个小结方便你复习时对照实现方式核心操作复杂度代码量推荐场景数组模拟O(1)少考试主推尤其单调栈链表实现O(1)多学习原理用考试不推荐STL stackO(1)最少常规题、快速开发也就是说只有当题目明确要求实现“栈的基本操作”时你才需要考虑手写完整结构一旦题目是“用栈解决某问题”我的建议是优先用STL。但如果你对数组模拟足够熟练直接用数组模拟也是一种非常稳的选择——毕竟栈的代码那么短写错的可能性不高还能顺带解决一些需要访问栈底下元素的场景。3. 队列的底层原理与实现3.1 队列的本质先进先出队列的逻辑结构也特别简单你只需要记住一个字“队”。入队发生在队尾出队发生在队头。先来的先走后来的排队等待这就是先进先出。生活场景更好理解你在食堂排队打饭排在前面的人先打到饭走了排在后面的人只能慢慢往前挪谁先到谁先走谁都不能插队。这个结构在程序里几乎无处不在——操作系统里进程的排队、打印任务的排队、网络里数据包的转发调度用的都是队列的思想。C里队列的核心操作和栈很像但名字有区别千万别记混push(x)把x入队放到队尾pop()把队头元素出队front()读取队头元素back()读取队尾元素empty()判断队列是否为空size()返回队列中元素个数对比一下你会发现队列多了一个back()操作而且读取队头的函数叫front()而不是top()。这是初学者最容易弄混的地方。另一个容易弄混的是STL queue的出队操作也是pop()它不是从队尾弹出而是从队头弹出。一定要把front()和pop()连在一起用先看front再pop弹出的是最老的那个元素。3.2 数组循环队列用数组实现普通队列有一个致命问题队头出队后front指针不断向后移动数组前面的位置永远空出来后面的位置却很快用完。这就是“假溢出”。如果直接把数组大小拉满数据规模增大后很容易爆内存。解决方案是循环队列——把数组当成一个环队尾指针走到数组末尾时回到数组头部继续走。实现循环队列时关键是要设计好判空和判满的条件。const int MAXN 100005; int queueArr[MAXN]; int head 0, tail 0; // 队头指针和队尾指针tail指向下一个入队的位置 // 入队 void enqueue(int x) { if ((tail 1) % MAXN head) { // 队满实际处理时可以扩容或者报错 return; } queueArr[tail] x; tail (tail 1) % MAXN; } // 出队 int dequeue() { int x queueArr[head]; head (head 1) % MAXN; return x; } bool isEmpty() { return head tail; }注意上面这个实现我把数组大小设为MAXN但实际最多只能存MAXN - 1个元素。因为判满条件用的是“tail再走一步就追上head”。这种“牺牲一个存储单元”的做法就是为了区分队空和队满——因为如果允许存满head和tail相等时既可能是空也可能是满就分不清了。循环队列的指针移动全都需要模运算。有的同学觉得模运算麻烦就写成了tail (tail 1 MAXN ? 0 : tail 1)这个写法也对本质和取模一样。考试时我更推荐直接写% MAXN代码短、不容易出错。3.3 链表队列链表实现队列需要维护两个指针队头指针指向链表头队尾指针指向链表尾。入队操作是向链表尾部插入新节点出队操作是删除链表头部的节点。时间复杂度也都是O(1)。链表队列的优势在于不浪费数组空间不会出现循环队列那种“少存一个元素”的问题。但在六级考试的场景里你几乎不需要用链表实现队列。我更推荐你掌握数组循环队列因为BFS这类题目本身就需要自己维护队列数组版写起来更直观。3.4 STL queue实战用法STL queue的使用比数组手写版更简单同样包含头文件即可。#include iostream #include queue using namespace std; int main() { queueint q; for (int i 1; i 3; i) q.push(i); while (!q.empty()) { cout q.front() ; q.pop(); } // 输出1 2 3 return 0; }这个模板同样要记住循环内的顺序先读front再pop。和stack的区别只有一点stack读的是topqueue读的是front。底层容器方面queue默认也是deque。这里特别提醒一下STL queue没有clear()方法。你想清空一个队列要么重新构造一个新的queue对象要么用while (!q.empty()) q.pop();把元素全部弹掉。这点和vector、map不一样很多同学第一次用queue清空时会去找clear()然后找不到白白浪费时间。3.5 双端队列deque考纲外的隐藏利器严格来说deque不在六级考纲的基础要求里但它在单调队列、滑动窗口这类高频题目中几乎是必用的。deque的特点是队头和队尾都可以入队、出队。C里包含头文件deque后用push_back、push_front、pop_back、pop_front就能操作两端。为什么需要deque我举个例子。求“滑动窗口最大值”时你需要随时从队尾弹出比当前元素小的旧元素又要从队头弹出已经滑出窗口的过期元素还要从队尾压入新元素。普通queue只允许从一端进另一端出根本做不到。deque两端开放正好满足需求。deque的用法我后面在“单调队列”小节会给出完整代码。你现在记住一个结论队列相关的高级题基本绕不开deque。4. 栈的经典应用场景4.1 括号匹配最常见的入门题括号匹配是栈最经典的应用没有之一。题目给你一串只包含()、[]、{}的字符串让你判断括号是否合法。合法的定义有三条左括号必须用同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号必须有一个对应的左括号。用栈的解法是遍历字符串遇到左括号就压栈遇到右括号时先判断栈是否为空为空说明当前右括号没有匹配的左括号直接判不合法不为空则弹出栈顶检查类型是否和当前右括号匹配。#include iostream #include stack #include string using namespace std; bool isValid(string s) { stackchar st; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty()) return false; char top st.top(); st.pop(); if (c ) top ! () return false; if (c ] top ! [) return false; if (c } top ! {) return false; } } return st.empty(); }这个代码里最关键的细节是最后的return st.empty()。很多同学遍历完字符串就直接return true忽略了字符串可能是“((())”这种左边多一个括号的情况。遍历结束后栈里还有剩余未匹配的左括号说明不合法。这个细节六级考试反复考你务必形成条件反射。4.2 表达式求值中缀转后缀与后缀计算表达式求值是六级爱考的“综合型题目”。它通常分两种考法一种要求你把中缀表达式转成后缀或前缀表达式另一种直接让你算出表达式的结果。中缀转后缀的规则是遍历中缀表达式的每个元素如果是数字或变量直接输出如果是左括号压栈如果是右括号不断弹出栈顶运算符并输出直到遇到左括号左括号弹出但不输出如果栈为空或栈顶是左括号运算符直接压栈如果当前运算符优先级高于栈顶运算符直接压栈否则弹出栈顶并输出然后继续比较新的栈顶。#include iostream #include stack #include string #include map using namespace std; int priority(char c) { if (c || c -) return 1; if (c * || c /) return 2; return 0; } string infixToPostfix(string s) { string result; stackchar st; for (char c : s) { if (isdigit(c) || isalpha(c)) { result c; } else if (c () { st.push(c); } else if (c )) { while (!st.empty() st.top() ! () { result st.top(); st.pop(); } if (!st.empty()) st.pop(); // 弹出左括号 } else { while (!st.empty() priority(st.top()) priority(c)) { result st.top(); st.pop(); } st.push(c); } } while (!st.empty()) { result st.top(); st.pop(); } return result; }注意这里的优先级比较我用的是“大于等于”就弹出。为什么不是“大于”因为当相邻运算符优先级相同时中缀转后缀遵循“先左后右”的原则必须先把栈里已有的运算符弹出来不能让它压在底下。如果你写成“大于”同一级的运算符输出顺序就会反转结果就错了。后缀表达式求值就简单多了遍历后缀串遇到操作数就压栈遇到运算符时弹出两个操作数先弹出的是右操作数后弹出的是左操作数计算之后把结果再压回栈。遍历结束后栈顶就是最终结果。这个“先弹出右、后弹出左”的顺序特别容易写反你写代码时一定注意除法时谁是被除数。4.3 单调栈找最近更大或更小元素单调栈不是一个独立的容器而是用栈维护一个“单调递增”或“单调递减”的序列。它的典型题型是给你一个数组对每个元素求它右边第一个比它大的元素。这类题目用暴力法的话两层循环O(n²)直接超时。用单调栈可以把复杂度降到O(n)。核心思想是维护一个栈从栈底到栈顶元素值保持单调递减遍历数组时每遇到一个新元素就把栈中所有比它小的元素弹出弹出时说明这些元素的“右边第一个更大元素”就是当前元素。#include iostream #include stack #include vector using namespace std; vectorint nextGreaterElement(vectorint nums) { int n nums.size(); vectorint res(n, -1); stackint st; // 存下标 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { res[st.top()] nums[i]; st.pop(); } st.push(i); } return res; }这个代码里我做了一个关键决定栈里存的是下标不是元素值。为什么不直接存值因为结果数组res需要按下标赋值。如果只存值你还得再去找这个值的位置多一步查找不说值重复时还可能找错。存下标就完全避免了这个问题这也是单调栈的标准写法。六级考试如果考单调栈大概率就是类似这样让你求“下一个更大值/更小值”或者“之前最近更大值/更小值”。4.4 函数调用与递归栈的更底层价值你有没有好奇过递归函数为什么能一层一层调用再一层一层返回这正是因为系统在底层用调用栈维护了每次函数调用的现场——局部变量、返回地址、参数全部压进栈里。最深的一层调用最先返回完全就是后进先出。这个知识点在六级里虽然不会直接要求你写汇编或模拟函数调用栈但理解它有一个实际好处你能理解为什么递归容易爆栈。递归层数太多时系统调用栈空间被耗尽程序就会异常退出。考场上如果一道递归题跑崩了很大概率不是逻辑错而是栈爆了。这时候你就该考虑用显式的栈改写递归或者用递推直接算。另外很多“模拟递归”的题目会明确要求你不用递归自己用栈模拟函数调用过程。这种题本质上就是把系统调用栈改成自己的栈只是你需要连参数、返回值、当前执行到第几步这些状态一起维护。能把这个做明白你对栈的理解就远超六级水平了。5. 队列的经典应用场景5.1 广度优先搜索BFS与队列绑定的原因BFS广度优先搜索是六级考试的高频考点而BFS的标准实现就是队列。为什么一定是队列因为BFS要求按层遍历先把距离起点为1的所有节点处理完再处理距离为2的节点保证“先访问的节点先扩展”。这个“先来先处理”的规则正好就是队列的先进先出性质。我写过很多次BFS给你一个最标准的模板。假设是从一个起点出发在二维网格上求到达某个目标的最短步数#include iostream #include queue #include vector using namespace std; int bfs(vectorvectorint grid, int startX, int startY, int targetX, int targetY) { int rows grid.size(), cols grid[0].size(); vectorvectorint dist(rows, vectorint(cols, -1)); queuepairint, int q; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; dist[startX][startY] 0; q.push({startX, startY}); while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (x targetX y targetY) return dist[x][y]; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx rows ny 0 ny cols grid[nx][ny] ! 1 dist[nx][ny] -1) { dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } } return -1; }这个模板有几个容易遗漏的细节。一是dist数组初始化成-1既表示“还没访问过”又能顺便存步数。二是每次新节点入队前就把dist值更新好千万不能等出队时再更新。如果出队才更新同一个节点可能被多个邻居重复入队就会出现“节点已经入队但dist还是-1”的情况造成重复访问甚至死循环。三是方向数组dx和dy四个方向要写全漏一个方向答案就会错。5.2 单调队列滑动窗口的最值问题滑动窗口最值问题也是六级爱考的高频类型。题目描述通常是给一个数组和一个窗口大小k窗口每次向右滑一个位置求每次窗口中k个元素的最大值或最小值。暴力做法的复杂度是O(nk)数据一大就超时。单调队列可以在O(n)内解决。核心思路用deque维护一个单调递减队列里面存数组下标。队头始终是当前窗口最大值所在的下标。每来一个新元素先把队尾所有比它小的下标弹出因为它们不可能成为最大值了再把新下标压入队尾最后把已经滑出窗口的下标从队头弹出。#include iostream #include vector #include deque using namespace std; vectorint maxSlidingWindow(vectorint nums, int k) { int n nums.size(); vectorint res; dequeint dq; for (int i 0; i n; i) { // 弹出队尾比当前元素小的旧下标 while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); // 弹出队头已经滑出窗口的下标 while (!dq.empty() dq.front() i - k) { dq.pop_front(); } // 窗口形成后才记录答案 if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; }这里有两个细节值得画重点。第一个是弹出队尾时用的是还是。如果窗口里允许存在值相同的多个元素用会丢掉前面那个等值元素但这不影响最大值结果因为它的位置更早出窗口也更早用反而把无法成为更优解的旧值提前清掉了。如果你用结果也正确但队列里会多存了一些等值下标。两种写法都能过题但理解区别能帮你在考场更自信。第二个是dq.front() i - k这个判断它判断下标是否已经滑出窗口。这个条件最好用下标比较而不是用窗口左边界因为队列里存的就是下标直接和i - k比较最直观。5.3 约瑟夫问题队列模拟环形生死游戏约瑟夫问题是一个经典的模拟题n个人围成一圈从第一个人开始报数报到m的人出圈然后从下一个人重新报数问最后剩下谁。这个问题的数学解法很有意思可以用递推公式O(n)求解但如果你在考场上想不出来数学方法队列模拟是最稳妥的。模拟的思路是把所有人依次入队。每次把前m-1个人从队头弹出、再重新压回队尾相当于让它们绕圈第m个人直接弹出不压回去。重复这个过程直到队列只剩一人。#include iostream #include queue using namespace std; int josephus(int n, int m) { queueint q; for (int i 1; i n; i) q.push(i); while (q.size() 1) { for (int cnt 1; cnt m; cnt) { int front q.front(); q.pop(); q.push(front); } q.pop(); // 第m个人出圈 } return q.front(); }这个方法虽然时间复杂度是O(n*m)但胜在思路直接、代码不容易错。在六级数据规模下性能完全够用。它能帮你理清“队列的两端循环移动”这个直觉对理解BFS里队列作为层级扩展工具也有帮助。5.4 缓冲区与任务调度队列在系统里的影子队列在计算机系统里无处不在。打印机任务会排队、消息队列会排队、进程调度也会排队。考纲里虽然不会展开系统实现细节但有类“模拟题”会借用队列做任务调度。比如题目会给你一堆任务每个任务有到达时间和处理时长问你平均等待时间或总完成时间。这道题的解法就是维护一个队列按时间顺序扫描事件任务到达时入队处理器空闲时从队头取任务处理。所谓“先来先服务”就是队列的先进先出。理解这个场景后你会发现队列不是考试专属的数据结构它本身就是系统最基础的调度模型。六级考这种模拟题时考查重点集中在“什么时候该入队”“什么时候该出队”“队满/队空怎么处理”三个问题上。6. 六级考场上的常见陷阱与得分技巧6.1 栈与队列最容易踩的五个坑这些年我批过不少学生的代码也帮很多同学排查过六级模拟题的问题。栈与队列相关的代码错误翻来覆去就是这几类。第一个坑把front()和back()用混。队列只有front()读队头、back()读队尾出队永远是把队头弹掉。有的同学觉得队列嘛两头都能出于是写了个q.pop_back()——这是deque的操作不是queue的操作。一旦编译器报错或者运行结果不对优先检查是不是把操作名写错。第二个坑忘记判断空栈或空队列就直接取顶部/队头元素。top()、front()、pop()对空容器调用都是未定义行为有的编译器会直接崩溃。考试时尤其是循环里取元素必须先用empty()把关。我建议你养成条件反射任何读取或弹出操作的前一行都要看一眼有没有空容器保护。第三个坑把数组栈的topIndex初始化为-1还是0搞混。很多教材习惯让topIndex表示当前栈顶的下标初始化为-1入栈先自增再赋值。而我在前面给的写法是topIndex表示下一个入栈位置初始化为0。这两种写法都对但你不能混着用。最惨的情况是写着写着把两种写法的判断条件混在一起导致栈顶元素取错。选定一种从头到尾用到底。第四个坑循环队列的判空判满条件。循环队列用“一个空位”区分空和满这一点在理解上特别容易出问题。很多同学背下了判断条件却不理解为什么要留一个空位结果一旦需要扩容或者修改队列大小代码就崩。建议你亲手画一个大小为5的数组模拟连续入队5次再出队3次把每一步的head、tail变化写出来比死记公式有用得多。第五个坑STL stack和queue的遍历不能范围for。很多同学对vector写惯了范围for对stack也来了个for (int x : st)然后编译器报错。原因是stack、queue不允许直接遍历内部元素你必须通过pop一个一个取。这在刷题时很浪费时间但搞清楚原理就发现它只是API设计如此不是你的编译器坏了。6.2 读题识栈题目话语与数据结构的对应关系我经常跟学生说六级考试里最难的技术不是写代码而是从题目描述里看出该用哪个结构。这里整理一个对应关系表你可以当口诀用。题目关键词或场景优先考虑的结构括号匹配、字符串撤销、嵌套结构栈表达式求值、中缀转后缀、逆波兰式栈递归改非递归、模拟函数调用栈求“下一个更大/更小元素”“最近更大/更小元素”单调栈BFS、最短路径、层级扩展队列“窗口”中的最值、区间最值单调队列deque按顺序输出、先来先服务、任务调度队列环形淘汰、轮转调度队列模拟看题时你先把题目里的“先进后出”“撤销”“嵌套”“匹配”这类词圈出来它们大概率提示用栈把“按层”“依次”“最短步数”“窗口”这些词圈出来大概率提示用队列。这个习惯能明显提高读题速度也能避免重复读题浪费时间。6.3 考场时间分配栈与队列部分应该花多久六级考试的时间压力其实是有的。如果你的策略是每题都满分做完那栈与队列相关的选择题通常不建议超过3分钟填空题如果有控制在3分钟以内算法题控制在20到30分钟。这不是说栈与队列不重要而是它们解题路径相对固定熟练之后不该在这里过度纠结。做算法题时我给的顺序是1分钟读题并圈关键词2分钟想清楚用哪种数据结构、大概需要几个容器5分钟写完代码框架剩下10分钟逐步验证边界情况。栈与队列相关的题目边界特别好找——空容器操作、单元素情况、窗口大小等于1或等于数组长度把这些都测一遍代码就基本没有大问题了。7. 三个拿来即用的完整例题7.1 括号匹配的进阶变体含星号的匹配六级如果提高难度括号匹配题可能加一个变体字符串里除了左右括号还出现星号*星号可以被当作左括号、右括号或者空字符。问你能否使这个字符串的括号完全匹配。这个题看起来复杂其实本质还是栈思想只是你可以用两个计数器或者两个栈分别记录“未匹配左括号的位置”和“星号的位置”。这里我不展开全部解法而是给你一个用栈实现的思路方便你体会栈在复杂题目里如何组合使用。#include iostream #include stack #include string using namespace std; bool checkValidString(string s) { stackint left, star; for (int i 0; i s.size(); i) { if (s[i] () { left.push(i); } else if (s[i] *) { star.push(i); } else { // 当前是右括号 if (!left.empty()) { left.pop(); } else if (!star.empty()) { star.pop(); } else { return false; } } } // 处理剩余的左括号尽量用星号匹配 while (!left.empty()) { if (star.empty() || star.top() left.top()) return false; star.pop(); left.pop(); } return true; }这里用两个栈的原因是左括号必须和它右面的星号才能匹配。如果星号在左括号左边它就不能充当右括号。所以在处理剩余左括号时必须检查星号下标是否大于左括号下标。单靠一个计数器做不到这种位置上的判断而栈天然保存了位置信息。你能把这个例子吃透说明你对栈的理解已经非常扎实。7.2 滑动窗口最大值完整实现结合前面单调队列的代码我给你一个可以完整提交的版本包含输入输出和结果展示。#include iostream #include vector #include deque using namespace std; vectorint maxSlidingWindow(vectorint nums, int k) { vectorint res; dequeint dq; for (int i 0; i (int)nums.size(); i) { while (!dq.empty() nums[dq.back()] nums[i]) { dq.pop_back(); } dq.push_back(i); while (!dq.front() i - k) { dq.pop_front(); } if (i k - 1) { res.push_back(nums[dq.front()]); } } return res; } int main() { int n, k; cin n k; vectorint nums(n); for (int i 0; i n; i) cin nums[i]; vectorint ans maxSlidingWindow(nums, k); for (int i 0; i (int)ans.size(); i) { cout ans[i] (i 1 (int)ans.size() ? \n : ); } return 0; }我特别提醒一下while (!dq.empty() dq.front() i - k)这行的空判断别省。虽然逻辑上前面的操作保证队列里可能有元素但如果代码在窗口还没形成时desk队头就过期了少了这个判断就会访问到空队列的front直接异常。这种细节在考场上崩一次心态就容易炸。另外输入格式注意处理当k等于数组长度时窗口只有一个只有一条输出当k等于1时输出就是原数组。这两种特殊情况自己用样例测一下再交。7.3 中缀表达式求值完整实现最后一个综合题我把中缀转后缀和后缀求值合在一起写一个能直接计算整数表达式值的完整程序。假设输入只包含数字、加号、减号、乘号、除号和括号操作数都是一位数字。#include iostream #include stack #include string using namespace std; int priority(char c) { if (c || c -) return 1; if (c * || c /) return 2; return 0; } int calculate(string s) { stackint nums; stackchar ops; for (int i 0; i (int)s.size(); i) { if (s[i] 0 s[i] 9) { nums.push(s[i] - 0); } else if (s[i] () { ops.push(s[i]); } else if (s[i] )) { while (!ops.empty() ops.top() ! () { int b nums.top(); nums.pop(); int a nums.top(); nums.pop(); char op ops.top(); ops.pop(); if (op ) nums.push(a b); else if (op -) nums.push(a - b); else if (op *) nums.push(a * b); else if (op /) nums.push(a / b); } if (!ops.empty()) ops.pop(); // 弹出左括号 } else { while (!ops.empty() priority(ops.top()) priority(s[i])) { int b nums.top(); nums.pop(); int a nums.top(); nums.pop(); char op ops.top(); ops.pop(); if (op ) nums.push(a b); else if (op -) nums.push(a - b); else if (op *) nums.push(a * b); else if (op /) nums.push(a / b); } ops.push(s[i]); } } while (!ops.empty()) { int b nums.top(); nums.pop(); int a nums.top(); nums.pop(); char op ops.top(); ops.pop(); if (op ) nums.push(a b); else if (op -) nums.push(a - b); else if (op *) nums.push(a * b); else if (op /) nums.push(a / b); } return nums.top(); } int main() { string expr; cin expr; cout calculate(expr) endl; return 0; }计算表达式时最关键的注意点还是“先弹出b、再弹出a”。我见过太多同学写成int a nums.top(); nums.pop(); int b nums.top(); nums.pop();然后算a - b结果所有减法都反了。遇到表达式“4-1”算成“1-4-3”最后答案怎么对都对不上。写除法时a是被除数、b是除数弹出顺序错一个字符结果就差十万八千里。另外强调一下这个版本只处理一位数字。如果题目中出现多位数你需要在扫描数字时做一个循环把连续的数字累加起来再压栈。六级的计算器题大概率会有多位数情况建议你自己把这个版本升级一下当字符是数字时用一个while循环从当前i开始连续取数字字符构造完整整数后压栈。这个改动很能检验你字符串处理的功底。结合我自己辅导学生备考的经验栈与队列这部分只要你把“手写数组模拟”和“STL用法”两套能力都扎实再把括号匹配、表达式求值、BFS、滑动窗口这四个经典模板各亲手敲三遍以上六级的考察基本就覆盖全面了。最后还有个小建议考前一周不要再刷新题把错题和这几个模板从头到尾默写一遍比做十套新卷子都管用。栈与队列的题做到真正“闭眼都能写”你在考场上就能腾出时间给那些更需要思考的难题。