企业官网建设流程全解析

刷题刷到一定阶段，你会发现一个很有意思的现象：队列和栈这两个基础数据结构，几乎出现在每一场笔试里。它们各自的定义都很简单——一个先进先出，一个后进先出，可一旦落到题目里，考法却五花八门。栈可以用来做括号匹配、表达式求值、单调栈优化；队列能演化出循环队列、双端队列、广度优先搜索。这篇内容就是把这些“基础题目”从头到尾捋一遍，适合刚开始刷题的同学，也适合面试前想快速过一遍核心题型的人。

我见过不少同学，上来就背题解模板，结果题目稍微换个马甲就认不出来了。所以这篇不会直接丢代码让你抄，而是把每个经典题型背后的判断逻辑讲清楚：它为什么用栈、为什么用队列、代码需要怎么组织边界条件。你把这些想明白了，再做变体题会轻松很多。

1. 先搞清楚：队列和栈到底在考什么

很多教程一上来就讲数组模拟栈、链表模拟队列，把实现细节铺一大堆，学生跟着写完了还是懵的。我觉得第一步应该是把问题最核心的矛盾看清楚。

1.1 两种结构的本质差异

栈是后进先出，队列是先进先出。这句话谁都会背，但做题时怎么用？我一般会用一个生活化的场景帮自己判断：

栈就像叠盘子。你洗完一个盘子往上一放，要用的时候必然先拿最上面的那个。所以栈天然适合处理“最近相关”的信息——最近进入的括号、最近推入的操作符、最近访问过的路径节点。

队列就像排队买奶茶。先来的人先拿到，后来的人只能往后站。所以队列适合处理“顺序保障”的信息——按层遍历的节点、任务调度的请求、滑动窗口里的元素顺序。

做题的时候先问自己一句：我当前的场景里，是需要“回溯最近状态”，还是“维持提交顺序”？要回溯，优先想栈；要顺序，优先想队列。这个判断比任何模板都管用。

提示：有些题表面上是数组或字符串，但操作逻辑里藏着强烈的“最近匹配”味道，比如字符串连续消除、回文判断、历史记录恢复，基本都是栈的变体。

1.2 底层实现：数组还是链表，真的这么重要吗

教科书里通常会给两种实现：顺序栈（数组）和链栈（链表），队列也分顺序队列和链式队列。很多初学者在这里纠结，总觉得必须掌握某一种标准写法。我的建议是：基础实现要能默写，但刷题时别纠结，用现成的容器类就够了。

真正值得花时间搞明白的是“数组模拟栈/队列”背后的容量问题。数组模拟栈很简单，一个指针指向栈顶就行。数组模拟普通队列有个致命缺陷：出队以后队头前面的空间就浪费了，所以工程里很少用“普通数组队列”，更多用循环队列，或者直接用双端队列容器。

数组模拟循环队列有一个反直觉的地方——队空和队满的判定。我记得自己第一次写循环队列，用一个head == tail同时判断空和满，结果插入删除几次后就分不清了。后来才明白，这种写法必须预留一个位置：tail永远指向空位，队满条件就变成(tail + 1) % capacity == head。

你把这个细节想透，很多题目的边界条件就不会踩坑了。刷题不是背代码，是练边界条件的分寸感。

2. 必刷的基础题型与解题模板

队列和栈的基础题来来去去就那几类：互相实现、括号匹配、最小栈、单调栈、循环队列。这几类都可以演化出大量面试题，建议按顺序逐个击破。

2.1 用栈实现队列：核心是先存着，再倒出来

这是非常经典的设计题，LeetCode 平替题库里十有八九会出。它的价值不在于“把栈变成队列”这个结果，而在于让你理解两种结构的对称关系。

思路很简单：用两个栈，一个叫输入栈inStack，一个叫输出栈outStack。入队时往inStack压；出队时从outStack弹。但有一个关键操作——只有当outStack为空时，才把inStack里的元素全部倒进outStack。

为什么是“全部倒”而不是“倒一个”？因为一次倒完，元素的相对顺序就被逆转过来了：inStack栈顶是最后入队的元素，全部弹出压入outStack后，它就成了outStack栈底；而最早入队的元素变成outStack栈顶，正好符合队列先进先出的要求。倒完之后，之后的出队操作直接弹outStack就行，不需要再碰inStack，均摊时间复杂度是 O(1)。

