第五章 栈与队列

一、用栈实现队列

Leetcode 232

class MyQueue {
public:stack<int> in, out;MyQueue() {}void push(int x) {in.push(x);}int pop() {if (out.empty()) while (!in.empty())out.push(in.top()), in.pop();int res = out.top();out.pop();return res;}int peek() {int res = this->pop();out.push(res);return res;}bool empty() {return in.empty() && out.empty();}
};

二、用队列实现栈

Leetcode 225

两个队列：

class MyStack {
public:queue<int> que1, que2; // que2用于备份que1MyStack() {}void push(int x) {que1.push(x);}int pop() {int cnt = que1.size();cnt -- ;while (cnt -- )que2.push(que1.front()), que1.pop();int res = que1.front();que1.pop();que1 = que2;while (!que2.empty()) que2.pop();return res;}int top() {return que1.back();}bool empty() {return que1.empty();}
};

一个队列：

class MyStack {
public:queue<int> que;MyStack() {}void push(int x) {que.push(x);}int pop() {int cnt = que.size();cnt -- ;while (cnt -- )que.push(que.front()), que.pop();int res = que.front();que.pop();return res;}int top() {return que.back();}bool empty() {return que.empty();}
};

三、有效的括号

Leetcode 20

class Solution {
public:bool isValid(string s) {if (s.size() % 2) return false;stack<char> st;for (int i = 0; i < s.size(); i ++ ) {char c = s[i];if (c == '(') st.push(')');else if (c == '{') st.push('}');else if (c == '[') st.push(']');else if (st.empty() || st.top() != c) return false; // 为空或者不匹配else st.pop(); // 相等}return st.empty();}
};

四、删除字符串中的所有相邻重复项

Leetcode 1047

开辟一个栈：

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

直接使用字符串作为栈：

class Solution {
public:string removeDuplicates(string s) {string res;for (char c: s) if (res.empty() || res.back() != c) res.push_back(c);else res.pop_back();return res;}
};

五、逆波兰表达式求值

Leetcode 150

class Solution {
public:int evalRPN(vector<string>& s) {stack<long long> st;for (int i = 0; i < s.size(); i ++ )if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/") {long long a = st.top(); st.pop();long long b = st.top(); st.pop();if (s[i] == "+") st.push(b + a); if (s[i] == "-") st.push(b - a); // 注意顺序if (s[i] == "*") st.push(b * a);if (s[i] == "/") st.push(b / a);} else st.push(stoll(s[i]));int res = st.top(); st.pop();return res;}
};

六、滑动窗口最大值

Leetcode 239

单调队列经典题目，具体实现看参考文章

这个题目参考文章里面使用了库 deque 方便再前后两端进行操作，但是这里可以直接使用一个数组 $q$ 代替，效率更高，数组 $q$ 的作用是队列中队头和队尾的位置。

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();vector<int> q(n, 0), res;int hh = 0, tt = -1;for (int i = 0; i < n; i ++ ) {if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;while (hh <= tt && nums[q[tt]] <= nums[i]) tt -- ;q[ ++ tt] = i;if (i - k + 1 >= 0) res.push_back(nums[q[hh]]);}return res;}
};

七、前 K 个高频元素

Leetcode 347

使用优先队列（披着队列外衣的堆），如果使用的是大顶堆，每次弹出堆顶最大的一个数，就不能保证题目找出频率最高的 $k$ 个数，而且使用大顶堆每次要对整个堆进行排序，浪费时间。如果是使用小顶堆，每次仅保留 $k$ 个频率最高的元素在堆里面，就需要只对 $k$ 个元素进行排序，节省时间开销。

class Solution {
public:// 小顶堆class mycomparison{public:bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> mp; // <元素，频率>for (int c: nums) mp[c] ++ ;priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que; // 小顶堆for (auto it = mp.begin(); it != mp.end(); it ++ ) {pri_que.push(*it);if (pri_que.size() > k) pri_que.pop();}vector<int> res(k);for (int i = k - 1; i >= 0; i -- )res[i] = pri_que.top().first, pri_que.pop();return res;}
};