题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4016
链表模拟 怕爆内存 把所有申请空间的指针都放到一个vector里消除 结果超时。。。 每次top的时候删除居然不会爆内存。。
#include<bits/stdc++.h> #define maxn 100010 #define ll long long #define INF 0x3f3f3f3f3f3f3f3f using namespace std; typedef struct Node *Stack; struct Node { int data; Stack next; }; Stack s[3*maxn]; Stack se[3*maxn]; void Creat(Stack &s) { s=(Stack)malloc(sizeof(Node)); } int main() { int T; cin>>T; while(T--) { for(int i=0;i<3*maxn;i++) { s[i]=NULL; se[i]=NULL; } //vector<Stack> del; int n,p; scanf("%d%d",&n,&p); while(p--) { int x; scanf("%d",&x); if(x==1) { int i,v; scanf("%d%d",&i,&v); if(s[i]==NULL) { Creat(s[i]); // del.push_back(s[i]); s[i]->data=v; s[i]->next=NULL; se[i]=s[i]; } else { Stack st; Creat(st); //del.push_back(st); st->data=v; st->next=s[i]; s[i]=st; } } else if(x==2) { int i; scanf("%d",&i); if(s[i]==NULL) { printf("EMPTY\n"); } else { printf("%d\n",s[i]->data); Stack st=s[i]; s[i]=s[i]->next; delete st; } } else if(x==3) { int i,t; scanf("%d%d",&i,&t); if(s[t]!=NULL) { if(s[i]==NULL) { s[i]=s[t]; s[t]=NULL; se[i]=se[t]; se[t]=NULL; } else { se[t]->next=s[i]; s[i]=s[t]; s[t]=NULL; se[t]=NULL; } } } } // for(int i=0;i<del.size();i++) // { // if(del[i]!=NULL) // delete del[i]; // } } return 0; }在网上看到的一种做法 list的splice函数，C++没怎么用过list。。。。其实和手写没什么区别。。
#include<bits/stdc++.h> #define maxn 100010 #define ll long long #define INF 0x3f3f3f3f3f3f3f3f using namespace std; list<int> l[3*maxn]; int main() { int T; scanf("%d",&T); while(T--) { int n,p; scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) l[i].clear(); while(p--) { int x; scanf("%d",&x); if(x==1) { int i,v; scanf("%d%d",&i,&v); l[i].push_back(v); } if(x==2) { int i; scanf("%d",&i); if(l[i].size()) { printf("%d\n",l[i].back()); l[i].pop_back(); } else printf("EMPTY\n"); } if(x==3) { int i,v; scanf("%d%d",&i,&v); l[i].splice(l[i].end(),l[v]);//list拼接的功能。将源list的内容部分或全部元素删除，拼插入到目的list } } } return 0; }