栈与队列入门

算法

什么是栈？

是C++标准库（STL）的一部分，它实现了一个先进后出的数据结构，它适用于最后添加的元素先被移除的场景。

【C++】STL：栈和队列模拟实现_堆栈模拟队列c++-CSDN博客

栈的基本操作有哪些？

  • push():在栈顶添加一个元素

  • pop():弹出栈顶元素

  • top():返回栈顶元素的引用但不移除它

  • empty():检查栈是否为空

  • size():返回栈中元素的数量

    这里是栈的基本语法

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
#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // 向栈中添加元素
    s.push(1);
    s.push(2);
    s.push(3);

    // 访问栈顶元素
    std::cout << "Top element is: " << s.top() << std::endl;

    // 移除栈顶元素
    s.pop();
    std::cout << "After popping, top element is: " << s.top() << std::endl;

    // 检查栈是否为空
    if (!s.empty()) {
        std::cout << "Stack is not empty." << std::endl;
    }

    // 打印栈的大小
    std::cout << "Size of stack: " << s.size() << std::endl;

    return 0;
}

注意事项

  • <stack> 不提供直接访问栈中元素的方法，只能通过 top() 访问栈顶元素。

  • 尝试在空栈上调用 top() 或 pop() 将导致未定义行为。

  • <stack> 的底层容器可以是任何支持随机访问迭代器的序列容器，如 vector 或 deque。

什么是队列？

C++ 标准库中的 <queue> 头文件提供了队列（Queue）数据结构的实现。队列是一种先进先出（FIFO, First In First Out）的数据结构，它允许在一端添加元素（称为队尾），并在另一端移除元素（称为队首）。

队列是一种线性数据结构，它遵循以下规则：

  • 元素只能从队尾添加。
  • 元素只能从队首移除。

队列有哪些常用操作？

队列提供了以下常用操作：

  • empty(): 检查队列是否为空。
  • size(): 返回队列中的元素数量。
  • front(): 返回队首元素的引用。
  • back(): 返回队尾元素的引用。（栈就无法返回最底下的元素）
  • push(): 在队尾添加一个元素。
  • pop(): 移除队首元素。

简单实例如下

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
#include <iostream>
#include <queue>

int main() {
    // 创建一个整数队列
    std::queue<int> q;

    // 向队列中添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 打印队列中的元素数量
    std::cout << "队列中的元素数量: " << q.size() << std::endl;

    // 打印队首元素
    std::cout << "队首元素: " << q.front() << std::endl;

    // 打印队尾元素
    std::cout << "队尾元素: " << q.back() << std::endl;

    // 移除队首元素
    q.pop();
    std::cout << "移除队首元素后，队首元素: " << q.front() << std::endl;

    // 再次打印队列中的元素数量
    std::cout << "队列中的元素数量: " << q.size() << std::endl;

    return 0;
}

以上总结参考菜鸟驿站和OIWIKI

栈实战环节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
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int temp1 = 0, temp2 = 0, mark1 = 0, mark2 = 0, n, x = 0, y = 0;
    string a;
    int left[1000];
    int right[1000];
    cin >> a;
    for (int i = 0; i < a.length() && a[i] != '@'; i++) {
        if (a[i] == '(') {
            left[temp1] = i;
            temp1++;
        }
    }
    for (int j = 0; j < a.length() && a[j] != '@'; j++) {
        if (a[j] == ')') {
            right[temp2] = j;
            temp2++;
        }
    }
    if (temp1 != temp2) {
        x = 1;
    }
    for (int i = 0;i < temp1 && x==0; i++) {
        if (left[i] > right[i])
            y = 1;
    }
    if (x == 0 && y == 0) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    return 0;
}

把左右括号的坐标用两个数组存下来。然后去比对。不管思路和时间复杂度怎样，代码还是相对简洁的啊！

那么我们现在尝试用栈。思路很简单，遍历字符串。

  • 遇到 (压入栈 st。

  • 遇到 )时：

    • 如果栈为空，输出 “NO” 并结束程序。（这时候已经不合法了）
    • 否则弹出栈顶的 (。（括号成功匹配）

  • 遍历结束后，如果栈为空，说明所有 (都有对应的 )，输出 “YES”。

  • 否则输出 “NO”。（不为空说明“（”太多啦）

    贴上AC代码

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
#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> a;
    string s;
    cin >> s;
    int pos = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '@') {
            pos = i;
            break;
        }
    }
    for (int i = 0; i <= pos; i++) {
        if (s[i] == '(') {
            a.push(s[i]);
        }
        if(s[i]==')') {
            if(a.empty()) {
                cout <<"NO";
                return 0;
            }
            else {
                a.pop();
            }
        }
    }
    if (a.empty()) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
    return 0;
}

栈实战环节2（表达式）

洛谷普及难度题目

一打眼其实这是一道小模拟的题目。那么我们开始模拟吧。

1+1*3+4

对于这个样例，我们会怎么计算呢。我们往往想的是，先把带乘法的都算完，然后最后只剩加法来相加。比如这个算式我们肯定会先计算1*3得出3之后，把式子转为1+3+4。思路很简单，那么代码如何实现呢。

按照我们朴素的思路，应该就是查找“*”两边的数字位置。那么思路就出来了，首先用字符串的方式来读入，然后遍历字符串，找到乘号的位置，然后往前往后遍历寻找到相邻的符号，把符号间的数字提取出来。计算出结果后，再用计算结果替代原字符串。最后把乘号都替换完只剩下加号的时候再遍历一遍相加。

