一、单链表

需要二个数组 地址e[],下一个地址ne[],需要一个整数存放当前的下标
基本操作：

1、插入

 1）表头处插入
   a.将当前节点地址修改为x
   b.将当前节点的next指针指向head

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

 2）第k个数后面插入  
  a.修改第k个数后的地址
  b.让当前的x指向第k个数后面的地址
  c.将第k个节点后移

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

2、删除

将k的next指向下两个节点的next
 void remove(int k){
    ne[k] = ne[ne[k]];
    }

二、双链表

 相比于单链表，多了一条指向前节点的边
 需要用l[],r[],e[],来依次存放左右节点地址和本节点的地址
 基本操作：

1、插入

 a.修改当前地址
 b.k节点修改右指针，k节点的下一节点修改左指针，idx修改左右节点

 void add(int k,int x){
     e [idx] = x;
     r [idx] = r[k];
     l [idx] = k;
     l [r[k]] = idx;//使k节点的下一个节点的左指针指向idx
     r [k]= idx++;//让k节点的右指针指向idx
    }

2、删除

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

三、栈

一种先入后出的数据结构，在c++中存在一个STL stack。但手写栈会比STL时间快。
基本操作：

1、push（入栈）

stk[++ tt] = x;

2、pop（出栈）

tt--;

3、empty（判断是否空）

cout << (tt?"NO":"YES");

4、query（查询）

cout<<stk[tt];

5、单调栈

单调栈是一种特殊的栈，栈内元素单调的。
for(int i=0;i<n;i++){
    int x;
    cin>>x;
    while(tt && stk[tt]>=x) tt--;//单调递减
    if(tt)cout<<stk[tt]<<' ';
    else cout<<-1<<' ';

    stk[++tt] = x;
}

五、队列

是一种先入先出的数据结构，需要next，data，address，tt存放尾结点的后一节点

1、push

op[++ tt] = x;//队尾弹出

2、pop

hh++ ;//队头插入

3、empty

cout << (hh <= tt? "NO":"YES");

4、query

cout << op[hh];

5、单调队列

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口，q存放下标
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}

六、 KMP