单链表

//e[i] 存储值i位的值
// ne[i] 存储第i位的下一位的坐标
// idx 为单链表个数

注意idx是从一开始，如果要删除点k次插入的点,应该调用removal(k-1)，而不是removal(k).

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++;
}

双向链表

int l[N],r[N],e[N],ne[N],idx,head,tail;
void init()
{
// 0表示左端点，1表示右端点
    r[0]=1,l[1]=0;
// 因为 head和tail 已经占据了0，1点
    idx=2;
}
//在k的右边插入一个x
void add(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx;
}
// 删除第k个点
void remove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

栈的实现

栈是先进后出

int stk[N],tt=0;

//插入
stk[++tt]=x;

// 弹出
tt--;

//判断栈是否为空
if(tt>0) not empty;
else empty;

//为栈顶
stk[tt]

队列

// 在队伍尾部插入元素，队列首部弹出元素
int q[N],hh=0,tt=-1;

// 插入
q[++tt]=x;

// 弹出 hh++;
if(hh<=tt)not empty
else empty

单调栈

// 本质就是一升序或者降序的序列

int q[N],t=0;
// 单调上升的序列
for(int i=1;i<=n;i++)
{
    int x;
    cin>>x;
    while(t>=1&&q[t]>=x)t--;
    q[++t]=x;
}

// 单调下降的序列
for(int i=1;i<=n;i++)
{
    int x;
    cin>>x;
    while(t>=1&&q[t]<=x)t--;
    q[++t]=x;
}

单调队列

int a[N],q[N],n,k;
int head=0,tail=-1;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];

for(int i=1;i<=n;i++)
{
    while(head<=tail&&q[head]<i-k+1)head++;
    while(head<=tail&&a[q[tail]]>=a[i])tail--;
    q[++tail]=i;
    if(i>=k)printf("%d ",a[q[head]]);
}

kmp

int ne[N];
char p[N],s[N];
int n,m;
for(int i=2,j=0;i<=n;i++)
{
    while(j&&p[i]!=p[j+1])j=ne[j];
    if(p[i]==p[j+1])j++
    ne[j]=j;
}
for(int i=1,j=0;i<=n;i++)
{
    while(j&&s[i]!=p[j+1])j=ne[j];
    if(s[i]==p[j+1])j++;
    if(j==n)
    {
        printf("%d ",i-n);
        j=ne[j];
    }
}