跳到主要内容

算法刷题-栈与队列

232. 用栈实现队列​

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

实现 MyQueue 类：

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

思路​

开两个栈in和out，in负责加入元素，out负责弹出元素

  • 入队：将元素塞入in中
  • 出队，如果out为空，那么就把in中元素一个一个弹出塞到out中，这时候元素就会和刚加入的时候相反，满足队列的要求。然后再从out中弹出元素
  • peek：就是先让out顶部元素出队，然后入队，这样就不会删除元素，但是可以获取到栈顶的值
  • empty：判断in和out都为空，那么说明队列就是空的

代码​

class MyQueue {
public:
    stack<int> in;
    stack<int> out;
    MyQueue() {

    }
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        if(out.empty()){
            while(!in.empty()){
                auto t=in.top();
                in.pop();
                out.push(t);
            }
        }
        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();
    }
};

/**
 * 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 。

思路​

q1作为存储元素的队列，q2作为备份 删除元素的时候先把前n-1个元素放到q2里面，再删去一个元素 然后再把q2赋值给q1,再把q2清空

代码​

class MyStack {
public:
    queue<int> q1,q2;
    MyStack() {

    }
    
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        auto t=q1.back();
        int sz=q1.size();
        sz--;
        while(sz--){
            q2.push(q1.front());
            q1.pop();
        }
        q1.pop();
        q1=q2;
        while(q2.size()) q2.pop();
        return t;
    }
    
    int top() {
        return q1.back();
    }
    
    bool empty() {
        return q1.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. 有效的括号​

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

有效字符串需满足：

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

思路​

使用一个栈记录左括号， 扫描整个字符串，

  • 如果是左括号就加入到栈中
  • 如果是右括号，那就看栈顶元素能否匹配，不能就是不符合题意

代码​

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(char c:s){
            if(c=='('||c=='{'||c=='[') stk.push(c);
            else{
                bool ok=0;
                if(stk.empty()) return false;
                if(c==')'&&stk.top()=='(') stk.pop(),ok=1;
                if(c=='}'&&stk.top()=='{') stk.pop(),ok=1;
                if(c==']'&&stk.top()=='[') stk.pop(),ok=1;
                if(!ok) return false;
            }
        }
        cout<<stk.size()<<endl;
        if(stk.empty()) return true;
        return false;
    }
};

``

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

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

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

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

思路​

用栈记录元素，遍历整个字符串， 如果当前元素和栈顶元素相同，那么就将栈顶元素删除，否则就把当前元素加入到栈中。

代码​

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

150. 逆波兰表达式求值​

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

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

思路​

逆波兰表达式：是一种后缀表达式,好处就是适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

  1. 创建一个空栈来存储操作数。
  2. 遍历逆波兰表达式中的每个元素（字符串）。
  3. 对于每个元素，进行以下操作：
    • 如果它是一个操作数（即数字），则将其转换为整数并推入栈中。
    • 如果它是一个操作符（+、-、*、/），则从栈中弹出两个操作数，执行相应的运算，并将结果推回栈中。
  4. 遍历完成后，栈中仅剩一个元素，即整个表达式的结果。

代码​

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> sk;
        for(string s:tokens){
            if(s=="+"||s=="-"||s=="*"||s=="/"){
                long long a=sk.top();
                sk.pop();
                long long b=sk.top();
                sk.pop();
                if(s=="+") sk.push(a+b);
                if(s=="-") sk.push(b-a);
                if(s=="*") sk.push(a*b);
                if(s=="/") sk.push(b/a);
            }else{
                sk.push(stoll(s));
            }
        }
        return sk.top();
    }
};

239. 滑动窗口最大值​

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

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

思路​

在C++中，可以使用multiset这种数据结构作为单调队列

多重集合(multiset) 用以有序地存储元素的容器。允许存在相等的元素。

随着窗口的移动，每次将窗口的头元素加入到multiset中，并且删除尾元素，multiset的*rbegin() 就是整个窗口的最大值

代码​

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        multiset<int> st;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            if (i >= k) st.erase(st.find(nums[i - k]));
            st.insert(nums[i]);
            if (i >= k - 1) ans.push_back(*st.rbegin());
        }
        return ans;
    }
};

347. 前 K 个高频元素​

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

思路​

先使用map记录每个元素出现的频率，然后把map转为vector，再对vector进行排序，调用自定义排序函数，根据第二个元素的大小进行排序，然后再取出前k大大元素。

代码​

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> m;
        for(int x:nums) m[x]++;
        vector<pair<int,int>> t;
        for(auto [x,y]:m) t.push_back({x,y});
        sort(t.begin(),t.end(),[&](pair<int,int> a,pair<int,int> b){
            return a.second>b.second;
        });
        vector<int> res;
        for(int i=0;i<k;i++) res.push_back(t[i].first);
        return res;
    }
};
0%