class MyQueue { private: stack<int> inStack, outStack; void transfer() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } } public: void push(int x) { inStack.push(x); } int pop() { transfer(); int top = outStack.top(); outStack.pop(); return top; } int peek() { transfer(); return outStack.top(); } bool empty() { return inStack.empty() && outStack.empty(); } };

这个题最容易犯的错误是在peek或pop里每次都调用transfer，导致性能退化。transfer只有在outStack空的时候才执行，这是摊销 O(1) 的关键。

2.2 用队列实现栈：思路反过来了

反过来这题也有意思：用两个普通队列实现一个栈。我一开始会觉得两个队列是对称的，一个负责入，一个负责出，但写出来发现完全不是这么回事。

正确的思路是让一个队列q1作为主存储，另一个q2作为临时缓冲区。入栈时直接往q1推。出栈时，把q1前面size - 1个元素全部搬到q2，剩下最后一个元素就是栈顶，弹出它。然后再把q2里的元素搬回q1。

操作其实只有一句话：每次出栈，都让队列里的“最后一个”元素浮到队头。这个操作每次是 O(n)，所以用队列模拟栈的复杂度并不好看，但它能帮你理解“如何从一种结构里强行提取出另一种结构的顺序”。

class MyStack { private: queue<int> q1, q2; public: void push(int x) { q1.push(x); } int pop() { while (q1.size() > 1) { q2.push(q1.front()); q1.pop(); } int top = q1.front(); q1.pop(); swap(q1, q2); return top; } int top() { while (q1.size() > 1) { q2.push(q1.front()); q1.pop(); } int top = q1.front(); q1.pop(); swap(q1, q2); q1.push(top); return top; } bool empty() { return q1.empty() && q2.empty(); } };

注意top()和pop()的处理差异：pop()弹出的元素不要了，top()弹出以后还得放回去。这个细节特别容易漏，我自己就吃过亏——写完top()直接复制了pop()的逻辑，结果访问一次栈顶后元素就没了。

2.3 括号匹配：栈最经典的“最近匹配”应用

括号匹配是栈入门必刷题，面试出现率极高。它的难度不大，但能引出一个很重要的思想：用栈记录“还没被匹配的左括号”，然后遇到右括号时判断栈顶是否匹配。

为什么能用栈？因为括号匹配本质上是一个“就近配对”的过程：最新的左括号必须匹配最近出现的右括号。这个"最近"就是栈的特性。

bool isValid(string s) { stack<char> st; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else { if (st.empty()) return false; if (c == ')' && st.top() != '(') return false; if (c == ']' && st.top() != '[') return false; if (c == '}' && st.top() != '{') return false; st.pop(); } } return st.empty(); }

这里有两个关键边界：遇到右括号时如果栈是空的，说明右侧多了一个右括号，直接返回false；遍历完所有字符后栈不为空，说明还有左括号没闭合，也返回false。

顺着这个思路可以延伸出很多变体题：字符串里只删一个括号使之合法、最长有效括号、表达式括号嵌套深度。核心始终是“用栈维护最近状态”。

2.4 单调栈：一类被低估的进阶基础

单调栈不算“简单题”，但它是在栈这个数据结构上最典型的应用，基础题阶段就应该接触。它的应用场景很集中：找数组中某个元素左边/右边第一个比它大/小的元素。

原理是维护一个栈，让栈内元素保持单调（递增或递减）。遍历数组时，一旦当前元素破坏了单调性，就不断弹出栈顶，弹出来的这一刻，栈顶元素的“答案”就确定了。

用“每日温度”这类题来理解：给你一组温度，要计算每一天需要等几天才能等到更高的温度。暴力做法是两层循环，O(n²) 超时。单调栈做法是每个元素只进栈出栈一次，O(n)。

vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> result(n, 0); stack<int> st; // 存下标，栈内温度递减 for (int i = 0; i < n; i++) { while (!st.empty() && temperatures[i] > temperatures[st.top()]) { int prev = st.top(); st.pop(); result[prev] = i - prev; } st.push(i); } return result; }

