算法基础课题解合集

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈的实现过程

我们需要用一个指针 $top$ 记录栈顶（$top$ 初始为 $0$），然后用一个 $stk$ 数组来存储数据。

执行 push 操作时，我们只要把 $x$，插入到栈顶指针处，然后让栈顶指针加一即可。

执行 pop 操作时，我们不用真的把这个数删除，只需要将 $top$ 指针减一即可，让之后插入的数覆盖掉先前的。

执行 query 操作时，我们只需要把当前栈顶的元素输出即可。

执行 empty操作时，我们只需要判断 $top$ 是否为 $0$ 即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 100010;
int m, top, stk[N];
int main() {
    scanf("%d", &m);
    while (m --) {
        string s;
        int x;
        cin >> s;
        if (s == "push") {
            scanf("%d", &x);
            stk[top ++] = x;
        } else if (s == "pop") {
            top --;
        } else if (s == "query") {
            printf("%d\n", stk[top - 1]);
        } else {
            if (top == 0) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

好啦，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$