栈和队列

栈和队列

exdoubled Lv3
  2025-10-11 17:00 2025-10-11 17:00 Created   2025-10-22 10:37:50 2025-10-22 10:37:50 Updated    1.7k Words  8 Mins  

表达式求值

算术表达式的形式

前缀表达式：<操作符> <操作数> <操作数>

中缀表达式：<操作数> <操作符> <操作数>

后缀表达式：<操作数> <操作数> <操作符>

后缀表达式不需要括号和运算符优先级

中缀表达式转后缀表达式

遍历中缀表达式各个字符

准备一个后缀表达式的答案和辅助栈

对每个运算符设定一个栈外优先级和站内优先级，从左到右结合的运算符这两个相同，从右到左结合的运算符栈外比站内大

  • 为操作数

    直接加入后缀表达式

  • 为操作符

    • 是括号

      左括号直接入栈，右括号辅助栈直到左括号弹出

    • 是运算符

      如果栈空，直接入栈

      如果栈非空，判断栈顶操作符栈内优先级与当前操作符的栈外优先级：

      如果栈顶优先级更低，则该操作符入栈，否则一直出栈加入后缀表达式

最终再把辅助栈中所有操作符加入后缀表达式中

后缀表达式的计算

遍历后缀表达式各个字符

准备一个辅助栈

  • 为操作数：直接入栈
  • 为操作符：连续出栈两次，先出栈，再出栈计算操作符把结果入栈

最后栈中数据即结果

例题

P1175 表达式的转换 - 洛谷

点击查看代码
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <stack>
#include <unordered_map>
#include <cmath>

using namespace std;

unordered_map<char, pair<int, int>> priority = {
    {'+', {1, 1}},
    {'-', {1, 1}},
    {'*', {2, 2}},
    {'/', {2, 2}},
    {'^', {4, 3}}
};
// 栈外优先级，栈内优先级

void prints(string &s, int begin = 0) {
    for (int i = begin; i < s.size(); ++i) {
        cout << s[i] << ' ';
    }
}

int main() {
    string s, ans;
    cin >> s;
    stack<char> st;
    for (char c : s) {
        if (isdigit(c)) {
            ans.push_back(c);

        }
        else if (c == '(') st.push(c);
        else if (c == ')') {
            while (!st.empty() && st.top() != '(') {
                ans.push_back(st.top());
                st.pop();
            }
            if (!st.empty()) st.pop();
        } else {
            while (!st.empty() && st.top() != '(') {
                char top = st.top();
                if (priority[top].second >= priority[c].first) {
                    ans.push_back(top);
                    st.pop();
                } else {
                    break;
                }
            }
            st.push(c);
        }
    }
    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }
    prints(ans);
    cout << endl;

    stack<int> st2;
    for (int i = 0; i < ans.size(); i++) {
        char c = ans[i];
        if (isdigit(c)) {
            st2.push(c - '0');
        }
        else {
            int a = st2.top(); st2.pop();
            int b = st2.top(); st2.pop();
            int res;
            if (c == '+') res = b + a;
            else if (c == '-') res = b - a;
            else if (c == '*') res = b * a;
            else if (c == '/') res = b / a;
            else if (c == '^') res = pow(b, a);
            st2.push(res);

            stack<int> temp;
            while (!st2.empty()) {
                temp.push(st2.top());
                st2.pop();
            }
            while (!temp.empty()) {
                cout << temp.top() << ' ';
                st2.push(temp.top());
                temp.pop();
            }
            prints(ans, i + 1);
            cout << endl;

        }
    }
    return 0;
}

相互实现

两个栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

一个栈保持弹入元素，另一个栈保持弹出元素

点击查看代码
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
class MyQueue {
    stack<int> *s1, *s2;
public:
    MyQueue() {
        s1 = new stack<int>();
        s2 = new stack<int>();
    }

    void push(int x) {
        s1->push(x);
    }

    int pop() {
        peek();
        int res = s2->top();
        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();
    }
};

一个队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

用一个记录栈顶元素，弹出时到栈顶元素之前让队列弹出的元素重新回到队列中，用之前记录栈顶元素的变量当作这样能够记录弹出后的下一个栈顶元素

点击查看代码
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
class MyStack {
    queue<int> *q;
    int tops = 0;
public:
    MyStack() {
        q = new queue<int>();
    }

    void push(int x) {
        q->push(x);
        tops = x;
    }

