ZOJ 4016 Mergeable Stack（from The 18th Zhejiang University Programming Contest Sponsored by TuSimple）

模拟题，用链表来进行模拟
  1 # include <stdio.h>
  2 # include <stdlib.h>
  3 typedef struct node
  4 {
  5     int num;
  6     struct node *q;
  7     struct node *h;
  8 }node;
  9 struct Node
 10 {
 11     node *start;
 12     node *end;
 13     int sum;
 14 }m[400000];
 15 int main()
 16 {
 17     int k;
 18     scanf("%d", &k);
 19     while (k--)
 20     {
 21         int n, p;
 22         scanf("%d%d", &n, &p);
 23         for (int i = 0; i <= n; i++)
 24         {
 25             m[i].end = NULL;
 26             m[i].start = NULL;
 27             m[i].sum = 0;
 28         }
 29         for (int i = 0; i<p; i++)
 30         {
 31             int op, s, v, t;
 32             scanf("%d", &op);
 33             if (op == 1)
 34             {
 35                 scanf("%d%d", &s, &v);
 36                 if (m[s].sum == 0)
 37                 {
 38                     m[s].start = (node *)malloc(sizeof(node));
 39                     m[s].start->num = v;
 40                     m[s].start->q = NULL;
 41                     m[s].start->h = NULL;
 42                     m[s].end = NULL;
 43                     m[s].sum = 1;
 44                 }
 45                 else
 46                 if (m[s].sum == 1)
 47                 {
 48                     m[s].end = (node *)malloc(sizeof(node));
 49                     m[s].end->num = v;
 50                     m[s].end->q = m[s].start;
 51                     m[s].end->h = NULL;
 52                     m[s].start->h = m[s].end;
 53                     m[s].sum = 2;
 54                 }
 55                 else
 56                 {
 57                     node * z = (node *)malloc(sizeof(node));
 58                     z->num = v;
 59                     z->q = m[s].end;
 60                     z->h = NULL;
 61                     m[s].end->h = z;
 62                     m[s].end = z;
 63                     m[s].sum++;
 64                 }
 65             }
 66             else
 67             if (op == 2)
 68             {
 69                 scanf("%d", &s);
 70                 if (m[s].sum == 0)
 71                     printf("EMPTY
");
 72                 else
 73                 {
 74                     m[s].sum--;
 75                     if (m[s].sum != 0)
 76                         printf("%d
", m[s].end->num);
 77                     else
 78                         printf("%d
", m[s].start->num);
 79                     if (m[s].sum != 0)
 80                     {
 81                         node *z = m[s].end->q;
 82                         z->h = NULL;
 83                         m[s].end = z;
 84                     }
 85                     else
 86                     {
 87                         m[s].end = NULL;
 88                         m[s].start = NULL;
 89                     }
 90                 }
 91             }
 92             else
 93             {
 94                 scanf("%d%d", &s, &t);
 95                 if (m[s].sum == 0)
 96                 {
 97                     m[s].end = m[t].end;
 98                     m[s].start = m[t].start;
 99                     m[s].sum = m[t].sum;
100                     m[t].sum = 0;
101                     m[t].end = NULL;
102                     m[t].start = NULL;
103                 }
104                 else
105                 if (m[s].sum == 1)
106                 {
107                     m[s].sum += m[t].sum;
108                     m[t].sum = 0;
109                     if (m[t].start != NULL)
110                     {
111                         m[s].end = m[t].start;
112                         m[s].start->h = m[t].start;
113                         m[s].end->q = m[s].start;
114                         if (m[t].end != NULL)
115                             m[s].end = m[t].end;
116                         else
117                             m[s].end = m[t].start;
118                     }
119                     m[t].start = NULL;
120                     m[t].end = NULL;
121                 }
122                 else
123                 {
124                     m[s].sum += m[t].sum;
125                     m[t].sum = 0;
126                     if (m[t].start != NULL)
127                     {
128                         m[s].end->h = m[t].start;
129                         m[t].start->q = m[s].end;
130                         if (m[t].end != NULL)
131                             m[s].end = m[t].end;
132                         else
133                             m[s].end = m[t].start;
134                     }
135                     m[t].start = NULL;
136                     m[t].end = NULL;
137                 }
138             }
139         }
140     }
141     //system("pause");
142     return 0;
143 }