开个博客记录一下算法学习的内容
------------------------------------分界线------------------------------------
最近在acwing上学了数据结构之链表，栈，队列，KMP（都是采用数组进行模拟，比用struct实现更快）
链表：像一个链子一样一个元素串着另一个元素。
单链表：每个节点有一个值，同时存有一个指针指向后一个节点e[i]和ne[i]。链表还要有个头有个尾巴，于是用head来存储头结点的下标，用-1来表示空节点的下标（尾巴上的节点）而元素下标就用idx来表示。
初始化：idx = 0;head = -1:
可以实现的操作：
在最前面加入一个元素x
在下标k的数后面插入一个元素x
删除下标k的元素后面那个元素
双链表：我们发现单链表没法向前访问，这样就没法精准删除下标为k的元素，于是便多加一个数组来表示每个节点前面那个节点的下标。
初始化：（最左边和最右边的节点已经存在，他们没有值）idx = 2; r[0] = 1 ; l[1] = 0;
可以实现的操作：
在下标为k的数左/右边插入一个元素x
删除下标为k的元素
可以用单链表中的邻接表来存储树和图~~~然鹅我还没学到
栈（stack）：可以想象成一个罐子，先进后出。用tt来表示最末端的元素的下标，stk[i]代表值。
初始化：int stk[N]; tt = 0;
push：stk[++tt] = x;
pop：tt--;
！empty:tt＞0
query:stk[tt]
（甚至可以查询栈底的元素stk[1]）
队列（queue）：一个两端都能开口的罐子，先进先出。用tt表示最末端，hh表示首端，q[i]代表值。
初始化：int q[N]; tt = -1,hh = 0;
push:q[++tt] = x;
pop:hh++;
!check:tt>=hh;
query:q[tt]或者q[hh]；
总结：链表提供了从一个元素找到下一个元素的方法，单链表实际能存储的空间大小为N，双链表为N-2。个人理解链表是一种比栈&队列更高级的东西？他的缺点在于一个元素一旦删除，他对应的那个idx也永久性删除了（所以存储空间利用率没有那么高）
栈的实际存储空间为N-1，队列实际存储空间为N；
栈是其中唯一一个可以“释放”存储空间的容器。
p.s.其实所谓“实际所能存储的空间”并不绝对，可以采用更改下标的形式改变（比如在stk的初始化阶段让tt=114） 上述初始化的方法只是个人认为最方便的（单链表存储空间最大，双链表因为有l[1]r[0]所以必须从2开始，stk因为empty函数（tt>0）比较符合认知所以从1开始存，queue为了最大化存储空间所以tt=-1,hh = 0）