list容器 、数组 模拟栈
----zoj 4016 Mergeable Stack
题意
模拟题，给出三种操作：
- s v 将数字 v 放到 s 栈中
- s 输出 s 栈顶元素，并删除
- s t 将栈 t 合并到 栈 s 中，顺序不变
这一题数据比较大，所以用stack函数会超时；所以用 list 容器。
关于list
list 就是数据结构中的双向链表，内存空间不连续，不支持快速随机存取。
- begin() 和 end() 即头指针和尾指针
- push_back () 和 push_front() 在头部和末端插入元素。
- empty() 判断是否为空
- clear() 清空
遍历list
1#include<stdio.h>
2#include<list>
3using namespace std;
4int main()
5{
6 list<int>l;
7 for(int i=0;i<10;i++)
8 {
9 l.push_back(i+1);
10 }
11 list<int>::iterator it;
12 for(it=l.begin();it!=l.end();it++)
13 printf("%d
",*it);
14 return 0;
15}
撸代码：
1#include<stdio.h>
2#include<algorithm>
3#include<list>
4using namespace std;
5list<long long>s[300010];
6
7/**list stl容器 相当于双向循环链表
8*/
9
10int main()
11{
12 int t;
13 scanf("%d",&t);
14 while(t--)
15 {
16 int n,q;
17 scanf("%d%d",&n,&q);
18 for(int i=1;i<=n;i++)
19 s[i].clear();
20 int op,u,v;
21 for(int i=0;i<q;i++)
22 {
23 scanf("%d",&op);
24 if(op==1)
25 {
26 scanf("%d%d",&u,&v);
27 s[u].push_back(v);
28 }
29 else if(op==2)
30 {
31 scanf("%d",&u);
32 if(!s[u].empty())
33 {
34 /**输出尾部 并且扔掉*/
35 printf("%d
",s[u].back());
36 s[u].pop_back();
37 }
38 else
39 printf("EMPTY
");
40 }
41 else if(op==3)
42 {
43 /**将 v 接到 u 的尾部*/
44 scanf("%d%d",&u,&v);
45 s[u].splice(s[u].end(),s[v]);
46 }
47 }
48 }
49 return 0;
50}
数组模拟栈
撸代码：
1#include<stdio.h>
2#include<list>
3#include<string.h>
4using namespace std;
5const int N = 300010;
6int a[N],top[N],bottom[N],nex[N];
7/**top记录栈顶和bottom栈底 nex记录栈的元素位置 */
8int cnt;
9void push(int s,int v)
10{
11 a[++cnt]=v;
12 if(bottom[s]==0)
13 {
14 bottom[s]=cnt;
15 }
16 /**相当于邻接表 ，看 出栈 就明白了*/
17 nex[cnt]=top[s];
18 top[s]=cnt;
19}
20void pop(int s)
21{
22 if(top[s]==0)
23 printf("EMPTY
");
24 else
25 {
26 printf("%d
",a[top[s]]);
27 top[s]=nex[top[s]];
28 if(top[s]==0)/**若栈中没有元素，那么buttom标记成0*/
29 bottom[s]=0;
30 }
31}
32void mergeStack(int s,int v)
33{
34 if(bottom[s]==0)
35 bottom[s]=bottom[v];
36 nex[bottom[v]]=top[s];///v的栈底 和 s 的栈顶接上
37 top[s]=top[v];
38
39 bottom[v]=top[v]=0;
40}
41int main()
42{
43 int t;
44 scanf("%d",&t);
45 while(t--)
46 {
47 memset(bottom,0,sizeof(bottom));
48 memset(top,0,sizeof(top));
49 memset(nex,0,sizeof(nex));
50 cnt=0;
51 int n,q;
52 scanf("%d%d",&n,&q);
53 while(q--)
54 {
55 int op,x,y;
56 scanf("%d",&op);
57 if(op==1)
58 {
59 scanf("%d%d",&x,&y);
60 push(x,y);
61 }
62 else if(op==2)
63 {
64 scanf("%d",&x);
65 pop(x);
66 }
67 else
68 {
69 scanf("%d%d",&x,&y);
70 if(bottom[y]==0)
71 continue;/**!!!*/
72 mergeStack(x,y);
73 }
74 }
75 }
76}