1.单链表

单链表包括：
头指针，当前节点值，下一节点的指针
由于是模拟链表，所以还有一个用来表示节点地址的计数指针
int e[N], ne[N], idx, head;

函数包括:
init(), add_to_head(int x)
add(int k, int x), remove(int k)

// 初始化
void init()
{
    head = -1;
    idx = 1;
}

// 插到头节点
// 当前节点赋值(val, next指针), 更新head
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

// 在第k个插入的位置后面插入节点
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

// 删除第 k 个插入的数后面的一个数
void remove( int k )
{
    ne[k] = ne[ne[k]];
}

2.栈

1.模拟栈

tt 是栈顶指针
int stk[N], tt;

函数包括:
init(), push(int x)
pop(), query(), empty()

// 初始化
void init()
{
    tt = -1;
}

// 压栈
void push( int x )
{
    stk[++tt] = x;    
}

// 出栈
void pop()
{
    tt--;
}

// 查询栈顶元素
int query()
{
    return stk[tt];
}

// 查询栈是否为空
void empty()
{
    if( tt == -1 ) cout<<"yes"<<endl;
    else cout<<"no"<<endl;
}

2.栈

stack<数据类型> stk;
stk.empty()
stk.push(数据)
stk.pop()

3.队列

1.模拟队列

队列包括队首,队尾
int q[N], hh, tt;

函数包括:
init(), push(), pop()
query(), empty()

// 初始化
void init()
{
    hh = 0;
    tt = -1;
}

// 入队
void push( int x )
{
    q[++tt] = x;
}

// 出队
void pop()
{
    hh++;
}

// 查询队首元素
void query()
{
    cout<<q[hh];
}

// 查询队列是否为空
void empty()
{
    if(tt<hh) cout<<"yes";
    else cout<<"no";
}

2.优先队列(小根堆)

priority_queue<int,vector<int>,greater<int>> q;
q.top()  // min
q.empty()
q.push(数据)
q.pop()

3.树与图

二叉排序树 及 树的前中后序遍历看这个 二叉排序树

数组建立邻接表
int h[N], e[N*2], ne[N*2], idx;

void add ( int a, int b )  // 插入一条a->b的边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点

cin >> n; //表示树的结点数

// 题目接下来会输入，n-1行数据，
// 树中是不存在环的，对于有n个节点的树，必定是n-1条边
for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    add(a, b), add(b, a); //无向图
}

4.哈希表

unordered_map<数据类型1, 数据类型2> mp;
mp[数据类型1] = 数据类型2

unordered_map<char,int> mp;
mp['{'] = 4;