基础数据结构介绍

栈 \(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}\) 将其封装，既方便使用，又提高了代码的整洁度和可观性。