一種先進後出的資料結構
int st[N];//模擬棧
int idx;//棧中元素數量
st[++idx]=x;//壓棧
return st[idx];//取棧頂元素
if(idx) idx--;//彈出棧頂元素
idx=0;//清空棧
#include <stack>//棧所需的標頭檔案
stack<int> st;
st.top();//返回棧頂元素
st.push(x);//壓棧
st.pop();//彈出棧頂元素
st.empty();//判斷棧是否為空
st.size();//返回棧中元素數量
具有單調性的棧。
在插入時，將不滿足單調性的元素彈出。
//手寫
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);
一種先進先出的資料結構
int q[N],h=1,t;//q為佇列，h為隊頭，t為隊尾
q[++t]=x;//將一個元素x加入佇列
h++;//隊首元素出隊
q[h];//隊頭元素
q[t];//隊尾元素
h=1;//清空佇列
t=0;//同時也是初始化
#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;//同時也是初始化
#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();//返回佇列元素數量
具有單調性的佇列。
注意：單調佇列與雙端佇列相似，均可以在隊頭（隊尾）進行插入或刪除操作。
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);
}
#include <queue>
priority_queue<int> q;
q.top();//查詢堆頂元素
q.empty();//判斷是否為空
q.size();//堆內元素數量
q.push(x);//將元素x加入堆中
q.pop();//刪除堆頂
一種鏈式資料結構。
與陣列的不同點在於陣列是連續儲存的，而連結串列可以是非連續的。
單向連結串列包括資料域和指標域，資料域用來儲存當前位置所儲存的值，指標域用來儲存下一個資料的位置。
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];
}
並查集是一種類似於樹的資料結構，支援合併和查詢兩種操作。
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