力扣刷题总结 栈与队列

2023-12-31 07:14:13

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

一、栈和队列的基础知识

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

?二、题目实战

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

(1)232.用栈实现队列

232. 用栈实现队列icon-default.png?t=N7T8https://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. 用队列实现栈icon-default.png?t=N7T8https://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;
    //还要清空q1
    while(!q1.empty())
    {
        q1.pop();
    }
    return res;
    }

(3)20.有效的括号

20. 有效的括号icon-default.png?t=N7T8https://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. 删除字符串中的所有相邻重复项icon-default.png?t=N7T8https://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);//如果为空或者不相等直接push
        else st.pop();//否则pop
    }
//输出操作,栈先进后出,所以最好输出要反过来
    string result = "";
    while(!st.empty()){
        result += st.top();
        st.pop();
    }
    reverse(result.begin(),result.end());
    return result;
    }
};

(5) 150.逆波兰表达式求和

150. 逆波兰表达式求值icon-default.png?t=N7T8https://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. 滑动窗口最大值icon-default.png?t=N7T8https://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操作时候就会被顶出。

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

文章来源:https://blog.csdn.net/showy0/article/details/134981960
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。