写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

本次算法均为用数组模拟STL，这样的速度更快而且可操作性更强。

记录

链表

链表，顾名思义，连成一串的数字。值得注意的是，链表并非一条直线，只是所有指针最后能够连城一条线从头到尾。

单链表

一个指针指向它的下一个节点。一般形式：head->0->0->0->0->……->末尾空集（一般用-1表示）

单链表的几个操作：

初始化：

把idx从0开始计数，head指向空集。

插入操作：

把待插入节点idx指针指向要插入位置后面节点。
把插入位置前面的指针指向idx。

删除操作：

把要删除节点前面的节点指针指向要删除节点后面的节点。

下面是模板：

#include <iostream>
const int N=1e6;
using namespace std;
int head,e[N],ne[N],idx;

//head表示头结点（即第一个节点，不是空的）
//e[i]表示第i个节点的数值，不按照顺序排列
//ne[i]表示第i的节点指向的节点序号
//ide表示新加入的节点（不用按顺序）

//init初始化
void initialize()
{
    head=-1;//空集,head也是指针
    idx=0;
}
void add_head(int x)
{
    e[idx]=x;
    ne[idx]=head;//如果这是加入的第一个元素那么加入之后就会变成指向末尾的空集
    head=idx;//本来head在-1，然后这个节点加了过去，所以把这个节点前面定义为head就行了。
    idx++;
}
void add(int x,int k)//在k后面加入x
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}
void removed(int k)//把k后面的一个节点删去
{
    ne[k]=ne[ne[k]];
}
int main()
{
    initialize();
    int n;
    cin>>n;
    while(n--)
    {
        char ch;
        int k,x;
        cin>>ch;
        if(ch=='H')
        {
            cin>>x;
            add_head(x);
        }
        else if(ch=='D')
        {
            cin>>k;//(k==0)
            if(!k)
                head=ne[head];//k=0为删除头节点，头节点其实就是第一个点，第一个点删除吧head指向第二个点（即head本身指向的点）就可以了。
            removed(k-1);//因为节点是从0开始的，所以计数要从k-1才是单链表内所对应的数字
        }
        else
        {
            cin>>k>>x;
            add(x,k-1);
        }
    }
    for(int i=head; i!=-1; i=ne[i])//输出时候每次更新都以指向的下一个节点为输出对象
        cout << e[i] <<" ";
    cout<< endl;
    return 0;
}

双链表

该节点有两个指针指向前后节点。

一般形式：head<->0<->0<->0<->0<->……<->末尾空集（一般用-1表示）

双链表的几个操作：

双链表的几个操作和单链表类似。

初始化：

初始化使用0和1，互相指向对方。

插入操作：

把待插入节点idx指针指向要插入位置后面节点。
把插入位置前面的指针指向idx。

删除操作：

把要删除节点前面的节点指针指向要删除节点后面的节点。

下面是模板：

#include <iostream>

using namespace std;
const int N =1e6;
int e[N],l[N],r[N],idx;

void initialize()
{
    r[0]=1;
    l[1]=0;
    idx=2;//前两个点被起始位置占领
}
void add(int k,int x)//在k后面插入x
{
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}

void removed(int k)//删除k节点
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

int main()
{
    int k=1,x=1;
    add(l[k],x);//在k的左边插入x
    return 0;
}

邻接表

多个单链表的和。可以用来存储图或树。

例如：

head（1）->0->0->0->0->……->末尾空集

head（2）->0->0->0->0->……->末尾空集

head（3）->0->0->0->0->……->末尾空集

head（4）->0->0->0->0->……->末尾空集

head（5）->0->0->0->0->……->末尾空集

…………

栈

先进后出。像是打羽毛球的羽毛球筒。

下面是常见符号和表示含义

const int N=1e6;

int stk[N],tt=0;//tt为栈顶

int x;

stk[++tt]=x;//插入元素，栈从第一个开始计数

tt--;//弹出元素

stk[tt];//即为栈顶

//tt=0时，栈为空

单调栈

题目例如：找到一个数组里面每一个数字左边离它最近而且比它小的数字。

题方法一般如下：

暴力模拟。
把没有用的数字删去。
剩下的元素若有单调性等，进行优化。比如本题，如果当前数字x小于前面的数字，那么前面的数字就可以删除。

下面是模板：

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6;

int n;
int stk[N],tt=0;


//单调队列
int main()
{
    scanf("%d",&n);//scanf输入大概会比cin>>快十倍左右
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        while (tt&&stk[tt]>=x) tt--;//如果栈里面的数字大于该数字，那么栈顶弹出
        if(tt)//栈不为空
            printf("%d ",stk[tt]);
        else printf("-1 ");
        stk[++tt]=x;//把当前的数字加入栈
    }
    printf("\n");
    return 0;
}

队列

先进后出。和医院排队相同。

下面是常见符号和表示含义

const int N=1e6;

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

q[++tt]=x;//插入，队列从0开始计数
hh++;//弹出队头q[hh];队尾为q[tt]
//hh>tt队列为空

单调队列

题目例如：有一个框可以框k个数字，这个框在一个数组从头到尾移动一次，看框每动一次里面的最小数字是多少。（移动窗口）

解题方法一般如下：

暴力模拟。
把没有用的数字删去。
剩下的元素若有单调性等，进行优化。比如本题，框即为队列。如果前面的数字比新加入的数字大，可以直接删除。如果队列存的数字超过k个，那么前面的数字要弹出。

下面是模板

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e6;

int n,k;
int q[N],a[N];//队列里面存的是序列的序号
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=0; i<n; i++)  scanf("%d",&a[i]);

    int hh=0,tt=-1;
    for(int i=0; i<n; i++)//不能从i=2开始，因为这样会导致前两个数字存不进队列
    {
        while(hh<=tt&&i+1-k>q[hh]) hh++;//如果长度超出k则把头部去掉

        while(hh<=tt&&a[q[tt]] >= a[i]) tt--;//如果队列末尾的值比当前值大，那么直接删除
        q[++tt]=i;//当前值放入队列
        if(i+1>=k) printf("%d ",a[q[hh]]);//从第k个数字开始输出运算结果
    }4
    cout  << endl;//这样队列里面就会以单调递增的顺序排列
    return 0;
}

【算法】链表、栈、队列

写在最前面：

记录

链表

单链表

单链表的几个操作：

双链表

双链表的几个操作：

邻接表

栈

单调栈

队列

单调队列