基础数据结构介绍
栈 /(luoguB3614/)
概念
一种先进后出的数据结构
实现方法
手写栈（用数组模拟）
int st[N];//模拟栈 int idx;//栈中元素数量 st[++idx]=x;//压栈 return st[idx];//取栈顶元素 if(idx) idx--;//弹出栈顶元素 idx=0;//清空栈 STL库
#include <stack>//栈所需的头文件 stack<int> st; st.top();//返回栈顶元素 st.push(x);//压栈 st.pop();//弹出栈顶元素 st.empty();//判断栈是否为空 st.size();//返回栈中元素数量 单调栈 /(luogu5788/)
概念
具有单调性的栈。
维护一个单调栈（/(st/)）
插入
在插入时，将不满足单调性的元素弹出。
//手写 int st[N],idx=0; inline void add(int x) { while(idx!=0&&st[idx]<x) idx--; st[++idx]=x; } //STL stack<int> st; while(!st.empty()&&st.top()<x) st.pop(); st.push(x); 其余操作（读取栈顶元素，返回栈顶数量等）与栈操作相同
队列 /(luoguB3616/)
概念
一种先进先出的数据结构
实现方法
手写（用数组模拟）
int q[N],h=1,t;//q为队列，h为队头，t为队尾 q[++t]=x;//将一个元素x加入队列 h++;//队首元素出队 q[h];//队头元素 q[t];//队尾元素 h=1;//清空队列 t=0;//同时也是初始化 STL库
#include <queue>//队列所需头文件 queue<int> q;//队列 q.front();//队首元素 q.back();//队尾元素 q.push(x);//将元素x添加到队列中 q.pop();//弹出队首元素 q.empty();//判断队列是否为空 q.size();//返回队列元素数量 双端队列
概念
与普通队列的不同之处在于双端队列可以在队头/队尾添加（删除）元素。
实现方法
手写双端队列（用数组模拟）
int q[N],h=1,t;//q为队列，h为队头，t为队尾 q[++t]=x;//将一个元素x加入队首 q[--h]=x;//将一个元素x加入队尾 h++;//队首元素出队 t--;//队尾元素出队 q[h];//队头元素 q[t];//队尾元素 h=1;//清空队列 t=0;//同时也是初始化 STL库
#include <deque>//双端队列所需头文件 deque<int> q; q.front();//查询队头元素 q.back();//查询队尾元素 q.push_back(x);//在队尾插入元素x q.push_front(x);//在队首插入元素x q.pop_back();//在队尾弹出元素 q.pop_front();//在队首弹出元素 q.empty();//判断队列是否为空 q.size();//返回队列元素数量 单调队列 /(luogu1886/)
概念
具有单调性的队列。
注意：单调队列与双端队列相似，均可以在队头（队尾）进行插入或删除操作。
维护一个单调队列（/(q/)）
插入
int q[N],h=1,t; inline void add(int x) { while(h<=t&&q[t]<=x) t--; q[++t]=x; } 其余操作（查询元素，判断是否为空等）与双端队列相同
优先队列（堆）
概念
堆其实是一棵完全二叉树，而优先队列是一个大根堆。
因此可以用一维数组来进行模拟堆。
堆的实现方法
手写（用一维数组模拟）
int h[N],idx;//h模拟堆，idx为堆内元素数量 void down(int x)//向下调整堆 { int t=x; if(x*2<=idx&&h[x*2]<h[t]) t=x*2; if(x*2+1<=idx&&h[x*2+1]<h[t]) t=x*2+1; if(x!=t) { int tmp=h[x]; h[x]=h[t]; h[t]=tmp; down(t); } } void up(int x)//向上调整堆 { while(x/2&&h[x/2]>h[x]) { int t=h[x/2]; h[x/2]=h[x]; h[x]=t; x/=2; } } inline void add(int x)//将元素x插入堆 { h[++idx]=x; up(x); } inline int minn()//返回堆内最小值 { return h[1]; } inline void delete_minn()//删除堆内最小值 { h[1]=h[idx]; idx--; down(1); } inline void _delete(int x)//删除堆内第x个元素 { h[x]=h[idx]; idx--; up(x); down(x); } inline void write(int x,int y)//将第x个元素修改为第y个元素 { h[x]=h[y]; up(x); down(x); } STL库（优先队列）
#include <queue> priority_queue<int> q; q.top();//查询堆顶元素 q.empty();//判断是否为空 q.size();//堆内元素数量 q.push(x);//将元素x加入堆中 q.pop();//删除堆顶 单向链表 /(luoguB3631/)
概念
一种链式数据结构。
与数组的不同点在于数组是连续存储的，而链表可以是非连续的。
链表相关操作
单向链表包括数据域和指针域，数据域用来存储当前位置所存储的值，指针域用来存储下一个数据的位置。
int e[N],ne[N],idx,h=-1; inline void add_front(int x)//在链表头插入元素x { e[idx]=e; ne[idx]=h; h=idx++; } inline void delete_front()//删除链表头元素 { h=ne[h]; } inline void add(int x,int i)//在第i个元素后面插入元素x { e[idx]=x; ne[idx]=ne[i]; ne[i]=idx++; } inline void _delete(int i)//将第i个元素删除 { ne[i]=ne[ne[i]]; } 双向链表
概念
与单链表的不同之处在于指针域有左右之分。
代码实现
int e[N],l[N],r[N],idx; inline void init()//初始化 { r[0]=1; l[1]=0; idx=2; } inline void add(int x,int i)//在第i个数据的右边插入数据x { e[idx]=x; l[idx]=i; r[idx]=r[i]; l[r[i]]=idx; r[i]=idx++; } inline void _delete(int i)//删除第i个结点 { l[r[i]]=l[i]; r[l[i]]=r[i]; } 并查集 /(luogu3367/)
概念
并查集是一种类似于树的数据结构，支持合并和查询两种操作。
代码实现
int fa[N]; inline void init(int n)//初始化 { for(register int i=1;i<=n;i++) { fa[i]=i; } } int f(int x)//查找操作 { if(fa[x]!=x) fa[x]=f(fa[x]);//路径压缩 return fa[x]; } inline void unionSet(int x,int y)//合并操作 { fa[f(x)]=f(y); } 数据结构实际运用
-
队列 广搜
-
优先队列 dijkstra堆优化（最短路算法）
-
链表 邻接表存图（也就是若干个单链表）
-
并查集 Kruskal（最小生成树算法）
-
单调队列/单调栈 优化dp
一些建议
- 在手动模拟数据结构时，若操作较多，可用 /(/text {struct}/) 将其封装，既方便使用，又提高了代码的整洁度和可观性。
