单链表

AcWing 826. 单链表

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int head, e[N], ne[N], idx;

void init()
{
    head = -1;
    idx = 0;
}

void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx++;
}

void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int n;
    cin >> n;

    init();

    while (n--)
    {
        int k, x;
        char op;
        cin >> op;

        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'I')
        {
            cin >> k >> x;
            add(k - 1, x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
    }

    for (int i = head; i != -1; i++) cout << e[i] << ' ';
    puts("");

    return 0;
}

双链表

AcWing 827. 双链表

#include <iostream>

using namespace std;

const int N = 100010;

int e[N], r[N], l[N], idx;

void init()
{
    r[0] = 1, l[1] = 0, idx = 2;
}

void add(int k, int x)
{
    e[idx] = x;
    r[idx]=  r[k],l[idx] = k;
    l[r[idx]] = idx, r[k] = idx++;
}

void remove(int k)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main()
{
    init();

    int M;
    cin >> M;
    while (M--)
    {
        int k, x;
        string op;
        cin >> op;
        if (op == "L")
        {
            cin >> x;
            add(0, x);
        }
        if (op == "R")
        {
            cin >> x;
            add(l[1], x);
        }
        if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        if (op == "IL")
        {
            cin >> k >> x;
            add(l[k + 1], x);
        }
        if (op == "IR")
        {
            cin >> k >> x;
            add(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);
    puts("");

    return 0;
}

栈

AcWing 828. 模拟栈

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

typedef long long LL;

int M;
LL stk[N];
int tt = 0; //tt指针初始化为0，第一个数存在1上，当tt==0的时候，代表空栈

int main()
{
    cin >> M;

    string op;
    int x;
    while (M--){
        cin >> op;

        if (op == "push")
        {
            cin >> x;
            stk[++tt] = x;
        }
        else if (op == "pop")
        {
            tt--;
        }
        else if (op == "empty")
        {
            if (!tt) cout << "YES";
            else cout << "NO";
            puts("");
        }
        else if (op == "query")
        {
            cout << stk[tt] << endl;
        }
    }

    return 0;
}

队列

AcWing 829. 模拟队列

#include <iostream>

using namespace std;

const int N = 100010;

int q[N], hh = 0, tt = -1;

int main()
{
    int M;
    cin >> M;

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

        cin >> op;
        if (op == "push")
        {
            cin >> x;
            q[++tt] = x;
        }
        if (op == "pop")
        {
            hh++;
        }
        if (op == "query")
        {
            cout << q[hh] << endl;
        }
        if (op == "empty")
        {
            if (hh > tt) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }

    return 0;
}

单调栈

AcWing 830. 单调栈

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int stk[N], tt = 0;

int main()
{
    int M;
    cin >> M;

    while (M--)
    {
        int x;
        cin >> x;

        while (tt && stk[tt] >= x) tt--;

        if (!tt) cout << "-1 ";
        else cout << stk[tt] << ' ';

        stk[++tt] = x;
    }

    return 0;
}

单调队列

AcWing 154. 滑动窗口

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;

int q[N], a[N];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
    {
        if (i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if (i - k >= 0) cout << a[q[hh]] << ' ';
    }
    puts("");

    hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
    {
        if (i - k + 1 > q[hh]) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i - k >= 0) cout << a[q[hh]] << ' ';
    }
    puts("");

    return 0;
}

KMP

AcWing 831. KMP字符串

堆

AcWing 838. 堆排序

AcWing 839. 模拟堆

Trie

并查集

树状数组

线段树

可持久化数据结构

平衡树

AC自动机