包括单链表，双链表，栈，队列，单调栈，单调队列，KMP，Trie,并查集,堆,哈希
#include<iostream>
using namespace std;
const int N=1e5+9;
int idx=0,e[N],ne[N],head=-1;
void to_head(int val){
e[idx]=val;
ne[idx]=head;
head=idx++;
}
void del(int k){
ne[k]=ne[ne[k]];
}
void in(int k,int val){
e[idx]=val;
ne[idx]=ne[k];
ne[k]=idx++;
}
int main(){
int n;
char op[2];
scanf("%d",&n);
while(n--){
cin>>op;
int x,r;
if(op[0]=='H'){
scanf("%d",&x);
to_head(x);
}
else if(op[0]=='D'){
scanf("%d",&x);
if(!x)head=ne[head];
else del(x-1);
}
else if(op[0]=='I'){
scanf("%d%d",&x,&r);
in(x-1,r);
}
}
for(int i=head;i!=-1;i=ne[i]){
cout<<e[i]<<' ';
}
}
#include<iostream>
#include<string>
using namespace std;
const int N=1e5+9;
int idx,e[N],r[N],l[N];
string op;
void in(int k,int val){
e[idx]=val;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx++;
}
void del(int k){
l[r[k]]=l[k];
r[l[k]]=r[k];
}
int main(){
int n;scanf("%d",&n);
idx=2;
int k,val;
r[0]=1;l[1]=0;
while(n--){
cin>>op;
if(op=="L"){
cin>>val;
in(0,val);
}
else if(op=="R"){
cin>>val;
in(l[1],val);
}
else if(op=="D"){
cin>>k;
del(k+1);
}
else if(op=="IL"){
cin>>k>>val;
in(l[k+1],val);
}
else if(op=="IR"){
cin>>k>>val;
in(k+1,val);
}
}
for(int i=r[0];i!=1;i=r[i]){
cout<<e[i]<<' ';
}
}
#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+9;
int hh=-1,e[N],ee=0;
string op;
int main(){
int n;cin>>n;
int val;
while(n--){
cin>>op;
if(op=="push"){
cin>>val;
e[++hh]=val;
}
else if(op=="query"){
cout<<e[hh]<<'\n';
}
else if(op=="empty"){
if(hh==-1)cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
else if(op=="pop"){
hh--;
}
}
}
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<stack>
using namespace std;
stack<int> num;
stack<char> op;
void eval(){
auto c=num.top();num.pop();
auto b=num.top();num.pop();
auto a=op.top();op.pop();
int x;
if(a=='+')x=b+c;
else if(a=='-')x=b-c;
else if(a=='*')x=b*c;
else if(a=='/')x=b/c;
num.push(x);
}
int main(){
unordered_map<char,int> pr{ {'+',1},{'-',1},{'*',2},{'/',2}};
string str;cin>>str;
for(int i=0;str[i];i++){
auto c=str[i];
if(isdigit( c )){
int x=0,j=i;
while(j<str.size() && isdigit(str[j])){
x= x*10+ str[j++]-'0';
}
i=j-1;
num.push(x);
}
else if(c =='('){
op.push(c);
}
else if(c==')' ){
while( op.top() !='(')eval();
op.pop();
}
else {
while(op.size() && op.top() !='(' && pr[op.top()]>= pr[c])eval();
op.push(c);
}
}
while(op.size())eval();
cout<<num.top();
}
#include<iostream>
#include<string>
using namespace std;
const int N=1e5+9;
string op;
int hh=0,ee=-1,e[N];
int val;
int main(){
int n;cin>>n;
while(n--){
cin>>op;
if(op=="push"){
cin>>val;
e[++ee]=val;
}
else if(op=="empty"){
if(hh<=ee)cout<<"NO"<<'\n';
else cout<<"YES"<<'\n';
}
else if(op=="query"){
cout<<e[hh]<<'\n';
}
else {
hh++;
}
}
}
单调栈
给定一个长度为 N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1
#include<iostream>
using namespace std;
const int N=1e5+9;
int stk[N],tt;
int main(){
int n;
cin>>n;
int val;
for(int i=0;i<n;i++){
cin>>val;
while(tt&& stk[tt]>=val)tt--;
if(tt==0)cout<<"-1 ";
else cout<<stk[tt]<<' ';
stk[++tt]=val;
}
}
(单调队列)滑动窗口
任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
#include<iostream>
using namespace std;
const int N=1e6+9;
int yuan[N],que[N],front,endd=-1;
int main(){
int n,k;cin>>n>>k;
for(int i=0;i<n;i++)scanf("%d",&yuan[i]);
for(int i=0;i<n;i++){
if(front<= endd && i-k+1 > que[front])front++;
while(front<= endd && yuan[i]<=que[endd])endd--;
que[++endd]=i;
if(i>=k-1)cout<<yuan[que[front]]<<' ';
}
puts("");
front =0;endd=-1;
for(int i=0;i<n;i++){
if(front <=endd &&i-k+1>que[front])front++;
while(front <= endd && yuan[que[endd]]<=yuan[i])endd--;
que[++endd]=i;
if(i>=k-1)printf("%d ",yuan[que[front]);
}
}
#include<iostream>
using namespace std;
const int N=1e5+9,M=1e6+9;
char zi[N],mu[M];
int nex[N];
int main(){
//KMP 下标从1开始
int n,m;cin>>n>>zi+1>>m>>mu+1;
//求nex[N]数组
for(int i=2,j=0;i<=n;i++)
{
while( j &&zi[i]!=zi[j+1])j=nex[j];
if(zi[i]==zi[j+1])j++;
nex[i]=j;
}
//KMP匹配
for(int i=0,j=0;i<=m;i++)
{
while(j && mu[i]!=zi[j+1] )j=nex[j];//不匹配->回退->匹配
if(mu[i]==zi[j+1])j++;
if(j==n){
printf("%d ",i-n );
j=nex[j];
}
}
}
#include<iostream>
using namespace std;
const int N=2e4+9;
int sun[N][26],cnt[N],idx;
char aa[N];
void insert(char str[]){
int p =0;
for(int i=0; str[i]; i++){
int u=str[i] - 'a';
if(! sun[p][u] )sun[p][u]=++idx;
p=sun[p][u];
}
cnt[p]++;
}
int query(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]- 'a';
if(! sun[p][u] )return 0;
p=sun[p][u];
}
return cnt[p];
}
int main(){
int n;
cin>>n;
char op[2];
while(n--){
cin>>op>>aa;
if(op[0]=='I')insert(aa);
else cout<<query(aa)<<'\n';
}
return 0;
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int p[N];
int find (int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)p[i]=i;
char op[2];int a,b;
while(m--){
scanf("%s%d%d",op,&a,&b);
if(op[0]=='M'){
p[find(a)]=find(b);
}
else {
if(find(a)==find(b))puts("Yes");
else puts("No");
}
}
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int p[N],cnt[N];
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main(){
int n ,m;
cin>>n>>m;
for(int i=1;i<=n;i++)p[i]=i,cnt[i]=1;
char op[2];int a,s;
while(m--){
scanf("%s",op);
if(op[0]=='C'){ //在点 a和点 b 之间连一条边，a 和 b可能相等
scanf("%d%d",&a,&s);
if(find(a)==find (s))continue;
cnt[find(a)]+=cnt[find(s)];
p[find(s)]=find(a);
}
else if(op[1]=='1'){ //询问点a和点b是否在同一个连通块中，a和 b 可能相等；
scanf("%d%d",&a,&s);
puts(find(a)==find(s)?"Yes":"No");
}
else { //询问点 a所在连通块中点的数量；
scanf("%d",&a);
printf("%d\n",cnt[find(a)]);
}
}
}
#include<iostream>
using namespace std;
const int N=1e5+9;
int dui[N],count;
void down(int i){
int u= i;
if( u*2 <= count && dui[u*2]<dui[i])i=u*2;
if(u*2+1 <=count && dui[u*2+1] <dui[i])i=u*2+1;
if(i!=u){
swap(dui[i],dui[u]);
down (i);
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&dui[i]);
count=n;
for(int i=n/2;i>0;i--)down (i);
while(m--){
printf("%d " ,dui[1]);
swap(dui[1],dui[count]);
count--;
down(1);
}
}
#include <cstring>
#include <iostream>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N];
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
int main()
{
memset(h, 0x3f, sizeof h);
int n;
scanf("%d", &n);
while (n -- )
{
char op[2];
int x;
scanf("%s%d", op, &x);
if (*op == 'I') h[find(x)] = x;
else
{
if (h[find(x)] == null) puts("No");
else puts("Yes");
}
}
return 0;
}
