栈

1.AcWing828.模拟栈

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
#include <iostream>
using namespace std;

const int MAX = 100010;

typedef struct {
	int data[MAX];
	int top;
} Stack;

Stack stack1;

void stack_push(Stack &stack, int x) {
	stack.data[stack.top] = x;
	stack.top++;
}

int stack_pop(Stack &stack) {
	int ret = stack.data[stack.top];
	stack.top--;
	return ret;
}

int stack_top(Stack &stack) {
	return stack.data[stack.top - 1];
}

bool stack_empty(Stack &stack) {
	if (stack.top > 0) return false;
	return true;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int m; cin >> m;
	string opt;
	int x;
	int top;
	while (m--) {
		cin >> opt;
		if (opt == "push") {
			cin >> x;
			stack_push(stack1, x);
		} else if (opt == "pop") {
			stack_pop(stack1);
		} else if (opt == "empty") {
			stack_empty(stack1) ? cout << "YES" << endl : cout << "NO" << endl;
		} else {
			top = stack_top(stack1);
			cout << top << endl;
		}
	}
	//for (int i = 0; i < stack1.top; ++i) cout << stack1.data[i] << " ";
	return 0;
}

2.Acwing3302.表达式求值

利用中缀表达式的性质，用一个栈达到递归的结果，实现中缀表达式计算：

image-20230331234023819

  1. 如何判断某棵子树被遍历完？向上走表示已经被遍历完成，向下走表示没有被遍历完成（运算符优先级）。
  2. 如何处理左右括号？如果遇到左括号不做任何运算，遇到右括号则从右向左（运算符优先级递增）将所有运算符操作出来。
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
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> nums;
stack<char> op;

//用末尾的运算符 操作末尾的两个数
void eval() {
    int x;
    auto b = nums.top(); nums.pop();
    auto a = nums.top(); nums.pop();
    auto c = op.top(); op.pop();
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    nums.push(x);
}

//中缀表达式运算顺序
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
    //1.定义哈希表中各个运算符的优先级
    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
	string str; cin >> str;
    for (int i = 0; i < str.size(); ++i) {
        auto c = str[i];
        if (isdigit(c)) {
            int x = 0;
            int j = i;
            while (j < str.size() && isdigit(str[j])) {
                /* 将str中连续的数字字符转为int类型 */
                x = x * 10 + str[j] - '0';
                j++;
            }
            i = j - 1;
            nums.push(x);
        } else if (c == '(') {
            op.push(c);
        } else if (c == ')') {
            while (op.top() != '(') eval();//将栈中所有的运算符从右向左操作一遍
            op.pop();
        } else {
            while (op.size() && pr[op.top()] >= pr[c]) eval();
            op.push(c);
        }
    }
	while (op.size()) eval();//将所有没有操作完成的运算符从右向左操作一遍
    cout << nums.top() << endl;
	return 0;
}

3.AcWing830.单调栈

（1）暴力法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

const int MAX = 100010;

int arr[MAX], n;

int main() {
    int flag;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> arr[i];
    for (int i = 0; i < n; ++i) {
        flag = 1;
        for (int j = i - 1; j >= 0; --j) {
            if (arr[j] < arr[i]) {
                cout << arr[j] << " ";
                flag = 0;
                break;
            }
        }
        if (flag) cout << "-1 ";
    }
    return 0;
}

（2）单调栈：

  1. 在暴力做法中，随着指针i向右移动的过程中，可以用一个栈来存储指针i左边的所有元素，
  2. 由题意求序列中左边距离最近的、且小的数字，可知当存在am > an且m < n时，输出的结果一定是an 则am 无用、可直接删除。
  3. 在将栈中所有逆序的元素删除之后，栈中的元素一定是单调的（单调栈）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;

const int MAX = 100010;

int base[MAX], top;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n; int x;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        while (top && base[top - 1] >= x) top--;//维护这个单调栈
        if (top) cout << base[top - 1] << " ";//栈空
        else cout << -1 << " ";//栈非空
        base[top++] = x;
    }
    return 0;
}