栈与队列

序言：受限的线性表

在深入具体的数据结构之前，我们需要理解一个基本概念：线性表。你可以把它想象成一排整齐排列的元素，就像一列火车车厢。你可以访问任何一节车厢，也可以在任何位置插入或移除车厢。数组（vector）和链表都是线性表的典型实现。

然而，在许多计算问题中，我们并不需要如此完全的自由度。有时候，对操作加以限制，反而能带来结构上的简洁和效率上的优势。栈与队列就是两种最重要的受限线性表。它们限制了元素的插入和删除操作只能在表的两端进行，从而衍生出两种截然不同的数据处理模式。

第一章：栈 (Stack)

1.1 定义与特性：后进先出 (LIFO)

栈是一种遵循后进先出（Last-In, First-Out，简称 LIFO）原则的数据结构。

这个概念可以用一个简单的生活实例来理解：一叠盘子。

1. 放盘子 (Push)：你洗好一个新盘子，自然会把它放在最上面。
2. 取盘子 (Pop)：当你要用盘子时，也总是从最上面拿走一个。

最后放上去的盘子，最先被拿走。这就是“后进先出”的核心思想。在栈结构中，允许插入和删除的一端被称为栈顶 (top)，另一端则是栈底 (bottom)。所有操作都围绕栈顶进行。

1.2 核心操作

栈的基本操作非常简洁：

• push(x): 将元素 $x$ 压入栈顶。
• pop(): 移除栈顶元素。
• top(): 查询栈顶元素的值，但不移除它。
• empty(): 判断栈是否为空。
• size(): 返回栈中元素的数量。

1.3 C++ 实现

在算法竞赛中，我们几乎总是使用 C++ 标准模板库 (STL) 中提供的 std::stack，因为它高效、稳定且易于使用。

std::stack 是一个容器适配器，意味着它并非一个全新的容器，而是对现有容器（默认是 std::deque，双端队列）的功能进行封装和限制，使其表现出栈的行为。

基础用法示例

下面的代码演示了 std::stack 的所有核心操作。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    // IO优化
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    stack<int> s; // 声明一个存放 int 类型元素的栈

    cout << "Is stack empty? " << (s.empty() ? "Yes" : "No") << endl; // 输出: Yes

    s.push(10); // 压入 10, 栈: [10]
    s.push(20); // 压入 20, 栈: [10, 20]
    s.push(30); // 压入 30, 栈: [10, 20, 30]

    cout << "Stack size: " << s.size() << endl; // 输出: 3
    cout << "Top element: " << s.top() << endl; // 输出: 30

    s.pop(); // 弹出 30, 栈: [10, 20]
    cout << "After pop, top is: " << s.top() << endl; // 输出: 20

    s.pop(); // 弹出 20, 栈: [10]
    s.pop(); // 弹出 10, 栈: []

    cout << "Is stack empty now? " << (s.empty() ? "Yes" : "No") << endl; // 输出: Yes

    // 注意：对空栈执行 top() 或 pop() 会导致未定义行为（通常是程序崩溃）
    // if (!s.empty()) { s.pop(); } // 安全的做法

    return 0;
}

• 复杂度分析：对于 std::stack，所有基本操作——push, pop, top, empty, size——的时间复杂度均为 $O(1)$，即常数时间。空间复杂度为 $O(N)$，其中 $N$ 是栈中元素的数量。

1.4 典型应用

栈的 LIFO 特性使其在处理具有“对称性”、“嵌套性”或“撤销性”的问题时特别有效。

1.4.1 程序阅读题：预测输出

题目

分析以下代码片段，写出其最终输出。

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    stack<int> s;
    for (int i = 1; i <= 5; ++i) {
        s.push(i);
    }
    int a = s.top(); s.pop();
    s.push(a - 2);
    s.push(s.top() + 1);
    cout << s.top() << " ";
    s.pop();
    cout << s.top() << endl;
    return 0;
}

解题思路

我们需要像计算机一样，一步步地追踪栈内元素的变化：

