咳咳,这里是一篇简陋的博客
单链表
每个结点只有一个指向后的指针
用于:邻接表—存储图和树
int head, e[N], ne[N], idx; 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 ++; } void remove_head(){ head = ne[head]; } void remove(int k){ ne[k] = ne[ne[k]]; }
双链表
每个结点有一个指向前,一个指向后的指针
用于:优化某些问题
int e[N], l[N], r[N], idx; void init() { l[1] = 0, r[0] = 1, idx ++; } void add(int k, int x){ e[idx] = x; l[idx] = k; r[idx] = r[k]; l[r[k]] = idx, r[k] = idx ++; } void remove(int k){ r[l[k]] = r[k], l[r[k]] = l[k]; }
栈
先进后出
int stk[N], tt; stk[++tt] = x; tt--; stk[tt]; if(tt > 0)
单调栈
队列
先进先出
int q[N], hh = 0, tt = -1; q[++tt] = x; hh++; q[hh]; if(hh <= tt)
循环队列
int q[N], hh = 0, tt = 0; q[tt ++ ] = x; if (tt == N) tt = 0; hh ++ ; if (hh == N) hh = 0; q[hh]; if (hh != tt)