栈和队列——相关例题_栈的例题

提示：栈和队列相关知识点见数据结构-栈和队列

一、栈例题——模拟栈

题目描述

实现一个栈，栈初始为空，支持四种操作：

• push x – 向栈顶插入一个数 x。
• pop – 从栈顶弹出一个数。
• empty – 判断栈是否为空。
• query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x ，pop ，empty ，query。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

1 ≤ M ≤ 100000
1 ≤ x ≤ 1e9
所有操作保证合法。

输入样例

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例

5
5
YES
4
NO

具体实现

1. 模板

1.1 代码注解

• 用数组模拟栈。
• 下标从 0 开始或者从 1 开始，依据自身习惯即可。
• 用 top 表示栈顶所在的索引。初始时，top = -1。表示没有元素。
• push x ：栈顶所在索引往后移动一格，然后放入x。st[++top] = x。
• pop : top 往前移动一格。top–。
• empty ：top 大于等于 0 栈非空，小于 0 栈空。top == -1 ? “YES” : “NO”
• query ： 返回栈顶元素。st[top]

1.2 实现代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int m;
int tt,stk[N];
int main()
{
    cin>>m; 
    while(m--)
    {
        string s;
        cin>>s;
        if(s=="push")
        {
            int x;
            cin>>x;
            stk[++tt]=x;
        }
        else if(s=="pop")
        {
            tt--;
        }
        else if(s=="query")
        {
            cout<<stk[tt]<<endl;
        }
        else if(s=="empty")
        {
            if(tt>0) puts("NO");
            else puts("YES");
        }
    }
    system("pause");
    return 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
32
33
34
35
36

2. STL

2.1 代码注解

• C++ 库中包含 栈（stack），直接调用其相关函数即可。

2.2 实现代码

#include<bits/stdc++.h>
using namespace std;

int m;
stack<int>stk;
int main()
{
    cin>>m; 
    while(m--)
    {
        string s;
        cin>>s;
        if(s=="push")
        {
            int x;
            cin>>x;
            stk.push(x);
        }
        else if(s=="pop")
        {
            stk.pop();
        }
        else if(s=="query")
        {
            cout<<stk.top()<<endl;
        }
        else if(s=="empty")
        {
            if(!stk.empty()) puts("NO");
            else puts("YES");
        }
    }
    system("pause");
    return 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
32
33
34
35

二、栈例题——表达式求值

题目描述

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。
注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1。
• 题目中的整除是指向 0 取整，也就是说对于大于 0 的结果向下取整，例如 5/3=1，对于小于 0 的结果向上取整，例如 5/(1−4)=−1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 1e5。

输入样例

(2+2)*(1+1)

输出样例

8

具体实现

1. 实现思路

• 样例可转换为如下图所示：
  
• 从表达式分离出一个个整体。
• 遇到符号，要按照符号的优先级运算。
• 如果栈顶是 + ，即将入栈的是 + ，栈顶优先级高，需要先计算，再入栈。
• 如果栈顶是 + ，即将入栈的是 * ，栈顶优先级低，直接入栈。
• 如果栈顶是 * ，即将入栈的是 + ，栈顶优先级高，需要先计算，再入栈。
• 如果栈顶是 * ，即将入栈的是 * ，栈顶优先级高，需要先计算，再入栈。
• 加上括号，括号是特殊处理的，如果没有遇到右括号，则运算最多只能处理到上一个左括号，例如 2 * （3+4），在加号位置不能先算 2 * 3 ，而是先等待。如果遇上了右括号，则一直运算，直到遇到左括号。

2. 代码注解

• unordered_map<char, int> pr{{‘+’, 1}, {‘-’, 1}, {‘*’, 2}, {‘/’, 2}} 定义加减乘除四则运算的优先级。
• isdigit() 是 C++ 中的一个函数，主要用于检查其参数是否为十进制数字字符,若为阿拉伯数字 0~9 ，则返回非 0 值，否则返回 0 。
• 加法，乘法的顺序无所谓，减法，除法要注意两个数的顺序关系。

3. 实现代码

#include <bits/stdc++.h>
using namespace std;

stack<int> num;
stack<char> op;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();
    int x;
    if (c == '+')
    {
        x = a + b;
    }
    else if (c == '-') 
    {
        x = a - b;
    }
    else if (c == '*') 
    {
        x = a * b;
    }
    else 
    {
        x = a / b;
    }
    num.push(x);
}

int main()
{
    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, j = i;
            while (j < str.size() && isdigit(str[j]))
            {
                x = x * 10 + str[j ++ ] - '0';
            }
            i = j - 1;
            num.push(x);
        }
        else if (c == '(') 
        {
            op.push(c);
        }
        else if (c == ')')
        {
            while (op.top() != '(') eval();
            {
                op.pop();
            }
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
            {
                op.push(c);
            }
        }
    }
    while (op.size()) 
    {
        eval();
    }
    cout << num.top() << endl;
    system("pause");
    return 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
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

三、单调栈例题——单调栈