1. for 循环：依次将 1, 2, 3, 4, 5 压入栈。栈内状态（从底到顶）：[1, 2, 3, 4, 5]。
2. int a = s.top(); s.pop();：s.top() 是 5，所以 a 被赋值为 5。然后 pop 操作移除 5。栈状态：[1, 2, 3, 4]。
3. s.push(a - 2);：a 是 5，a-2 是 3。将 3 压入栈。栈状态：[1, 2, 3, 4, 3]。
4. s.push(s.top() + 1);：此时 s.top() 是 3，3+1 是 4。将 4 压入栈。栈状态：[1, 2, 3, 4, 3, 4]。
5. cout << s.top() << " ";：输出栈顶元素 4。
6. s.pop();：移除 4。栈状态：[1, 2, 3, 4, 3]。
7. cout << s.top() << endl;：输出栈顶元素 3。

最终输出

4 3

1.4.2 程序补全题：括号匹配

题意概括

给定一个只包含 (, ), {, }, [ 和 ] 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，且左括号必须以正确的顺序闭合。

分析

这是一个经典的栈应用。括号的嵌套结构天然符合 LIFO 原则。当我们遇到一个左括号，就好像进入了一个新的“层级”，我们将其压栈。当我们遇到一个右括号，就必须与最近进入的那个“层级”（即栈顶的左括号）相匹配。

代码框架

bool isValid(string t) {
    stack<char> s;
    for (char c : t) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else {
            // --- 补全这里的逻辑 ---
        }
    }
    return s.empty();
}

补全逻辑

当遇到右括号时，有三种情况会导致无效：

1. 栈为空：说明没有左括号与之匹配。
2. 栈顶的左括号与当前右括号类型不匹配。
3. 遍历完整个字符串后，栈不为空：说明有未闭合的左括号。

// 完整函数
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

bool chk(string t) {
    stack<char> s;
    for (char c : t) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);
        } else {
            if (s.empty()) return false; // 情况1：右括号多
            char top = s.top();
            s.pop();
            if (c == ')' && top != '(') return false; // 情况2：类型不匹配
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return s.empty(); // 情况3：检查是否所有左括号都已闭合
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string s1 = "()[]{}";
    string s2 = "([)]";
    cout << s1 << ": " << (chk(s1) ? "Valid" : "Invalid") << endl;
    cout << s2 << ": " << (chk(s2) ? "Valid" : "Invalid") << endl;
    return 0;
}

• 复杂度分析：我们对字符串进行单次遍历，每个字符最多被压入和弹出栈一次。因此，时间复杂度为 $O(L)$，其中 $L$ 是字符串长度。空间复杂度最坏情况下为 $O(L)$（例如，字符串全是左括号）。

1.4.3 核心代码题：后缀表达式求值

题意概括

计算一个后缀表达式（也叫逆波兰表达式）的值。例如，表达式 "4 5 + 3 *" 对应中缀表达式 "(4 + 5) * 3"。

分析

后缀表达式的求值是栈的绝佳应用。其规则是：从左到右扫描表达式，遇到数字则压入栈；遇到运算符，则从栈中弹出两个数字进行运算，并将结果压回栈中。扫描完毕后，栈中唯一剩下的数字就是最终结果。

C++ 核心代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 此处为了简化，我们假设输入是空格分隔的字符串
// 实际题目中可能需要处理负数和多位数，但核心逻辑不变
int eval(vector<string>& v) {
    stack<int> s;
    for (const string& t : v) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = s.top(); s.pop();
            int a = s.top(); s.pop();
            if (t == "+") s.push(a + b);
            else if (t == "-") s.push(a - b);
            else if (t == "*") s.push(a * b);
            else s.push(a / b);
        } else {
            s.push(stoi(t)); // stoi 将字符串转为整数
        }
    }
    return s.top();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<string> v = {"4", "13", "5", "/", "+"}; // 对应 (4 + (13 / 5))
    cout << "Result: " << eval(v) << endl;
    return 0;
}

• 复杂度分析：每个元素（数字或操作符）仅被处理一次。时间复杂度为 $O(N)$，其中 $N$ 是表达式中元素（数字和运算符）的个数。空间复杂度为 $O(N)$，用于存储操作数。

第二章：队列 (Queue)

2.1 定义与特性：先进先出 (FIFO)

队列是一种遵循先进先出（First-In, First-Out，简称 FIFO）原则的数据结构。

这完全符合我们日常生活中排队的经验：

1. 入队 (Enqueue)：新来的人总是站到队尾。
2. 出队 (Dequeue)：办理业务时，总是队首的人先接受服务。

