目錄

一、數組實現單鏈表

二、數組實現雙鏈表

三、數組實現棧

四、數組模擬隊列

五、數組模擬單調棧

六、數組模擬單調隊列（滑動窗口）

七、數組模擬堆

---

一、數組實現單鏈表

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
const int N=1e5+10;
int e[N],ne[N],q,head,idx;
//e[i]表示結點i的值
//ne[i]表示結點i的next的指針是多少
//idx存儲當前已經用到了哪個點
void init()
{head=-1;idx=0;e[0]=0;ne[0]=0;
}
//將x插到head---插入操作
void add_to_head(int x)
{e[idx]=x,ne[idx]=head,head=idx,idx++;
}
//將x插到下標為k的點的后面
void add(int k,int x)
{e[idx]=x,ne[idx]=ne[k],ne[k]=idx,idx++;
}
//將下標是k的后面的點刪掉
void remove(int k)
{ne[k]=ne[ne[k]];
}
#if 0
int main(void)
{cin>>q;while(q--){int t;cin>>t;if(t==1){int x,int y;cin>>x>>y;}}return 0;
}
#endif

二、數組實現雙鏈表

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
const int N=1e5+10;
int l[N],r[N],e[N],head,idx;
int n,m;//初始化
void init()
{//0表示左端點 1表示右端點r[0]=1,l[1]=0;idx=2;
}
//在下標為k的右邊插入x
//如果要實現在下標為k的左邊插入x  直接調用add(l[k],x)
void add(int k,int x)
{e[idx]=x;r[idx]=r[k];l[idx]=k;l[r[k]]=idx;//這一步和下一步不可以顛倒r[k]=idx;
}
//刪除第k個點
void remove(int k)
{r[l[k]]=r[k];l[r[k]]=l[k];
}

三、數組實現棧

B3614 【模板】棧 - 洛谷

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
#define int unsigned long long
int stk[N],tt;//tt表示棧頂下標
//1.插入一個元素：stk[++tt]=x;
//2.刪除一個元素：tt--;
//3.判斷棧是否為空：if(tt>0)
//4.棧頂元素：stk[tt];
signed main(void)
{int  t;cin>>t;while(t--){int n;cin>>n;tt=0;for(int i=1;i<=n;i++){string s;cin>>s;if(s=="push"){int x;cin>>x;stk[++tt]=x;}else if(s=="pop"){if(tt==0)cout<<"Empty"<<endl;else tt--;}else if(s=="query"){if(tt>0)cout<<stk[tt]<<endl;else cout<<"Anguei!"<<endl;}else if(s=="size"){cout<<tt<<endl;}}}return 0;
}

四、數組模擬隊列

B3616 【模板】隊列 - 洛谷

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int hh,tt=-1,q[N];//1.隊尾插入一個元素：q[++tt]=x;
//2.彈出：hh++
//3.判斷是否為空：if(hh<=tt)為空 else 非空
//4.取出隊頭元素：q[hh]
int main(void)
{int  t;cin>>t;while(t--){int opt;cin>>opt;if(opt==1){int x;cin>>x;q[++tt]=x;}else if(opt==2){if(hh>tt)cout<<"ERR_CANNOT_POP"<<endl;else hh++;}else if(opt==3){if(hh>tt)cout<<"ERR_CANNOT_QUERY"<<endl;else cout<<q[hh]<<endl;}else if(opt==4){cout<<tt-hh+1<<endl;}}return 0;
}

五、數組模擬單調棧

碼蹄集OJ-山脈

//求一段序列中的每個元素之前的第一個小于它的元素
#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
const int N=3e6+10;
int n,stk[N],tt;
int main(void)
{cin>>n;for(int i=0;i<n;i++){int x;cin>>x;while(tt&&stk[tt]>=x)tt--;if(tt)cout<<stk[tt]<<" ";else cout<<1<<" ";stk[++tt]=x;}return 0;
}

六、數組模擬單調隊列（滑動窗口）

P1886 滑動窗口 /【模板】單調隊列 - 洛谷

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;
const int N=1e6+10;
int q[N],a[N],n,k,tt=-1,hh=0;
int main(void)
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){//判斷隊頭是否已經滑出窗口 如果沒滑出窗口 則hh++while(hh<=tt&&(i-k+1)>q[hh]){hh++;}//將隊列中的元素與第i個元素進行比較，如果隊列中的元素大于當前元素 則彈出while(hh<=tt&&a[q[tt]]>=a[i]){tt--;}q[++tt]=i;if(i>=k)cout<<a[q[hh]]<<" ";}cout<<endl;tt=-1,hh=0;for(int i=1;i<=n;i++){//判斷隊頭是否已經滑出窗口 如果沒滑出窗口 則hh++while(hh<=tt&&(i-k+1)>q[hh]){hh++;}//將隊列中的元素與第i個元素進行比較，如果隊列中的元素大于當前元素 則彈出while(hh<=tt&&a[q[tt]]<=a[i]){tt--;}q[++tt]=i;if(i>=k)cout<<a[q[hh]]<<" ";}return 0;
}

七、數組模擬堆

#include<iostream>
#include<algorithm>using namespace std;
const int N=1e6+10;int h[N],size;
void down(int u)
{int t=u;if(2*u<=size&&h[u*2]<h[t])t=u*2;if(u*2+1<=size&&h[u*2+1]<h[t])t=u*2+1;if(u!=t){swap(h[u],h[t]);down(t);}
}
void up(int u)
{while(u/2>0&&h[u/2]>h[u]){swap(h[u/2],h[u]);up(u/2);}
}
void insert(int x)
{size++; h[size]=x;up(size);
}
void remove()
{h[1]=h[size],size--;down(1),up(1);
}
int main(void)
{int n;cin>>n;while(n--){int op;cin>>op;if(op==1){int x;cin>>x;insert(x);}else if(op==2)cout<<h[1]<<endl;else {remove();}}return 0;
}