题目描述

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

输入格式

第一行包含整数 N，表示数列长度。
第二行包含 N 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围

1 ≤ N ≤ 1e5
1 ≤ 数列中元素 ≤ 1e9

输入样例

5
3 4 2 7 5

输出样例

-1 3 -1 2 2

具体实现

1. 实现思路

• 可以用暴力两个 for 循环。
• 用单调递增栈，当该元素可以入栈的时候，栈顶元素就是它左侧第一个比它小的元素。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int stk[N], tt;
int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        while (tt && stk[tt] >= x) 
        {
            tt -- ;
        }
        if (!tt) 
        {
            cout << "-1" << " ";
        }
        else 
        {
           cout << stk[tt] << " ";
        }
        stk[ ++ tt] = x;
    }
    system("pause");
    return 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

四、队列例题——模拟队列

题目描述

实现一个队列，队列初始为空，支持四种操作：

• push x – 向队尾插入一个数 x。
• pop – 从队头弹出一个数。
• empty – 判断队列是否为空。
• query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围

1 ≤ M ≤ 100000
1 ≤ x ≤ 1e9
所有操作保证合法。

输入样例

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例

NO
6
YES
4

具体实现

1. 实现思路

• 用一个数组 q 保存数据。
• 用 hh 代表队头，q[hh] 就是队头元素， q[hh + 1] 就是第二个元素。
• 用 tt 代表队尾， q[tt] 就是队尾元素， q[tt + 1] 就是下一次入队，元素应该放的位置。
• [hh, tt] 左闭右闭，代表队列中元素所在的区间。
• 出队pop：因为 hh 代表队头，[hh, tt] 代表元素所在区间。所以出队可以用 hh++实现，hh++后，区间变为[hh + 1, tt]。
• 入队push：因为 tt 代表队尾，[hh, tt] 代表元素所在区间。所以入出队可以用 tt++实现，tt++后，区间变为[hh, tt + 1], 然后在q[tt+1]位置放入入队元素。
• 是否为空empty：[hh, tt] 代表元素所在区间，当区间非空的时候，对列非空。也就是tt >= hh的时候，对列非空。
• 询问队头query：用 hh 代表队头，q[hh] 就是队头元素，返回 q[hh] 即可。

2. 代码注解

• hh <= tt ? “NO” : “YES” 是三目运算符，如果 hh<=tt ，则输出 NO ，否则输出 YES。

3. 实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int m;
int q[N], hh, tt = -1;

int main()
{
    cin >> m;

    while (m -- )
    {
        string op;
        int x;

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            tt++; 
            q[tt] = x;
        }
        else if (op == "pop") 
        {
            hh ++ ;
        }
        else if (op == "empty") 
        {
            cout << (hh <= tt ? "NO" : "YES") << endl;
        }
        else 
        {
            cout << q[hh] << endl;
        }
    }
    system("pause");
    return 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
32
33
34
35
36
37
38
39

五、队列例题——滑动窗口

题目描述

给定一个大小为 n ≤ 1e6 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。
同行数据之间用空格隔开。

输出格式

输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例

8 3
1 3 -1 -3 5 3 6 7

输出样例

-1 -3 -3 -3 3 3
3 3 5 5 6 7

具体实现

1. 实现思路

• 有题目可知，窗口大小为 3 ，因此要先从数组的第一个元素开始，遍历三个元素形成窗口后，再进行判断。
• 为了保持窗口的大小为3，左侧元素就需要从窗口中剔除。这样使得窗口一直在向右移动，直到考察到最后一个元素结束。
• 如下图过程：

• 以最大值为例：
• 如果当前的滑动窗口中有两个下标 i 和 j ，其中 i 在 j 的左侧（i<j），并且 i 对应的元素不大于 j 对应的元素（nums[i]≤nums[j]），则：
• 当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中。这是由于 i 在 j 的左侧所保证的。
• 因此，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将nums[i]永久地移除。
• 因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组nums中对应的值是严格单调递减的。
• 当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。
• 为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果新元素大于等于队尾元素，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。
• 由于队列中下标对应的元素是严格单调递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。
• 窗口向右移动的时候。因此我们还需要不断从队首弹出元素保证队列中的所有元素都是窗口中的，因此当队头元素在窗口的左边的时候，弹出队头。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;
int a[N], q[N];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i ++ )
    {
        cin >> a[i];
    }
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) 
        {
            hh ++ ;
        }
        while (hh <= tt && a[q[tt]] >= a[i]) 
        {
            tt -- ;
        }
        q[ ++ tt] = i;
        if (i >= k - 1) 
        {
            cout << a[q[hh]] << " ";
        }
    }
    puts("");
    hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh])
        {
            hh ++ ;
        }
        while (hh <= tt && a[q[tt]] <= a[i])
        {
            tt -- ;
        }
        q[ ++ tt] = i;
        if (i >= k - 1) 
        {
            cout << a[q[hh]] << " ";
        }
    }
    puts("");
    system("pause");
    return 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52