单调栈的模板题还有“下一个更大元素”“柱状图中最大的矩形”。这类题看起来难，但掌握了模板以后反倒比堆排、DP 更容易得分——代码短、思路固定、边界条件少。

注意：单调栈里存下标比存值更好用。存下标可以同时拿到值和位置，很多题目需要返回索引差，只存值还得额外映射。

2.5 最小栈：设计题里的空间换时间

最小栈要求实现一个栈，除了常规 push、pop、top，还要支持在 O(1) 时间内返回栈内最小值。最直接的思路是额外用一个“最小值栈”，记录当前栈中的最小值历史。

具体做法：主栈正常操作；每次 push 时，如果新值比最小栈栈顶小（或等于），就把新值也压入最小栈；每次 pop 时，如果主栈弹出的值等于最小栈栈顶，最小栈也弹出一个。

为什么相等也要压？因为如果最小栈遇到重复最小值时只压一次，pop 掉一个最小值后，另一个相同最小值可能还在主栈里，但最小栈已经丢了记录。这个细节不注意会 WA（答案错误）。

class MinStack { private: stack<int> data; stack<int> minData; public: void push(int val) { data.push(val); if (minData.empty() || val <= minData.top()) { minData.push(val); } } void pop() { if (data.top() == minData.top()) { minData.pop(); } data.pop(); } int top() { return data.top(); } int getMin() { return minData.top(); } };

复杂度上，主栈和最小栈都是 O(n) 空间，每个操作 O(1) 时间。如果你不想额外开一个栈，可以在主栈里存“当前值和当前最小值”的差值，但那属于进阶骚法，理解成本高，面试里容易把自己绕晕，不推荐新手用。

3. 手写实现：从零到 AC 的实操过程

光看题目解析容易产生一种错觉，觉得自己会了。真正动手写的时候，各种边界条件才会冒出来。这个章节我用一个完整的实操流程，带你手写栈和循环队列的底层实现，并且把过程中最容易踩的坑指出来。

3.1 用数组实现栈

数组实现栈是最基础的能力，代码很短，但有一个关键点：栈顶指针的初始值。假设数组长度为n，栈顶指针top从 -1 开始，那么插入元素时先top++，再把元素写入arr[top]。

