数组实现各类数据结构
目录
一、数组实现单链表
二、数组实现双链表
三、数组实现栈
四、数组模拟队列
五、数组模拟单调栈
六、数组模拟单调队列（滑动窗口）
一、数组实现单链表
#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;
}