0411代码,备战蓝桥杯基础数据结构

本文主要是介绍0411代码,备战蓝桥杯基础数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.单链表

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 1000010;int h,e[N],ne[N],idx;
int m;void addhead(int x){e[idx] = x;ne[idx] = h;h = idx ++;
}void add(int k,int x){e[idx] = x;ne[idx] = ne[k];ne[k] = idx ++;
}void delete1(int k){ne[k] = ne[ne[k]];
}int main()
{cin>>m;char op[2];h = -1;while(m--){scanf("%s",&op);if(op[0] == 'H'){int x;cin>>x;addhead(x);}if(op[0] == 'I'){int k,x;cin>>k>>x;add(k-1,x);}if(op[0] == 'D'){int k;cin>>k;if (k == 0) h = ne[h];//删除头节点要特判！！！！ delete1(k-1);}}	for(int i=h;i!=-1;i=ne[i]){int j = e[i];cout<<j<<' ';}return 0;
}

2.栈：读入string要用cin

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 1000010;int m;
int st[N];
int tt = -1;int main()
{cin>>m;while(m--){string op;cin>>op;if(op == "push"){int x;cin>>x;st[++tt] = x;}if(op == "empty"){if(tt==-1) cout<<"YES"<<endl;else cout<<"NO"<<endl;}if(op == "query"){cout<<st[tt]<<endl;}if(op == "pop"){tt--;}}return 0;}

3.队列

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 1000010;int m;
int q[N];
int tt = -1,hh;int main()
{cin>>m;while(m--){string op;cin>>op;if(op == "push"){int x;cin>>x;q[++tt] = x;}if(op == "empty"){if(hh>tt) cout<<"YES"<<endl;else cout<<"NO"<<endl;}if(op == "query"){cout<<q[hh]<<endl;}if(op == "pop"){hh++;}}return 0;}

4.单调栈

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 1000010;int n;
int st[N];
int tt;int main()
{cin>>n;for(int i=0;i<n;i++){int x;cin>>x;while(tt && st[tt] >= x){tt--;}if(tt) cout<<st[tt]<<' ';//第一个数序号是0，输出-1 else cout<<"-1"<<' ';st[++tt] = x;}return 0; 
}

5.单调队列：注意第二次更新hh=0,tt=-1

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
const int N = 1000010; int n,k;
int q[N],hh,tt=-1;
int a[N];int main()
{cin>>n>>k;for(int i=0;i<n;i++) cin>>a[i];//找最小值 for(int i=0;i<n;i++){while(hh<=tt && i-k+1 > q[hh]){hh++;//q数组是下标 }while(hh<=tt && a[q[tt]] >= a[i]){tt--;//则不可能作为答案输出 } q[++tt] = i;//要先添加进来，在窗口里，可能作为答案输出 if(i >= k-1){cout<<a[q[hh]]<<' ';}}cout<<endl;//找最大值int hh=0,tt=-1;for(int i=0;i<n;i++){while(hh<=tt && i-k+1 > q[hh]){hh++;//q数组是下标 }while(hh<=tt && a[i] >= a[q[tt]]){tt--;//则不可能作为答案输出 } q[++tt] = i;//要先添加进来，在窗口里，可能作为答案输出 if(i >= k-1){cout<<a[q[hh]]<<' ';}} return 0; }