Tong's Blog

Welcome to my Blog

0%

刷题小知识：队列/栈

发表于 更新于 分类于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

队列主要⽤在 BFS 算法，栈主要⽤在括号相关的问题

队列实现栈以及栈实现队列

相关题目：

  1. ⽤栈实现队列（简单）

  2. ⽤队列实现栈（简单）

队列：先进先出；栈：先进后出

用栈实现队列

双栈实现队列

image-20220315182119191 
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
class MyQueue {
private:
    stack<int> s1;
    stack<int> s2;
public:
    MyQueue() {
    }
    /** 添加元素到队尾 */
    void push(int x) {
        s1.push(x);
    }
    /** 删除队头的元素并返回 */
    int pop() {
        int res = peek();
        s2.pop();
        return res;
    }
    /** 返回队头元素 */
    int peek() {
        if(s2.empty()) {
            while(!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        return s2.top();
    }
    /** 判断队列是否为空 */
    bool empty() {
        return s1.empty() && s2.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
class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    MyStack() {
        
    }
    /** 添加元素到栈顶 */
    void push(int x) {
        q2.push(x);
        while(!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        swap(q1, q2);
    }
    /** 删除栈顶的元素并返回 */
    int pop() {
        int r = q1.front();
        q1.pop();
        return r;
    }
    /** 返回栈顶元素 */
    int top() {
        int r = q1.front();
        return r;
    }
    /** 判断栈是否为空 */
    bool empty() {
        return q1.empty();
    }
}

括号字符串问题

相关题目：

  1. 有效的括号（简单）

  2. 使括号有效的最⼩添加（中等）

  3. 平衡括号串的最少插⼊（中等）

判断合法括号字符串

输⼊⼀个字符串，其中包含[](){}六种括号，判断这个字符串组成的括号是否合法。

每个右括号 ) 的左边必须有⼀个左括号 ( 和它匹配。

解法：使用栈，遇到左括号就⼊栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isValid(string str) {
    stack<char> left;
    for(char c : str) {
        if (c == '(' || c == '[' || c == '{') {
            left.push(c);
        } else { // 字符 c 是右括号
            if (!left.empty() && leftOf(c) == left.top())
                left.pop();
            else 
                // 和最近的左括号不匹配
                return false;
        }
    }
    return left.empty();
}
char leftOf(char c) {
    if (c == ')') return '(';
    if (c == '}') return '{';
    return '[';
}

平衡括号串

输⼊⼀个字符串 s，你可以在其中的任意位置插⼊左括号(或者右括号 )，返回需要⼏次插⼊才能使得 s 变成⼀个合法的括号串

输⼊ s = "())("，算法应该返回 2，因为⾄少需要插⼊两次把 s 变成 "(())()"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minAddToMakeValid(string s) {
    int res = 0; // res 记录插⼊次数
    int need = 0; // need 变量记录右括号的需求量
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            // 对右括号的需求 + 1
            need++; 
        }
        if (s[i] == ')') {
            // 对右括号的需求 - 1\
            need--;
            if (need == -1) {
                need = 0;
                // 需插⼊⼀个左括号
                res++;
            }
        }
    }
    return res + need;
}

单调栈结构

相关题目：

  1. 下⼀个更⼤元素I（简单）

  2. 下⼀个更⼤元素II（中等）

  3. 每⽇温度（中等）

单调栈：每次新元素⼊栈后，栈内的元素都保持有序（单调递增或单调递减）。

一般只用来处理Next Greater Element 问题。

单调栈模板

⽐如：输⼊⼀个数组 nums = [2,1,2,4,3]，返回数组 [4,2,4,-1,-1]。

解释：第⼀个 2 后⾯⽐ 2 ⼤的数是 4; 1 后⾯⽐ 1 ⼤的数是 2；第⼆个 2 后⾯⽐ 2 ⼤的数是 4; 4 后⾯没有⽐ 4 ⼤的数，填 -1；3 后⾯没有⽐ 3 ⼤的数，填 -1。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的数组
    stack<int>  s;
    // 倒着往栈⾥放
    for (int i = nums.size() - 1; i >= 0 ;i++) {
        // 判定个⼦⾼矮
        while(!s.empty() && s.top() <= nums[i]) {
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        s.push(nums[i]);
    }
    return res;
}

每日温度

给定⼀个数组 T，这个数组存放的是近⼏天的天⽓⽓温，你返回⼀个等⻓的数组，计算：对于每⼀天，还要⾄少等多少天才能等到⼀个更暖和的⽓温；如果等不到那⼀天，填 0。

⽐如：输⼊ T = [73,74,75,71,69,76]，返回 [1,1,3,2,1,0]。

解释：第⼀天 73 华⽒度，第⼆天 74 华⽒度，⽐ 73 ⼤，所以对于第⼀天，只要等⼀天就能等到⼀个更暖和的⽓温，后⾯的同理。

解法：单调栈，区别在于需要返回与Next Greater Number 的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> dailyTemperatures(vector<int>& T) {
    vector<int> res(T.size());
    stack<int> s; // 这⾥放元素索引，⽽不是元素
    /* 单调栈模板 */
    for (int i = T.size() - 1; i >= 0; i++) {
        while(!s.empty() && T[s.top()] <= T[i]) {
            s.pop();
        }
        // 得到索引间距
        res[i] = s.empty() ? 0 : (s.top() - i);
        s.push(i); // 将索引⼊栈，⽽不是元素
    }
    return res;
}