08.栈与队列

栈与队列

栈与队列是两种重要的线性数据结构，分别遵循后进先出与先进先出的操作原则，广泛应用于程序设计与算法问题的解决。

栈

• 食堂的餐盘：洗->放->取
• 浏览器的后退按钮：页面0->页面1 -> 页面2 -> 页面3 -> 后退 -> 后退，你在页面几？
• 文本编辑器的撤销（ctrl+z）、退格（<--）输入：“abcdef”，按两下“<--”键，剩下的是什么

栈就像一个放盘子的容器，你只能从最上面放盘子或者取盘子，先放进去的盘子会被压在下面，要等上面的盘子都取走了才能取到，这种数据结构的特点就是先进后出，就像叠盘子和取盘子的过程一样。

例：小鱼的数字游戏

输入一串数字，以一个0结尾，倒过来输出

输入

3 65 23 5 34 1 30 0

输出

30 1 34 5 23 65 3

你当然可以输入到数组里，然后循环反过来输出

#include<stdio.h>
int a[111];
int main() {
    int n;  // 统计输入的个数
    for(n = 0; ; n ++) {
        scanf("%d", &a[n]);
        if(a[n] == 0) {
            break;
        }
    }
    for(int i = n - 1; i >= 0; i --) {
        printf(" %d" + (i == n - 1), a[i]);
    }
    printf("\n");
    return 0;
}

其实你已经发现了栈的一种实现方式，那就是用数组模拟它。更符合栈的定义一些，这样写：

#include<stdio.h>
struct Stk {
    int stk[111];
    int top;
    Stk() {top = -1;}
    bool Empty() {return top == -1;}
    int Top() {return stk[top];}
    void Pop() {top --;}
    void Push(int x) {stk[++top] = x;}
    unsigned Size() { return top + 1; }
};
int main() {
    Stk stk = Stk();
    int x;
    while(scanf("%d", &x) && x != 0) {
        stk.Push(x);
    }
    for(; !stk.Empty(); stk.Pop()) {
        printf("%d", stk.Top());
        if(stk.Size() > 1) printf(" ");
    }
    printf("\n");
    return 0;
}

在熟悉栈的工作方式后，可以用 C++ STL 中的栈容器来简化代码

#include<stdio.h>
#include<stack> // C++里的头文件
int main() {
    std::stack<int> stk;
    int x;
    while(scanf("%d", &x) && x) {
        stk.push(x);
    }
    for(; !stk.empty(); stk.pop()) {
        printf("%d", stk.top());
        if(stk.size() > 1) printf(" ");
    }
    printf("\n");
    return 0;
}

例：表达式括号匹配

假设一个表达式有英文字母（小写）、运算符（+、-、*、/）和左右小（圆）括号构成，以 @ 作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则输出 YES；否则输出 NO。

输入