你是不是晕了？

你确实该晕。因为实现代码实在是太复杂啦！(这里附上代码，但是不是为了让你学习，只是让你看看这有多麻烦)

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

const int MOD = 10000;

int main() {
    string expr;
    cin >> expr;

    // 先处理所有乘法
    size_t pos;
    while ((pos = expr.find('*')) != string::npos) {
        // 找到 * 左边的数字的起始位置
        size_t left_start = pos;
        while (left_start > 0 && isdigit(expr[left_start - 1])) {
            left_start--;
        }

        // 找到 * 右边的数字的结束位置
        size_t right_end = pos;
        while (right_end + 1 < expr.size() && isdigit(expr[right_end + 1])) {
            right_end++;
        }

        // 提取左右数字
        int left_num = stoi(expr.substr(left_start, pos - left_start));
        int right_num = stoi(expr.substr(pos + 1, right_end - pos));

        // 计算乘积并取模
        int product = (left_num * right_num) % MOD;

        // 替换原字符串中的部分
        expr.replace(left_start, right_end - left_start + 1, to_string(product));
    }

    // 现在只剩下加法，直接计算总和
    int result = 0;
    size_t start = 0;
    while (start < expr.size()) {
        size_t end = expr.find('+', start);
        if (end == string::npos) {
            end = expr.size();
        }
        int num = stoi(expr.substr(start, end - start));
        result = (result + num) % MOD;
        start = end + 1;
    }

    cout << result << endl;
    return 0;
}

虽然说我们是模拟，但是也不能完全模拟。因为你要按照计算机更好实现的方式来模拟。

这个思路最大的问题在于，它用string手动存储了整个表达式，手动解析了运算符号。非常依赖字符串索引。

这是不会利用cin的表现。cin>>t可以直接读取一个整数，跳过空格和换行符。cin >>c可以读取一个字符。

所以你可以根据c++的输入流自动处理数字和运算符。达到边输入边计算的效果。

1+1*3+4 1*5+3*6

我们再看几个例子，那我们按照计算机的输入方法从左往右看。第一个数字是1，然后接着的运算符是“+”，那显然1就是要被我们直接加到结果里面而不需要进行乘法运算的了。用一个sum变量存一下，把1加进去。第二个数字是1，后面的运算符号是*，那1就要和乘号后面的数相乘。得到一个数，后面是＋号，那把前面的乘积累计到sum，最后是4，也直接加上去。

在这个模拟过程中，我们不难发现，其实我们只需要关注两个东西。一个是当前的总和，一个是需要乘了之后才能加上去的和。那么乘积我们用t来维护，遇到乘号时，累积到当前结果t,如果是加号，说明乘法段结束，把t加入总和sum，然后重置t。最终sum+t的答案就是最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
const int mod = 10000;
long long x,s,t; //x是当前的数，s是和，t是当前段的乘积
char c;
int main(){
    cin>>t;//先读入第一个数，之后每次读入一个符号一个数
    while(cin >>c && c != '\n'){ //最后会读到换行符
        cin >>x;
        if(c == '*') t = t * x % mod; //是乘号就相乘
        else s = (s + t) % mod,t = x; //加号就加上上一段的积，t变为下一段的第一个数
    }
   cout <<(s + t) % mod;
    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
#include <bits/stdc++.h>
using namespace std;
const int mod = 10000;
char op;
stack<int>q;
int main() {
    int t,m;
    cin >>t;
    q.push(t);
    while(cin>>op && op!='\n') {
        int num;
        cin >>num;
        if(op=='*') {
            int top=q.top();
            q.pop();
            q.push(num*top%mod);
        }
        else {
            q.push(num%mod);
        }
    }
    int sum=0;
    while(!q.empty()) {
        sum=(sum+q.top())%mod;
        q.pop();
    }
    cout <<sum<<endl;
}


用熟练了之后你会发现其实用的挺顺手的。也许你会说，这还不如前面的动态维护呢，时间复杂度都是O(n)。

栈的空间复杂度还可能大一点。但是动态维护的方法仅适用于+，*。栈的话可以扩展到有括号的。这时候你就能理会栈的方便了。（后面会继续讲解单调栈以及进阶版表达式求值和括号匹配例题）

队列实战1（用队列实现bfs）

Breadth First Search (BFS) 宽度优先搜索，又称广度优先搜索，是图搜索算法中的一种，BFS 顾名思义，我们搜索的过程是平铺开进行搜索，即从起点开始，将所有和它相邻的结点都搜索一遍，然后再一个个去搜索这些相邻结点自己的相邻节点，一层一层铺开，从而进行搜索。其搜索过程就像水中的涟漪，从中心开始，向四周进行扩散，直到遍历完整个图。（贴心的备上视频）

对于 BFS 算法，正如上面所说的，我们需要一层一层遍历所有的相邻结点。那么相邻结点之间的先后顺序如何确定？因此我们需要一个数据结构来进行存储和操作，需要使得先遍历的结点先被存储，直到当前层都被存储后，按照先后顺序，先被存储的结点也会被先取出来，继续遍历它的相邻结点。

我们可以惊奇的发现，这个需求不就是我们的队列吗，First In First Out (FIFO)* 完全契合这里的 use case。因此对于 BFS 我们需要使用 Queue 这样的一个数据结构，来存储每一层的结点*，同时**维护『先进先出 FIFO』**的顺序。

理论知识差不多就这样了。