    int pop() {
        int size = q->size();
        for (int i = 0; i < size - 1; i++) {
            tops = q->front();
            q->pop();
            q->push(tops);
        }
        int res = q->front();
        q->pop();
        return res;
    }

    int top() {
        return tops;
    }

    bool empty() {
        return q->empty();
    }
};

单调栈

用栈实现了一组单调递增/递减的值，即栈中元素具有单调性

一般存角标，也可能存值，存角标能解决存值不能解决的问题

左侧/右侧第一个比更大/更小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> nextGreaterElement(vector<int>& nums) {
    stack<int> s;
    vector<int> result(nums.size(), -1);
    for (int i = nums.size() - 1; i >= 0; --i) {
        while (!s.empty() && s.top() <= nums[i]) {
            s.pop();
        }
        if (!s.empty()) {
            result[i] = s.top();
        }
        s.push(nums[i]);
    }
    return result;
}

503. 下一个更大元素 II - 力扣（LeetCode）

改成循环数组

点击查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n = nums.size();
vector<int> result(n, -1);
stack<int> s;
for (int i = 2 * n - 1; i >= 0; --i) {
	int cur = nums[i % n];
    while (!s.empty() && s.top() <= cur) {
        s.pop();
    }
    if (i < n && !s.empty()) {
        result[i] = s.top();
    }
    s.push(cur);
}
return result;

2454. 下一个更大元素 IV - 力扣（LeetCode）

用两个单调栈即可

点击查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    vector<int> s1; // 第一个更大（存索引）
    vector<int> s2; // 第二个更大（存索引）

    for (int i = 0; i < n; ++i) {
        while (!s2.empty() && nums[s2.back()] < nums[i]) {
            ans[s2.back()] = nums[i];
            s2.pop_back();
        }
        vector<int> tmp;
        while (!s1.empty() && nums[s1.back()] < nums[i]) {
            tmp.push_back(s1.back());
            s1.pop_back();
        }
        while (!tmp.empty()) {
            s2.push_back(tmp.back());
            tmp.pop_back();
        }
        s1.push_back(i);
    }
    return ans;
}

接雨水

42. 接雨水 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int trap(vector<int> &height) {
    stack<int> s;   // 栈中存下标
    int cnt = 0;
    for (int i = 0; i < height.size(); ++i) {
        while (!s.empty() && height[s.top()] < height[i]) {
            int low = height[s.top()];
            s.pop();
            if (s.empty()) break;
            int high = min(height[s.top()], height[i]);
            cnt += (i - s.top()- 1) * (high - low);
        }
        s.push(i);
    }
    return cnt;
}

左侧最远的比其大的元素

维护一个单调递增的栈

每次在栈上二分得到最远的比其大的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> leftMostFarGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    vector<int> s; // 存索引

    for (int i = 1; i <= n; ++i) {
        if (s.empty() || nums[i] < nums[s.back()]) {
            s.push_back(i);
        } else {
            int l = 1, r = s.size(), ansId = 0;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (nums[s[mid]] > nums[i]) ansId = mid, r = mid - 1;
                else l = mid + 1;
            }
            ans[i] = s[ansId];
        }
    }
    return ans;
}

单调队列

用队列实现了一组单调递增/递减的值，即队列中元素具有单调性

一般存角标

滑动窗口最大值

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> q;
    vector<int> ans;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        if (!q.empty() && q.back() == i-k) {
            q.pop_back();
        }
        while (!q.empty() && nums[q.front()] <= nums[i]) {
            q.pop_front();
        }
        q.push_front(i);
        if (i >= k - 1) {
            ans.push_back(nums[q.back()]);
        }
    }
    return ans;
}

对动态规划的优化

单调队列优化 dp - 洛谷专栏

  • Title: 栈和队列
  • Author: exdoubled
  • Created at : 2025-10-11 17:00:00
  • Updated at : 2025-10-22 10:37:50
  • Link: https://github.com/exdoubled/exdoubled.github.io.git/sjjg/sjjg03/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
栈和队列
  1. 表达式求值
    1. 算术表达式的形式
    2. 中缀表达式转后缀表达式
    3. 后缀表达式的计算
  2. 相互实现
    1. 两个栈实现队列
    2. 一个队列实现栈
  3. 单调栈
    1. 左侧/右侧第一个比更大/更小的元素
    2. 接雨水
    3. 左侧最远的比其大的元素
  4. 单调队列
    1. 滑动窗口最大值
  5. 对动态规划的优化