(25+x)*(a*(a+b+b)@

输出

NO

括号的层次就像栈，每遇到一个左括号，就“深”了一层，每遇到一个右括号，就“浅”了一层，那么左括号和右括号就想入栈和出栈一样，模拟这个操作，某个时候出栈比入栈多，或最后出栈比入栈少，就都是不正确的括号匹配。

#include<stdio.h>
#include<stack>
char s[550];
int main() {
    std::stack<char> stk;
    scanf("%s", s);
    bool no_flag = false;
    for(int i = 0; s[i]; i ++) {
        if(s[i] == '(') {
            stk.push('(');
        } else if(s[i] == ')') {
            if(stk.empty()) {
                printf("NO\n");
                no_flag = true;
                break;
            }
            stk.pop();
        }
    }
    if(!no_flag) {
        if(stk.empty()) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

栈是一类数据结构，同时也是一种思想，心中有栈，码中无栈，也可以解决这个问题

#include<stdio.h>
char s[550];
int main() {
    scanf("%s", s);
    bool no_flag = false;
    int l_cnt = 0;
    for(int i = 0; s[i]; i ++) {
        if(s[i] == '(') {
            l_cnt ++;
        } else if(s[i] == ')') {
            if(l_cnt == 0) {
                printf("NO\n");
                no_flag = true;
                break;
            }
            l_cnt --;
        }
    }
    if(!no_flag) {
        if(l_cnt == 0) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

知识点：既然括号的深度与栈有对应关系，那么一个数学表达式的计算顺序也可以用栈来表达，甚至包括加减乘除的优先级，这就是“后缀表达式”，拆解一个数学表达式，根据运算顺序转为一个栈，就能条理清晰的按顺序计算，得到表达式的值。

队列

队列就像生活中的排队，先到的人排在前面，遵循 “先进先出” 的规则。

为更灵活计算某些问题，也可以设计一种两边都能入队与出队的双端队列

例：约瑟夫问题

n 个人围成一圈，从第一个人开始报数，每报第 \(m\) 个人出圈，输出依次出圈的编号。

输入

10 3

输出

3 6 9 2 7 1 8 5 10 4

此题有多种解法，用队列模拟是其中一种，如果一个队列出队后立刻排到队尾，就构成了一个圈。

队列可以用数组模拟，但队列和栈不同，不断地一端进另一端出，会很快到达数组的尽头，所以在代码组织上将数组的头尾接起来

知识点：循环队列，让队头队尾到达数组末尾后，回到数组的开头，让数组首尾接为一个圈。为了避免错误地覆盖数据，需利用队首队尾的位置关系，合理判断队伍是空的还是满的。在竞赛中，可以简化这一点，直接把数组开得够大即可。

#include<stdio.h>
struct Queue {
    int a[111];
    int front = 0, rear = DSIZE - 1;
    const int DSIZE = 110;  // 队列容量
    void Push(int x) {
        a[rear = (rear + 1) % DSIZE] = x;
    }
    int Front() {
        return a[front];
    }
    void Pop() {
        front = (front + 1) % DSIZE;
    }
    bool Empty() {
        return (rear + 1) % DSIZE == front;
    }

};
int n, m;
Queue q;
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) {
        q.Push(i);
    }
    for(int i = 1; !q.Empty(); i ++) {
        if(i % m != 0) {
            q.Push(q.Front());
        } else {
            printf("%d", q.Front());
            if(i != n * m) {
                printf(" ");
            }
        }
        q.Pop();
    }
    printf("\n");
    return 0;
}

用 C++ STL 的方法可自行尝试

优先级队列

有的场景中，出队的时候不是按到达顺序，而是有一个固定的优先规则，外在使用上和队列一样，但内在逻辑中通过特定规则优先出队，完成一些特殊的任务。

知识点：优先队列中，按某种规则优先的高效机制是由堆这种数据结构来实现的，之后我们会学习。C++ STL 封装了优先队列，可以直接使用。

例：外星窗口服务

某外星窗口优先服务年长者，顾客陆续来到大厅等待，窗口每次叫号都是大厅中年龄最小的顾客，窗口服务的客户将离开大厅.

第一行 \(1\leq n\leq 100000\) ，表示按顺序有 \(n\) 个情况，情况有两类：

• 1 x 表示到来了一位年龄为 \(10 \leq x \leq 10^9\) 的顾客；
• 2 表示窗口叫了一次号，数据保证叫号时大厅有顾客.

输入

14
1 81
2
1 17
1 77
2
1 101
1 66
1 120
1 68
1 120
1 89
1 87
2
2

输出

81
17
66
68

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#include<algorithm>

int main() {

    int n, op, ag;
    scanf("%d", &n);
    // priority_queue默认大者优先，利用 std::greater<int> 实现小者优先
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    while(n --) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d", &ag);
            q.push(ag);
        } else {
            printf("%d\n", q.top());
            q.pop();
        }
    }
    return 0;
}