【算法基础篇】数组模拟栈、表达式求值、单调栈问题

思路

https://www.acwing.com/problem/content/830/
数组模拟栈：

1. 用top表示栈顶所在的索引。初始时，top = -1。表示没有元素。

2. push x ：栈顶所在索引往后移动一格，然后放入x。st[++top] = x。

3. pop : top 往前移动一格。top–。

4. empty ：top 大于等于 0 栈非空，小于 0 栈空。top == -1 ? “YES” : “NO”

5. query ： 返回栈顶元素。st[top]

AC代码

#include <iostream>

using namespace std;
const int N = 100010;
int stack[N], top = -1;
int m;

int main()
&#123;
    string op;
    cin >> m;
    while (m -- )
    &#123;
        cin >> op;
        if(op == "push") // 压栈
        &#123;
            int x;
            cin >> x;
            stack[++ top] = x;
        &#125;
        else if(op == "pop") // 出栈
        &#123;
            top --;
        &#125;
        else if(op == "empty") // 是否为空
        &#123;
            if(top < 0) cout << "YES" << endl;
            else cout << "NO" << endl;
        &#125;
        else if(op == "query") // 查询栈顶
        &#123;
            cout << stack[top] << endl;
        &#125;
    &#125;
    return 0;
&#125;

习题 表达式计算

思路

https://www.acwing.com/solution/content/40978/

AC代码

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>

using namespace std;

// 定义两个栈 一个数字栈 一个符号栈
stack<int> num;
stack<char> op;

// 优先级表  
unordered_map<char, int> p &#123;&#123;'+', 1&#125;, &#123;'-', 1&#125;, &#123;'*', 2&#125;, &#123;'/', 2&#125;&#125;;

void eval()
&#123;
    int b = num.top(); num.pop();
    int a = num.top(); num.pop();

    int h = op.top(); op.pop();
    if(h == '+') num.push(a + b);
    if(h == '-') num.push(a - b);
    if(h == '*') num.push(a * b);
    if(h == '/') num.push(a / b);
&#125;

int main()
&#123;
    // 读入表达式
    string s;
    cin >> s;

    for(int i = 0; i < s.size(); i ++)
    &#123;
        if(isdigit(s[i]))
        &#123;
            // 如果不止一位数字
            int x = 0, j = i;
            while(j < s.size() && isdigit(s[j]))
            &#123;
                x = x * 10 + s[j] - '0';
                j ++;
            &#125;
            num.push(x);
            i = j - 1;
        &#125;
        else if(s[i] == '(')
        &#123;
            op.push(s[i]);
        &#125;
        else if(s[i] == ')') 
        &#123;
            // 如果是右括号一直计算到左括号
            while(op.top() != '(') eval();
            op.pop();
        &#125;
        else
        &#123;
            // 栈顶操作符比准备压入的操作符优先级高 则先计算
            while(op.size() && p[op.top()] >= p[s[i]]) eval();
            op.push(s[i]);
        &#125;
    &#125;
    while(op.size()) eval();
    cout << num.top() << endl;
    return 0;
&#125;

单调栈问题

问题描述

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

问题分析&实现思路

1. 单调递增栈：在保持栈内元素单调递增的前提下（如果栈顶元素大于要入栈的元素，将将其弹出），将新元素入栈。

2. 单调递减栈：在保持栈内元素单调递减的前提下（如果栈顶元素小于要入栈的元素，则将其弹出），将新元素入栈。

这里转载别人的解释https://www.acwing.com/solution/content/13981/

AC代码

#include <iostream>

using namespace std;
const int N = 100010;
int stack[N], top = -1;

int main()
&#123;
    int n, x;
    scanf("%d", &n);
    while (n -- )
    &#123;
        scanf("%d", &x);
        // 栈不空 并且 栈顶元素大于当前数 则弹出
        while(top != -1 && stack[top] >= x) top --;
        if(top == -1)
            printf("-1 ");
        else
            printf("%d ", stack[top]);
        stack[++ top] = x;
    &#125;
    return 0;
&#125;