目录
一、用栈实现队列
二、用队列实现栈
三、有效的括号
四、删除字符串中的所有相邻重复项
五、逆波兰表达式求值
六、滑动窗口最大值
七、前 K 个高频元素
一、用栈实现队列
232. 用栈实现队列 - 力扣（LeetCode）
https://leetcode.cn/problems/implement-queue-using-stacks/description/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
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 falseclass MyQueue {
public:// 定义栈stack<int> Instack;stack<int> Outstack;MyQueue() {}void push(int x) {Instack.push(x);}int pop() {if (Outstack.empty()) {// 输出栈为空while (!Instack.empty()) {Outstack.push(Instack.top());Instack.pop();}}int re = Outstack.top();Outstack.pop();return re;}int peek() {// 使用已有函数int re = this->pop();Outstack.push(re);return re;}bool empty() {return (Instack.empty() && Outstack.empty());}
};/*** 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. 用队列实现栈 - 力扣（LeetCode）https://leetcode.cn/problems/implement-stack-using-queues/description/
请你仅使用两个队列实现一个后入先出（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(); // 返回 Falseclass MyStack {
public:queue<int> Inqueue; // 单队列MyStack() {}void push(int x) {Inqueue.push(x);}int pop() {for (int i = 0; i < Inqueue.size() - 1; i++) {Inqueue.push(Inqueue.front());Inqueue.pop();}int res = Inqueue.front();Inqueue.pop();return res;}int top() {return Inqueue.back();}bool empty() {return Inqueue.empty();}
};/*** 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. 有效的括号 - 力扣（LeetCode）https://leetcode.cn/problems/valid-parentheses/description/
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入: "()"
输出: true示例 2:
输入: "()[]{}"
输出: true示例 3:
输入: "(]"
输出: false示例 4:
输入: "([)]"
输出: false示例 5:
输入: "{[]}"
输出: true思路：
本题遍历时存在三种情况：
第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以 return false
第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以 return false
第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
class Solution {
public:bool isValid(string s) {stack<char> str;for (int i = 0; i < s.length(); i++) {if (s[i] == '(') str.push(')');else if (s[i] == '{') str.push('}');else if (s[i] == '[') str.push(']');// 遍历的过程中栈已经为空，或者不匹配else if (str.empty() || s[i] != str.top()) return false;else str.pop();}return str.empty();}
};四、删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
给出由小写字母组成的字符串
s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在
s上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。class Solution {
public:string removeDuplicates(string S) {string result;for(char s : S) {if(result.empty() || result.back() != s) {result.push_back(s);}else {result.pop_back();}}return result;}
};五、逆波兰表达式求值
150. 逆波兰表达式求值 - 力扣（LeetCode）https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
给你一个字符串数组
tokens，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9示例 2：
输入：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
= 22class Solution {
public:int evalRPN(vector<string>& tokens) {stack<long long> record;for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = record.top(); record.pop();long long num2 = record.top(); record.pop();if (tokens[i] == "+") record.push(num2 + num1);if (tokens[i] == "-") record.push(num2 - num1);if (tokens[i] == "*") record.push(num2 * num1);if (tokens[i] == "/") record.push(num2 / num1);}else {record.push(stoll(tokens[i]));}}return record.top();}
};六、滑动窗口最大值
239. 滑动窗口最大值 - 力扣（LeetCode）https://leetcode.cn/problems/sliding-window-maximum/description/
给你一个整数数组
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 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7示例 2：
输入：nums = [1], k = 1
输出：[1]思路：
这是使用单调队列的经典题目。
队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列。
设计单调队列的时候，pop 和 push操作要保持如下规则：
- pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要问 que.front() 就可以返回当前窗口的最大值。
具体的请查看网站：代码随想录 (programmercarl.com)
class Solution {
private:class MyQueue { //单调队列（从大到小）public:deque<int> que; // 使用deque来实现单调队列void pop(int value) {// 如果弹出的数值等于队列出口元素的数值，则弹出if (!que.empty() && value == que.front()) {que.pop_front();}}void push(int value) {// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出// 这样就保持了队列里的数值是单调从大到小的了while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}int front() {// front为当前队列里的最大值return que.front();}
};public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;// 先将前 k 的元素放进队列for (int i = 0; i < k; i++) { que.push(nums[i]);}// result 记录前 k 的元素的最大值result.push_back(que.front()); for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};七、前 K 个高频元素
347. 前 K 个高频元素 - 力扣（LeetCode）https://leetcode.cn/problems/top-k-frequent-elements/description/
给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]示例 2:
输入: nums = [1], k = 1
输出: [1]思路：
这道题目主要涉及到如下三块内容：
- 要统计元素出现频率
- 对频率排序
- 找出前K个高频元素
首先统计元素出现的频率，这一类的问题可以使用map来进行统计。
然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。
缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。
这种场景下，我们只需要维护 k 个 有序的序列 就可以了，所以 使用优先级队列是最优的。
要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
class Solution {
public:struct sortmap {bool operator() (pair<int, int> x, pair<int, int> y) {return x.second > y.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 记录频数unordered_map<int, int> map;for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 排序，小顶堆维护前 k 个 mappriority_queue<pair<int, int>, vector<pair<int, int>>, sortmap> record;for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {record.push(*it);if (record.size() > k) { record.pop();}}vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = record.top().first;record.pop();}return result;}
};![[PTA]7-6 吃火锅](https://i-blog.csdnimg.cn/direct/ae0117be0a704ae98f9462218e3101f0.png)
![[数据集][目标检测]手机识别检测数据集VOC+YOLO格式9997张1类别](https://i-blog.csdnimg.cn/direct/64685cdaf4b34c31838a52310e11cb9f.png)