最先进入队列的元素，最先被移出。在队列结构中，允许插入的一端称为队尾 (rear/back)，允许删除的一端称为队首 (front)。

2.2 核心操作

队列的操作集与栈类似，但名称和行为体现了 FIFO 的特性：

• push(x): 将元素 $x$ 加入队尾。
• pop(): 移除队首元素。
• front(): 查询队首元素的值。
• back(): 查询队尾元素的值。
• empty(): 判断队列是否为空。
• size(): 返回队列中元素的数量。

2.3 C++ 实现

与 std::stack 类似，C++ 标准库提供了 std::queue，它也是一个容器适配器，默认基于 std::deque 实现。

基础用法示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    // IO优化
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    queue<string> q; // 声明一个存放 string 的队列

    q.push("Alice");  // 入队, 队列: ["Alice"]
    q.push("Bob");    // 入队, 队列: ["Alice", "Bob"]
    q.push("Carol");  // 入队, 队列: ["Alice", "Bob", "Carol"]

    cout << "Queue size: " << q.size() << endl; // 输出: 3
    cout << "Front of queue: " << q.front() << endl; // 输出: Alice
    cout << "Back of queue: " << q.back() << endl; // 输出: Carol

    q.pop(); // Alice 出队, 队列: ["Bob", "Carol"]
    cout << "After pop, front is: " << q.front() << endl; // 输出: Bob

    q.pop(); // Bob 出队, 队列: ["Carol"]
    cout << "Now front is: " << q.front() << endl; // 输出: Carol

    // 注意：对空队列执行 front(), back(), pop() 同样是未定义行为
    
    return 0;
}

• 复杂度分析：对于 std::queue，所有基本操作——push, pop, front, back, empty, size——的时间复杂度也均为 $O(1)$。空间复杂度为 $O(N)$，其中 $N$ 是队列中元素的数量。

2.4 典型应用与笔试题

队列的 FIFO 特性使其成为实现“按顺序处理”、“逐层扩展”等算法的核心工具，最典型的应用就是广度优先搜索 (BFS)。

2.4.1 判断题

题目

一个初始为空的队列，依次将元素 A, B, C, D 压入队列，然后执行两次 pop 操作，再将元素 E 压入队列，最后再执行一次 pop 操作。此时的队首元素是 C。 (判断对错)

解题思路

1. push(A), push(B), push(C), push(D): 队列状态 (队首 -> 队尾): [A, B, C, D]。
2. pop(): A 出队。队列状态: [B, C, D]。
3. pop(): B 出队。队列状态: [C, D]。
4. push(E): E 入队。队列状态: [C, D, E]。
5. pop(): C 出队。队列状态: [D, E]。

题目问的是，在最后一次 pop 之后，队首元素是 C。这是错误的。在第三次 pop 操作中，被移除的元素是 C，操作后的新队首是 D。如果问题是“第三次 pop 操作移除的元素是C”，则为正确。因此，原命题为错误。

2.4.2 核心代码题：二叉树的层序遍历

题意概括

给定一个二叉树，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

分析

这正是队列 FIFO 特性的完美舞台。

1. 将根节点放入队列。
2. 当队列不为空时，循环执行以下操作： a. 从队首取出一个节点。 b. 访问该节点（例如，记录其值）。 c. 如果该节点有左孩子，将左孩子入队。 d. 如果该节点有右孩子，将右孩子入队。

由于队列的 FIFO 特性，我们处理完第一层的节点（只有根节点）后，队列里装的正好是所有第二层的节点。处理完所有第二层的节点后，队列里装的又正好是所有第三层的节点，以此类推。

C++ 核心代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 树节点的简单定义
struct Node {
    int val;
    Node *l, *r;
    Node(int v) : val(v), l(nullptr), r(nullptr) {}
};

// 层序遍历函数
vector<vector<int>> levelOrder(Node* root) {
    vector<vector<int>> ans;
    if (!root) return ans;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        int n = q.size(); // 当前层的节点数
        vector<int> cur; // 存放当前层结果
        for (int i = 0; i < n; ++i) {
            Node* node = q.front();
            q.pop();
            cur.push_back(node->val);
            if (node->l) q.push(node->l);
            if (node->r) q.push(node->r);
        }
        ans.push_back(cur);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // 构建一个简单的树: 3 / \ 9 20 / \ 15 7
    Node* root = new Node(3);
    root->l = new Node(9);
    root->r = new Node(20);
    root->r->l = new Node(15);
    root->r->r = new Node(7);

    vector<vector<int>> res = levelOrder(root);
    for (const auto& level : res) {
        for (int val : level) cout << val << " ";
        cout << endl;
    }
    return 0;
}

