数据结构总结（CSP-J）

wsy_I · 2026-09-01 21:06:54 · 算法·理论

upd：修正了一处关于时间复杂度的错误言论，实际上使用提高组算法可以做到更优。

upd：修正：堆不在 J 组考纲里，已转移至 S 组文章。

前言

保证全部的内容在 CSP-J 的考纲内。题目难度为橙题到青题。

介绍的数据结构有：栈、队列、链表、树、图、堆（优先队列）。

好的，废话不多说，直接开始~

1. 栈

1.1 基础栈

栈是什么东西？

是一个 FILO 的数据结构。

很明显刚才那句话不是给人看的。

其实栈是这么一个东西。它是一个数组加上了一个栈顶，并且只可以在栈顶进行操作。

比如这里有一只可爱的栈 s。它初始为空。假如我们要往这个栈里面依次加入 1, 2, 3, 4, 5，那么这个栈就只会星程 s=1, 2, 3, 4, 5 这个序列。这个时候，栈顶指向 5。

如果我们一个一个把这个栈里面的数弹出，那么得到的出栈序列就是 5, 4, 3, 2, 1。为什么？因为我们的栈顶从 5 移动到了 1。

这个时候我们就可以解释 FILO 是什么了。FILO 其实是 First In Last Out 的缩写，也就是在前面进去的数在后面出来。就像 1，是第一个入栈的，但是却最后一个出栈。

一个手写栈大概有以下的基础操作：

• 判断栈是否为空。
• 询问栈顶的元素。
• 询问栈的大小。
• 向栈中加入一个元素。
• 弹出栈顶的元素。
• 清空栈。

栈可以用一个数组实现，核心代码如下：

int a[], t;//栈数组，栈顶指针
bool empty() {return t == 0;}//判断栈是否为空
int top() {return a[t];}//询问栈顶元素
int size() {return t;}//询问栈的大小
void push(int x) {a[++t] = x;}//向栈中加入一个数x
void pop() {if(t > 0) t--;}//弹出栈顶元素，如果没有元素则忽略
void clear() {t = 0;}//清空栈

可以发现栈还是非常好写的。

这是 模板题 的代码： ::::success[代码]

#include <bits/stdc++.h>
#define endl '\n'
#define ull unsigned long long
using namespace std;
const int N = 1e6 + 10;
struct myStack {
    ull a[N];
    int t;
    void clear() {t = 0;}
    void push(ull x) {a[++t] = x;}
    int size() {return t;}
    void pop() {if(t > 0) t--;}
    ull top() {return a[t];}
} st;
int T, n;
int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while(T--) {
        cin >> n;
        st.clear();
        for(int i = 1; i <= n; i++) {
            string s;
            ull x;
            cin >> s;
            if(s == "push") {
                cin >> x;
                st.push(x);
            } else if(s == "pop") {
                if(st.t == 0) cout << "Empty\n";
                st.pop();
            } else if(s == "query") {
                ull t = st.top();
                if(st.t == 0) cout << "Anguei!\n";
                else cout << t << endl;
            } else {
                cout << st.t << endl;
            }
        }
    }
    return 0;
} 

:::: 当然，就算栈很好写，时时刻刻的手写还是很烦的，所以 STL 给我们提供了一个封装好了的栈：stack<T>。

其中提供了以下的核心操作：

stack<int> st;//声明一个栈，int也可以换成其他类型
st.push(x);//相当于手写栈的push
st.pop();//相当于手写栈的pop
st.top();//相当于手写栈的top
st.size();//相当于手写栈的size
st.empty();//相当于手写栈的empty

当然，手写还是有一定好处的，毕竟 STL 栈不支持 \mathcal{O}(1) 的清空栈，只能一个一个的手动弹出。

STL 栈实现模板题的代码如下： ::::success[代码]

#include <bits/stdc++.h>
#define endl '\n'
#define ull unsigned long long
using namespace std;
const int N = 1e6 + 10;
stack<ull> st;
int T, n;
int main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> T;
    while(T--) {
        cin >> n;
        while(!st.empty()) st.pop();
        for(int i = 1; i <= n; i++) {
            string s;
            ull x;
            cin >> s;
            if(s == "push") {
                cin >> x;
                st.push(x);
            } else if(s == "pop") {
                if(st.empty()) cout << "Empty\n";
                else st.pop();
            } else if(s == "query") {
                if(st.empty()) cout << "Anguei!\n";
                else cout << st.top() << endl;
            } else {
                cout << st.size() << endl;
            }
        }
    }
    return 0;
} 

:::: 可以做一下下面这些题：

1. 验证栈序列
2. 日志分析

以及团队内部的一道神题（我绝对不会承认小 W 是我）： ::::info[题面]

题目描述

小 W 终于鼓起勇气向小 M 表白，然而只是有勇气写情书。为了防止情书内容被同学窃取，小 W 给情书加密。小 M 的解密方式很简单，假设情书是字符串 S1，小 W 给她的解密串是 S2，小 M 会重复 地完成“在 S1 中找到子串 S2 并删除”这一操作直到在 S1 中找不到 S2。假如你是小 M，请你确定情书的最终内容。（从前往后遍历的时候找到一个可以删除的立即删除，删除之后，继续遍历新的数组，继续删除）

输入格式

第一行，一个字符串 S_1。

第二行，一个字符串 S_2。

输出格式

输出只有一行，一个字符串 S，表示最终内容。

输入输出样例 #1

输入 #1

iloooooooooooooooveu
oo

输出 #1

iloveu

说明 / 提示

用 L(s) 表示字符串 s 的长度。