力扣刷题总结栈与队列

🔥博客主页： A_SHOWY
🎥系列专栏：力扣刷题总结录数据结构云计算数字图像处理力扣每日一题_

一、栈和队列的基础知识

队列是先进先出，栈是先进后出。同时二者都是容器适配器而不是容器。

二、题目实战

232.用栈实现队列	easy	基础操作
225.用队列实现栈	easy	基础操作
20.有效的括号	easy	碰到左括号存栈里，等右括号匹配
1047.删除字符串中所有的重复项	mid	匹配相邻元素消除
150.逆波兰式求和	mid	字符转换整型
239.滑动窗口的最大值	hard	双值队列的应用，巧妙

（1）232.用栈实现队列

232. 用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/我们知道栈是先进先出，队列是先进后出。所以要用栈来实现队列，需要一个输入栈一个输出栈（按输入的顺序倒叙存放）。这个题目有四个操作

1.第一个操作很容易就是一个入队列的操作和入栈一样

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

2.第二个操作是出队列的操作，这个操作就有一定的难度，我们需要一个输入栈和一个输出栈，当输出栈为空的时候，我们需要把输入栈的所有元素全部弹出到输出栈，这样从输出栈进行pop这个顺序满足先入先出。输出栈弹出的第一个元素就我们的结果。

  int pop() {//当out栈为空的时候if(stkOut.empty()){while(!stkIn.empty()){//把所有in栈里面的东西全部弹出给out，否则顺序不对stkOut.push(stkIn.top());stkIn.pop();}}int res = stkOut.top();stkOut.pop();return res;

3.第三个操作是返回队列开头的元素，我们发现和第二个操作是大量重复代码相似的操作，所以我们可以直接复制第二问的代码，但是我们专业来说可以用this->来直接调用同一个类中的函数，调用结束后发现多弹出一个元素，我们再push回去就可以了。

int peek() {//学会运用this->,这里发现和pop操作的代码大同小异int res = this -> pop();//发现这里多弹出了stkOut.push(res);return res;}

第四个操作是判断队列是否为空，直接判断入栈和出栈相与为空，说明两个栈都没有元素时为空既可。

 bool empty() {return stkIn.empty() && stkOut.empty();}

（2）225.用队列实现栈

225. 用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/这道题目其实就是用一个队列来实现栈，具体思路和上一题有很多相似之处。

1.首先第一个问题还是一个push操作，栈和队列的push操作是一样的，所以可以直接push

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

2.第二个pop操作还是整个题目最需要思考的。当一个队列的时候，我们的整体思路是把size-1个元素取出来然后重新push进入队列。再pop队列front的元素一次。

int pop() {int size = q.size();size--;while(size--){q.push(q.front());q.pop();}int res = q.front();q.pop();return res;}

3.第三个操作直接使用back就可以解决

    int top() {return q.back();}

4.第四个操作，空值操作

bool empty() {return q.empty();}

可以看出来整体思路还是比较简单的，除了pop操作需要多思考一下，其他小问的要求容易。

拓展：如果要求使用两个队列来满足栈的pop操作

将第一个队列的size-1个元素移动到第二个队列中，留下的最后一个元素就是要返回的值，再把第二个队列中的元素移动到第一个队列中即可。核心思想不变。但是记住要把q1最后清空。

 int pop() {//  int size = q.size();//  size--;//  while(size--){//      q.push(q.front());//      q.pop();//  }//  int res = q.front();//  q.pop();//  return res;int size = q.size();size--;while(size--){q1.push(q.front());q.pop();}int res = q.front();q.pop();q = q1;//还要清空q1while(!q1.empty()){q1.pop();}return res;}

（3）20.有效的括号

20. 有效的括号https://leetcode.cn/problems/valid-parentheses/栈非常适合做这种匹配的问题，有一个小技巧，就是碰到左括号，就存一个右括号到栈里，再进行匹配。

class Solution {
public:bool isValid(string s) {stack<char> st;for(int i = 0; i< s.size();i++){if(s[i] == '(') st.push(')');else if(s[i] == '{') st.push('}');else if(s[i] == '[') st.push(']');//第二种else if(st.empty() || s[i] != st.top()) return false; else st.pop();}return (st.empty());}
};

（4）1047.删除字符串中所有重复项

1047. 删除字符串中的所有相邻重复项https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/ 本题要删除相邻相同元素，相对于20. 有效的括号 (opens new window)来说其实也是匹配问题，20. 有效的括号是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作。用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。这种消除问题也是栈的经典题目。

class Solution {
public:string removeDuplicates(string s) {stack<char> st;for(char x : s){if(st.empty() || x != st.top()) st.push(x);//如果为空或者不相等直接pushelse st.pop();//否则pop}
//输出操作，栈先进后出，所以最好输出要反过来string result = "";while(!st.empty()){result += st.top();st.pop();}reverse(result.begin(),result.end());return result;}
};

（5） 150.逆波兰表达式求和

150. 逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/

本题也是一道和栈有关的题目，要求求逆波兰式的求值，对于这道题目，我们可以考虑到当在一个栈中栈顶为符号的时候，就从栈顶拿出来两个元素进行符号操作再放回栈顶。

需要注意的是这道题给的范围定义的long long的栈,最后字符串转换的时候要用long long的stoll

注意本题给的是tokens数组中全部都是字符串，所以在push的时候需要进行转化

stoi 函数：将字符串转成 int 整数。 stol 函数：将字符串转成 long 整数。 stoll 函数：将字符串转成 long long 整数。

class Solution {
public:int evalRPN(vector<string>& tokens) {
stack<int> st;for(int i = 0 ; i < tokens.size(); i++){if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")      {int nums1 = st.top();st.pop();int nums2 = st.top();st.pop();if(tokens[i] == "+") st.push(nums2 + nums1);if(tokens[i] == "-") st.push(nums2 - nums1);if(tokens[i] == "*") st.push(nums2 * nums1);if(tokens[i] == "/") st.push(nums2 / nums1);}else st.push(stoi(tokens[i]));}return st.top();}
};

（6）239.滑动窗口的最大值

239. 滑动窗口最大值https://leetcode.cn/problems/sliding-window-maximum/这道题目是一个hard题目，思路确实很难，对于本题，我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。

我们用到的自定义的队列是一个deque，双向队列，也就是左右都能进出。我们先考虑push函数，在我们每次push的时候，当要push的元素比前面的都大时，把前面的元素全部删除，因为我们不需要维护所有的元素，我们只需要保证最大元素即可，可能有人就迷惑了，你把前面的元素都卷走了，那pop操作怎么办。pop操作就更为巧妙了，当要pop的元素和队列的front相等的时候，才是真正要pop 的时候。但是对于push和pop函数队列操作不要忘记队列不为空的判断，front函数就简单了，直接返回队列的front就可以。

在实现函数部分，先把前k个元素push进队列，找到最大的值，然后从第k+1个元素进行push，pop，front操作。最后放到数组里面返回。

class Solution {
private:
class MyQueue{
public:deque<int> que;void pop(int value){if(!que.empty() && que.front() == value){que.pop_front();} }void push(int value){while(!que.empty() && value > que.back()){que.pop_back();}que.push_back(value);}int front(){return que.front();}
};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> res;for(int i = 0 ; i < k; i++){que.push(nums[i]);//先把前k个push进去}res.push_back(que.front());//记录前k个元素的最大值for(int i = k; i < nums.size();i++){que.pop(nums[i-k]);que.push(nums[i]);res.push_back(que.front());}
return res;}
};

这道题目的重点是我们要确定维护的是大的元素，前面的元素较小在push操作时候就会被顶出。

本期总结了道题目，后续如果有相关题目会继续总结添加。