• 复杂度分析：每个节点被入队和出队恰好一次。时间复杂度为 $O(N)$，其中 $N$ 是树中的节点数。空间复杂度为 $O(W)$，其中 $W$ 是树的最大宽度，因为队列在某一时刻最多存储一层的所有节点。

第三章：深入与比较

3.1 双端队列 (Deque)

我们之前提到，std::stack 和 std::queue 默认都由 std::deque (double-ended queue) 实现。Deque 是一种更强大的序列容器，它允许在队首和队尾两端都进行 $O(1)$ 时间的插入和删除操作。

你可以把它想象成一列火车，两头都有火车头，可以在任意一端挂接或摘除车厢。

STL 提供了 std::deque，其接口像是 std::vector 和 std::queue 的结合体，支持 push_front, pop_front, push_back, pop_back 以及通过索引访问 []。

• 选择题视角：如果一个问题需要在序列的两端进行频繁的添加或删除，std::deque 是比 std::vector （其 push_front/pop_front 是 $O(N)$）更好的选择。

3.2 栈与队列的本质区别

特性	栈 (Stack)	队列 (Queue)
原则	LIFO (后进先出)	FIFO (先进先出)
操作端	仅在栈顶 (top)	队首 (front) 删除，队尾 (back) 添加
数据流	A, B, C -> 进栈 -> C, B, A -> 出栈	A, B, C -> 进队 -> A, B, C -> 出队
效果	颠倒顺序	保持顺序
核心应用	括号匹配、表达式求值、深度优先搜索(DFS)的递归实现	广度优先搜索(BFS)、任务调度、打印机缓冲

简单来说：

• 当你需要处理的问题有“撤销”或“返回”的意味，或者需要处理嵌套结构时，首先考虑栈。
• 当你需要处理的问题是“按顺序来”、“公平地处理”，或者要“一层一层地”探索时，首先考虑队列。

栈和队列是算法世界中最基础也最重要的两种数据结构。它们通过对线性表操作的限制，提供了简洁而高效的接口来解决特定类型的问题。

理解它们的 LIFO 和 FIFO 本质，是掌握更复杂算法（如图论、动态规划等）的基石。

第四章：高级技巧与变体

掌握了基础的栈与队列之后，我们可以探索一些由它们衍生出的、在算法竞赛中极为强大的技巧。这些技巧通过在基本操作中附加简单的规则，能够高效地解决一类特定问题。

4.1 单调栈 (Monotonic Stack)

单调栈是一种特殊的栈，它在任何时刻都保证从栈底到栈顶的元素是单调递增（或单调递减）的。

核心思想：

在向单调栈中压入一个新元素 $x$ 时，我们不再是直接将其 push 到栈顶。而是会不断地比较 $x$ 和当前的栈顶元素：

• 对于单调递增栈：如果 $x$ 小于栈顶元素，不满足递增性，则将栈顶元素弹出。重复此过程，直到栈为空或者 $x$ 大于等于新的栈顶元素。此时，再将 $x$ 压入栈。
• 对于单调递减栈：如果 $x$ 大于栈顶元素，不满足递减性，则将栈顶元素弹出。重复此过程，直到栈为空或者 $x$ 小于等于新的栈顶元素。此时，再将 $x$ 压入栈。

这个“清理”栈顶的过程，是单调栈所有魔力的来源。当一个元素被弹出时，意味着新压入的元素 $x$ 是它在某个方向上遇到的第一个比它更小（或更大）的元素。这使得单调栈成为解决“寻找下一个/上一个更大/更小元素”这类问题的利器。

4.1.1 核心代码题：寻找下一个更大元素 I

题意概括

给定一个数组 nums，对于每个元素 nums[i]，找到其右侧第一个比它大的元素。如果不存在，则结果为 -1。返回一个包含所有结果的数组。例如，输入 [2, 1, 2, 4, 3]，输出 [4, 2, 4, -1, -1]。

分析

我们可以从左到右遍历数组，并使用一个单调递减栈来存储元素的索引。

