算法学习代码随想录算法数据结构栈队列单调队列优先队列堆

栈与队列 - 代码随想录

Mr.L2026-04-03

栈与队列

栈与队列刷题记录，基于代码随想录整理，重点关注括号匹配、表达式求值、单调队列和优先队列等常见题型。

232 用栈实现队列（输入栈 + 输出栈）
225 用队列实现栈（队列 / 双端队列模拟）
20 有效的括号（栈匹配）
1047 删除相邻重复项（栈消消乐）
150 逆波兰表达式求值（操作数栈）
239 滑动窗口最大值（单调队列）
347 前 K 个高频元素（小顶堆）

232. 用栈实现队列

问题描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

思路

使用栈来模拟队列的行为，如果仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

如果进栈和出栈都为空的话，说明模拟的队列为空了。

代码

class MyQueue {
public:
    stack<int> st_In;
    stack<int> st_Out;
    MyQueue() {
        
    }
    
    void push(int x) {
        st_In.push(x);
    }
    
    int pop() {
        if(st_Out.empty()){
            while(!st_In.empty()){
                int tmp = st_In.top();
                st_In.pop();
                st_Out.push(tmp);
            }
        }
        int x = st_Out.top();
        st_Out.pop();
        return x;
    }
    
    int peek() {
        int tmp = this->pop();
        st_Out.push(tmp);
        return tmp;
    }
    
    bool empty() {
        if(st_In.empty() && st_Out.empty()) return true;
        else return false;
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

225. 用队列实现栈

问题描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

**进阶：**你能否仅用一个队列来实现栈。

思路

队列模拟栈，其实一个队列就够了。队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。

或者一个简单的方式直接使用双向队列 deque

代码

class MyStack {
public:
    deque<int> dq;
    MyStack() {
        
    }
    
    void push(int x) {
        dq.push_back(x);
    }
    
    int pop() {
        if(!dq.empty()){
            int res = dq.back();
            dq.pop_back();
            return res;
        }
        return 0;
    }
    
    int top() {
        if(dq.empty()) return 0; 
        int res = pop();
        dq.push_back(res);
        return res;
    }
    
    bool empty() {
        if(dq.empty()) return true;
        return false;
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

20. 有效的括号

问题描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

示例 5：

**输入：**s = “([)]”

**输出：**false

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

思路

三种情况：

字符串左括号多余，不匹配；
字符串右括号多余，不匹配；
括号无多余，但类型不匹配；

代码

class Solution {
public:
    bool isValid(string s) {
        if(s.size() == 0) return true;
        stack<char> st;
        for(auto c:s){
            if(c=='(' || c=='{' || c=='[') st.push(c);
            else if(st.empty()) return false;  //右括号多余
            // 括号类型不匹配
            else if(c==')' && st.top()!='(') return false;
            else if(c=='}' && st.top()!='{') return false;
            else if(c==']' && st.top()!='[') return false;
            else{
                st.pop();
            }
        }
        // 左括号多余
        if(!st.empty()) return false;
        return true;
    }
};

1047. 删除字符串中的所有相邻重复项

问题描述

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= s.length <= 105
s 仅由小写英文字母组成。

代码

class Solution {
public:
    string removeDuplicates(string s) {
        string res="";
        stack<char> st;
        for(auto c:s){
            if(st.empty()) st.push(c);
            else if(!st.empty() && st.top() == c){
                st.pop();
            }else{
                st.push(c);
            }
        }
        while(!st.empty()){
            res+=st.top();
            st.pop();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

150. 逆波兰表达式求值

问题描述

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

1
2
3

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

1
2
3

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

1 <= tokens.length <= 104
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto s: tokens){
            if(s=="+" || s=="-" || s=="*" || s=="/"){
                int n1 = st.top();
                st.pop();
                int n2 = st.top();
                st.pop();
                int tmp;
                if(s == "+") tmp = n2+n1;
                else if(s == "-") tmp = n2-n1;
                else if(s == "*") tmp = n2*n1;
                else if(s == "/") tmp = n2/n1;
                st.push(tmp);
            }else{
                st.push(stoi(s));
            }
        }
        return st.top();
    }
};

239. 滑动窗口最大值

问题描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

1 2	输入：nums = [1], k = 1 输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

思路

本题中 队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

这个维护元素单调递减的队列叫做单调队列，即单调递减或单调递增的队列。

动手模拟，什么情况下入队列？什么时候把队列最前面的元素弹出，维持窗口内的元素坐标？队列怎么按照从大到小排列？

先判断当前的窗口大小，若大于 k，则 pop 最前面的元素，维持窗口大小为 k;
如果队列末尾的元素小于当前 nums[i], 则弹出队列末尾该元素，直至从大到小排列；
判断当前的窗口大小是否满足 k，如果满足，则记录当前队列的结构即可；

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        vector<int> res;
        deque<int> dq;
        for(int i=0;i<len;i++){
            if(!dq.empty() && dq.front() <= i-k) dq.pop_front();
            while(!dq.empty() && nums[i]>=nums[dq.back()]) dq.pop_back();
            dq.push_back(i);
            if(i-k+1>=0) res.push_back(nums[dq.front()]);
        }
        return res;
    }
};

347. 前 K 个高频元素

问题描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

**输入：**nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

**输入：**nums = [1], k = 1

输出：[1]

示例 3：

**输入：**nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

**进阶：**你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

思路

这道题目主要涉及到三块内容：

要统计元素出现频率
对频率排序
找出前 K 个高频元素

首先统计元素出现的频率，可以使用 map 进行统计。

然后是对频率进行排序，这里可以使用一种容器适配器就是优先级队列 , 本质上是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列，默认情况下 priority_queue 利用 max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

priority_queue（优先级队列）底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

为什么不用快排呢?
使用快排要将 map 转换为 vector 的结构，然后对整个数组进行排序
而这种场景下，我们只需要维护 k 个有序的序列就可以了，所以使用优先级队列是最优的。

因为要统计最大前k个元素，我们可以使用小顶堆，每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

代码

class Solution {
public:
    class mycomparsion{
    public:
        bool operator()(const pair<int,int>& left, const pair<int,int>& right){
            return left.second>right.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res; 
        // 统计每个元素的频率
        unordered_map<int,int> mp;
        for(auto num:nums){
            mp[num]++;
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparsion> q;
        for(auto& it:mp){
            q.push(it);
            if(q.size()>k) q.pop();
        }
        while(!q.empty()){
            res.push_back(q.top().first);
            q.pop();
        }
        return res;
    }
};