算法-栈与队列

算法题-栈与队列相关

栈与队列

两个基础函数模板：用栈实现队列 用队列实现栈

　　‍

用栈实现队列

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    /** Initialize your data structure here. */
    MyQueue() {

    }
    /** Push element x to the back of queue. */
    void push(int x) {
        stIn.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
        if (stOut.empty()) {
            // 从stIn导入数据直到stIn为空
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    /** Get the front element. */
    int peek() {
        int res = this->pop(); // 直接使用已有的pop函数
        stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
        return res;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

　　‍

用队列实现栈

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MyStack {
public:
    queue<int> que;
    /** Initialize your data structure here. */
    MyStack() {

    }
    /** Push element x onto stack. */
    void push(int x) {
        que.push(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que.size();
        size--;
        while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
        que.pop();
        return result;
    }

    /** Get the top element. */
    int top() {
        return que.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que.empty();
    }
};

　　‍

栈应用

　　32. 最长有效括号 - 力扣（Leetcode）

　　给你一个只包含 '('​ 和 ')'​ 的字符串，找出最长有效（格式正确且连续）括号子串的长度

  • 用栈模拟一遍，将所有无法匹配的括号的位置全部置1
  • 例如: “()(()”的mark为[0, 0, 1, 0, 0]
  • 再例如: “)()((())”的mark为[1, 0, 0, 1, 0, 0, 0, 0]
  • 经过这样的处理后, 此题就变成了寻找最长的连续的0的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        vector<int> mark(s.length());
        for(int i=0;i<mark.size();i++) mark[i]=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(') st.push(i);
            else{
                if(st.empty()) mark[i]=1;
                else st.pop();
            }
        }
        while(!st.empty()){
            mark[st.top()]=1;
            st.pop();
        }
        int res=0;
        int ans=0;
        for(int i=0;i<s.size();i++){
            if(mark[i]){
                ans=0;
                continue;
            }
            ans++;
            res=max(res,ans);
        }
        return res;

    }
};

　　‍

　　‍

优先队列应用

　　 239. 滑动窗口最大值 - 力扣（Leetcode）

　　给你一个整数数组 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       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>> s;
        for(int i=0;i<k;i++) s.emplace(nums[i],i);
        int n=nums.size();
        vector<int> res={s.top().first};
        for(int i=k;i<n;i++){
            s.emplace(nums[i],i);
            while(s.top().second<=i-k) s.pop();
            res.emplace_back(s.top().first);
        }
        return res;
    }
};

　　‍

　　使用deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> s;
        //先放一个窗口的内容，实现按下标严格递减
        for(int i=0;i<k;i++){
            while(!s.empty()&&nums[i]>nums[s.back()]) s.pop_back(); 
            s.push_back(i);
        }
        vector<int> res={nums[s.front()]};
        for(int i=k;i<nums.size();i++){
            while(!s.empty()&&nums[i]>nums[s.back()]) s.pop_back();
            while(!s.empty()&&s.front()<=i-k) s.pop_front();
            s.push_back(i);
            res.push_back(nums[s.front()]);
        }
        return res;
    }
};

　　‍

　　347. 前 K 个高频元素 - 力扣（Leetcode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    static bool mycmp(const pair<int, int>&a, const pair<int, int>&b){
        return a.second>b.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> s;
        for(int i:nums){
            s[i]+=1;
        }
        vector<int> res;
        vector<pair<int,int>> ss(s.begin(),s.end());
        sort(ss.begin(),ss.end(),mycmp);
        for(int i=0;i<k;i++){
            res.push_back(ss[i].first);
        }
        return res;
    }
};

　　‍

算法
#算法
算法-栈与队列
https://shanhainanhua.github.io/2023/08/25/算法-栈与队列/
作者
wantong
发布于
2023年8月25日
许可协议