1. 遍历数组，当前元素为 nums[i]。
2. 当栈不为空，且 nums[i] 大于栈顶索引对应的元素 nums[s.top()] 时，说明我们为栈顶索引 s.top() 找到了它的“下一个更大元素”，即 nums[i]。我们记录下这个结果，并将栈顶索引弹出。
3. 重复步骤 2，直到栈为空或 nums[i] 不再大于栈顶索引对应的元素。
4. 将当前元素的索引 i 压入栈。因为所有比它小的元素的索引都已被弹出，栈的递减性得以维持。

遍历结束后，栈中剩余的索引所对应的元素，意味着它们右侧没有更大的元素，结果为 -1。

C++ 核心代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// v: 输入数组
vector<int> nxt(vector<int>& v) {
    int n = v.size();
    vector<int> ans(n);
    stack<int> s; // 存储索引

    for (int i = 0; i < n; ++i) {
        while (!s.empty() && v[i] > v[s.top()]) {
            // 当前元素 v[i] 是栈顶索引 s.top() 的下一个更大元素
            ans[s.top()] = v[i];
            s.pop();
        }
        s.push(i);
    }
    
    // 遍历结束后，栈中剩余的索引没有找到下一个更大元素
    while (!s.empty()) {
        ans[s.top()] = -1;
        s.pop();
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> v = {2, 1, 2, 4, 3};
    vector<int> res = nxt(v);
    for (int x : res) {
        cout << x << " ";
    }
    cout << endl; // 输出: 4 2 4 -1 -1 
    return 0;
}

• 复杂度分析：虽然代码中有 while 循环嵌套在 for 循环中，但每个元素的索引最多被压入和弹出栈一次。因此，总的时间复杂度为 $O(N)$，其中 $N$ 是数组的长度。空间复杂度为 $O(N)$，用于存储栈和结果数组。

4.2 单调队列 (Monotonic Queue)

单调队列通常使用双端队列 deque 实现，它和单调栈一样，内部元素维持单调性。但它更进一步，由于 deque 的特性，它允许我们从队首移除元素。这个特性使它完美适用于解决滑动窗口中的最值问题。

核心思想：

以“滑动窗口最大值”为例，我们需要一个单调递减的队列。队列中存储的是元素的索引。

1. 入队 (队尾): 当新元素 nums[i] 到来时，我们从队尾开始，移除所有比 nums[i] 小的元素对应的索引。这保证了队首永远是当前窗口内最大值的索引。然后将新元素的索引 i 加入队尾。
2. 出队 (队首): 当窗口向右滑动时，我们需要检查队首的索引是否已经“过期”（即小于当前窗口的左边界）。如果是，则从队首将其弹出。

这样，在窗口滑动的每一步，队首 q.front() 始终是当前窗口最大值的索引。

4.2.1 核心代码题：滑动窗口最大值

题意概括

给定一个数组 nums 和一个窗口大小 k。有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只能看到在窗口中的 k 个数字。每次窗口向右移动一位。返回一个数组，包含每个窗口中的最大值。

分析

这正是单调队列的模板题。我们将使用一个 deque 来维护一个单调递减的索引队列。

C++ 核心代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// v: 输入数组, k: 窗口大小
vector<int> win(vector<int>& v, int k) {
    int n = v.size();
    if (n < k || k == 0) return {};
    
    vector<int> ans;
    deque<int> q; // 存储索引，保持单调递减

    for (int i = 0; i < n; ++i) {
        // 1. 移除队首的过期索引
        if (!q.empty() && q.front() <= i - k) {
            q.pop_front();
        }

        // 2. 从队尾移除比当前元素小的，以维持单调性
        while (!q.empty() && v[q.back()] <= v[i]) {
            q.pop_back();
        }

        // 3. 将当前索引加入队尾
        q.push_back(i);

        // 4. 当窗口形成后，记录结果
        if (i >= k - 1) {
            ans.push_back(v[q.front()]);
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> v = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> res = win(v, k);
    for (int x : res) {
        cout << x << " ";
    }
    cout << endl; // 输出: 3 3 5 5 6 7
    return 0;
}

• 复杂度分析：同样地，每个元素的索引最多入队和出队一次。时间复杂度为 $O(N)$。空间复杂度为 $O(k)$，因为双端队列中最多存储 k 个索引。

4.3 用栈模拟队列

这是一个经典的笔试题，旨在考察对两种数据结构本质的理解。

题意概括

使用两个栈实现一个队列，要求支持 push 和 pop 操作。

分析

一个栈是 LIFO，而队列是 FIFO。关键在于如何利用栈的“逆序”特性来抵消一次，从而实现 FIFO。

我们可以使用两个栈：s_in 和 s_out。

• push (入队): 所有新元素一律压入 s_in。
• pop (出队):
  1. 首先检查 s_out 是否为空。
  2. 如果 s_out 不为空，直接从 s_out 弹出栈顶元素即可。因为 s_out 中的元素已经是正确的出队顺序。
  3. 如果 s_out 为空，则将 s_in 中的所有元素逐一弹出，并压入 s_out。这个“倾倒”操作会把 s_in 中的元素顺序完全逆转，从而变成了正确的出队顺序。完成倾倒后，再从 s_out 弹出栈顶元素。

C++ 核心代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct MyQueue {
    stack<int> sin, sout;

    void push(int x) {
        sin.push(x);
    }

    int pop() {
        if (sout.empty()) {
            // 从 sin 向 sout 倾倒
            while (!sin.empty()) {
                sout.push(sin.top());
                sin.pop();
            }
        }
        int val = sout.top();
        sout.pop();
        return val;
    }
    
    int front() {
        if (sout.empty()) {
            while (!sin.empty()) {
                sout.push(sin.top());
                sin.pop();
            }
        }
        return sout.top();
    }
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    MyQueue q;
    q.push(1);
    q.push(2);
    cout << q.pop() << endl; // 输出 1
    q.push(3);
    cout << q.pop() << endl; // 输出 2
    cout << q.pop() << endl; // 输出 3
    return 0;
}

• 复杂度分析：
  • push 操作永远是 $O(1)$。
  • pop 操作的复杂度看起来不稳定。有时是 $O(1)$ (当 s_out 非空)，有时是 $O(N)$ (当需要倾倒时)。但是，每个元素一生中最多只会被“倾倒”一次（从 s_in 到 s_out）。因此，如果我们执行 N 次操作，总的时间复杂度是 $O(N)$。平摊到每次操作上，其均摊时间复杂度为 $O(1)$。

第五章：底层实现

虽然在竞赛中我们几乎总是使用 STL，但理解栈和队列的底层实现有助于我们建立更深刻的认知。最常见的底层实现是基于数组。

5.1 数组模拟栈

用数组模拟栈非常直观。我们需要一个数组和一个指向栈顶的指针（或索引）。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
int stk[MAXN];
int tt = -1; // tt (top) 指向栈顶元素，-1 表示栈空

void push(int x) {
    stk[++tt] = x;
}

void pop() {
    --tt;
}

int top() {
    return stk[tt];
}

bool empty() {
    return tt == -1;
}

• 优点：实现简单，内存连续，缓存友好。
• 缺点：大小固定。如果预估大小不准，可能导致溢出或空间浪费。

5.2 数组模拟循环队列

如果用普通数组模拟队列，pop 操作（队首指针后移）会浪费数组前部的空间。当队尾指针到达数组末端时，即使数组前面有很多空位，也无法再入队，这被称为“假溢出”。

循环队列通过将数组看作一个环来解决此问题。我们使用取模运算 % 来实现“环”的效果。

我们需要两个指针：hh (head) 指向队首，tt (tail) 指向队尾的下一个位置。

• 队空条件：hh == tt
• 队满条件：(tt + 1) % MAXN == hh (浪费一个空间来区分队满和队空)
• 入队：q[tt] = x; tt = (tt + 1) % MAXN;
• 出队：hh = (hh + 1) % MAXN;

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
int q[MAXN];
int hh = 0, tt = 0; // hh: 队首, tt: 队尾的后一个位置

void push(int x) {
    q[tt++] = x;
    if (tt == MAXN) tt = 0; // 循环
}

void pop() {
    hh++;
    if (hh == MAXN) hh = 0; // 循环
}

int front() {
    return q[hh];
}

bool empty() {
    return hh == tt;
}

这种朴素的写法在 tt 或 hh 到达 MAXN 时折返，同样可以工作。使用模运算的写法更为常见和统一。理解循环队列是数据结构课程中的一个重要环节。