class ArrStack { private: vector<int> arr; int top; int capacity; public: ArrStack(int cap) : capacity(cap), top(-1) { arr.resize(cap); } bool push(int val) { if (top == capacity - 1) return false; // 栈满 arr[++top] = val; return true; } bool pop() { if (top == -1) return false; // 栈空 top--; return true; } int topValue() { return arr[top]; } };

为什么top要从 -1 开始？因为栈空时，top = -1表示“栈顶下标不存在”，插入第一个元素后top = 0，也方便判断top == capacity - 1表示满。这种细节看似不值一提，但很多考试题会考手写数组栈，边界条件没写全直接扣分。

另一种写法是top从 0 开始，指向“下一个空位”，这样栈空条件是top == 0，栈满条件是top == capacity。两种思路都可以，但判断条件和插入顺序完全不同，千万别混着写。

3.2 数组实现循环队列

循环队列是笔试手写题里的常客，核心就是为了解决普通数组队列的“假溢出”问题。普通队列用数组实现后，出队操作会导致队头前的空间无法再利用，所以用取模运算把数组“首尾相接”。

循环队列需要两个指针：head指向队头元素，tail指向队尾的下一个空位。初始时head = tail = 0。关键判定：

• 队空：head == tail
• 队满：(tail + 1) % capacity == head

class CircularQueue { private: vector<int> arr; int head, tail; int capacity; public: CircularQueue(int cap) : capacity(cap), head(0), tail(0) { arr.resize(cap); } bool enqueue(int val) { if ((tail + 1) % capacity == head) return false; arr[tail] = val; tail = (tail + 1) % capacity; return true; } bool dequeue() { if (head == tail) return false; head = (head + 1) % capacity; return true; } int front() { return arr[head]; } };

实现里有个反直觉的点：数组长度是capacity，实际能存的数据最多只有capacity - 1个。因为你必须留一个空位来区分“空”和“满”。如果不留这个空位，可以再加一个size变量来记录当前元素数量，但笔试手写时记录size会更繁琐，留空位是更标准、更不容易出错的方案。

3.3 手写风格对刷题的影响

很多平台都允许直接用现成容器，为什么我还要强调手写？因为某些面试场景会要求你展示“对基础实现的理解”，而且手写一遍能帮你看清容器底层做了什么。

我的建议是：平时刷题用容器，面试前专门花两天手写一遍栈、队列、循环队列，并且把数组版和链表版都写熟。写完以后，你会发现自己对push/pop/empty/full这些操作更敏感了，遇到容器题也不会犯“忘记判空”的低级错误。

选语言时，如果你用 C++，stack和queue都是现成的，记得queue的默认底层是双端队列deque；用 Java 的话，Deque接口可以同时模拟栈和队列，注意push/pop是作用于队头还是队尾的区别。不管什么语言，思路完全一致。

4. 常见问题排查与避坑经验实录

这章我把自己刷题、带人时遇到的共性问题集中列一下。这些坑如果你提前知道，能省下不少调试时间。

4.1 高频错误速查表

这张表是我把所有常见错误汇总出来的。你会发现，绝大多数错误都源于“边界条件不清”和“两种结构特性混淆”。前者靠画图解决，后者靠把 1.1 节里的“最近匹配 vs 顺序保障”判断练熟。

4.2 调试技巧：小数据手推 + 打印出入栈

我之前带某个同学调试一道中缀表达式求值题目，他卡了一个多小时找不到问题。我让他把每次 push 和 pop 的元素都打印出来，对照手推的小数据一步步走，几分钟就定位到了运算优先级处理错误。这个经验我觉得新手值得借鉴。

调试栈和队列题目，有一个极其有效的方法：用长度为 2 到 3 的极短数据测试，然后逐步在纸上记录栈或队列的内容变化。比如调试括号匹配，就用"()"、"(()"、")("这三个用例，分别覆盖正常、左括号多、右括号多三种情况。代码里临时加入输出语句：

// 调试括号匹配时 cout << "current char: " << c << " stack top: " << (st.empty() ? -1 : st.top()) << endl;

看输出状态的变化是否符合预期。这类问题一旦定位，往往是某个if条件的反向或缺失。

实操心得：不要只在出错的一组用例上调试。找一组“同类型但结果不同”的用例对比，比如(()和())，它们输入长度相同，但一个是左括号多，一个是右括号多。对比输出能直接暴露问题在哪一层逻辑。

4.3 关于复杂度分析的一个认知纠偏

很多同学刷基础题时完全不关注复杂度，因为题简单，暴力也能过。但我建议从基础题开始就养成习惯，每次 AC 以后停下来估算一下时间复杂度和空间复杂度，然后想想有没有更优解。

以“每个温度等几天变暖”为例，暴力 O(n²) 在数据量小时能过，可面试官问你“能不能优化”时，你说不上来就是减分项。再比如用队列模拟栈，每次 pop 是 O(n)，如果你意识不到这一点，后续遇到“要求 O(1) 操作”的设计题时就会走偏。复杂度分析不是独立的知识点，它是你选数据结构、设计算法时的决策依据。

5. 我对刷这些题目的几点个人建议

刷完队列和栈的基础题，你会发现自己对“数据结构怎么选”这件事有了初步的感觉。我再分享几个个人体会。

第一，别把“背代码”当“学会”。我自己带人的时候会让他们合上题解，把题目的关键逻辑用自己的话讲一遍：为什么用栈、什么时候倒数据、队列满的条件是什么。能讲清楚，才说明真懂了。第二，每个题尝试自己构造几个特殊用例，比如空输入、重复元素、单元素、全量操作——这些用例往往能炸出代码里的边界漏洞。第三，基础题刷完以后，建议马上去接触依赖这两种结构的中级题：单调栈进阶、滑动窗口最大值、表达式求值、BFS 层序遍历。因为栈和队列的真正威力，是在这些组合题里体现出来的。

我一直觉得，队列和栈是算法刷题路上投入产出比最高的内容。它们不像动态规划那样需要大量灵感，也不像图论那样有复杂的建模过程，只要把原理、模板、边界条件吃透，就能稳定拿到分数。从这两兄弟入手，是很值得的投资。