C++ Stack 与 Queue 核心用法：基础操作、场景与实战

2.4 基础用法演示

void test_stack() {
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(3);
    st.emplace(4);
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
}

int main() {
    test_stack();
    return 0;
}

三、Queue（队列）：先进先出（FIFO）的容器

3.1 核心特性

• 访问规则：从'队尾'添加元素，从'队头'删除元素（最先入队的元素最先出队）。
• 适用场景：任务调度（如打印队列）、消息队列、广度优先搜索（BFS）等。

参考文档：queue - C++ Reference

3.2 头文件与定义

#include <queue>
using namespace std;

// 定义队列：默认底层依赖 deque 实现
queue<int> q;

// 可指定底层容器（如 list，不建议用 vector，因 vector 头删效率低）
queue<int, list<int>> q_l; // 基于 list 的队列

3.3 常用接口全解析

3.4 基础用法演示

void test_queue() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.emplace(4);
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

int main() {
    test_queue();
    return 0;
}

四、实战练习题

4.1 最小栈

题目链接：

155. 最小栈 - 力扣（LeetCode）

题目描述：

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

C++ 算法代码：

class MinStack {
public:
    MinStack() {
        // 可以啥都不写，甚至可以删掉
        // 会去调这个自定义类型的默认构造
    }

    void push(int val) {
        _st.push(val);
        if (_minst.empty() || _minst.top() >= val) {
            _minst.push(val);
        }
    }

    void pop() {
        if (_minst.top() == _st.top()) {
            _minst.pop();
        }
        _st.pop();
    }

    int top() {
        return _st.top();
    }

    int getMin() {
        return _minst.top();
    }

private:
    stack<int> _st;
    stack<int> _minst;
};
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

思路解析： 维护两个栈，主栈 _st 存储所有数据，辅助栈 _minst 存储当前的最小值。每次压入新元素时，如果它小于等于辅助栈顶，也压入辅助栈。弹出时，如果主栈顶等于辅助栈顶，则同时弹出。这样就能保证 getMin() 是 O(1) 时间复杂度。

4.2 栈的压入、弹出序列

题目链接：

栈的压入、弹出序列 - 牛客题霸

题目描述：

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

C++ 算法代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int 整型 vector
     * @param popV int 整型 vector
     * @return bool 布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        int pushi = 0, popi = 0;
        stack<int> st;
        while (pushi < pushV.size()) {
            st.push(pushV[pushi]);
            while (!st.empty() && st.top() == popV[popi]) {
                st.pop();
                popi++;
            }
            pushi++;
        }
        return st.empty();
    }
};

思路解析： 模拟入栈过程。每压入一个元素，就检查是否与弹出序列当前元素匹配。如果匹配，则立即弹出，并移动弹出序列指针。最后如果栈为空，说明是合法的弹出序列。

4.3 逆波兰表达式求值

题目链接：

150. 逆波兰表达式求值 - 力扣（LeetCode）

题目描述：

根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, /。

补充说明：

逆波兰表达式是一种后缀表达式，运算数在前，运算符在后。

C++ 算法代码：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (auto& str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/") {
                // 运算符
                int right = st.top(); st.pop();
                int left = st.top(); st.pop();
                switch (str[0]) {
                    case '+': st.push(left + right); break;
                    case '-': st.push(left - right); break;
                    case '*': st.push(left * right); break;
                    case '/': st.push(left / right); break;
                }
            } else {
                // 运算数
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

思路解析： 遇到数字入栈，遇到运算符则弹出两个数字进行计算，结果再压回栈中。注意减法和除法要注意操作数的顺序（left 是栈顶弹出的第二个，right 是第一个）。

4.4 二叉树的层序遍历

题目链接：

102. 二叉树的层序遍历 - 力扣（LeetCode）

题目描述：

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

C++ 算法代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        int levelSize = 0;
        if (root) {
            q.push(root);
            levelSize = 1;
        }
        vector<vector<int>> vv;
        while (!q.empty()) {
            vector<int> v;
            // 一层一层的出
            while (levelSize--) {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            vv.push_back(v);
            // 现在的 levelSize 等于当前队列的 size
            levelSize = q.size();
        }
        return vv;
    }
};

思路解析： 利用队列的特性，每次处理完当前层的所有节点后，更新下一层的节点数量 levelSize。这样就能准确地将每一层的节点放入单独的 vector 中。

Stack 和 Queue 作为 C++ 标准库中经典的适配器容器，凭借明确的访问规则在各类场景中发光发热。掌握它们的基础操作，再结合实战习题打磨，就能轻松应对算法与业务中的数据管理需求。