【ACM】Doubly Linked List（STL list）

109 阅读 0 评论 72 点赞

我是靠谱客的博主勤恳黑米，这篇文章主要介绍【ACM】Doubly Linked List（STL list），现在分享给大家，希望可以做个参考。

题目链接：https://vjudge.net/problem/Aizu-ALDS1_3_C

这一题一开始的时候想的是用vector，超时

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
int main ()
{
ll x,n,i;
scanf("%lld",&n);
char command[20];
vector<ll> s;
for(i=1;i<=n;i++)
{
scanf("%s",command);
if(strcmp(command,"insert")==0)
{
scanf("%lld",&x);
s.insert(s.begin(),x);
}
else if(strcmp(command,"delete")==0)
{
scanf("%lld",&x);
vector<ll>::iterator it = s.begin();
for(;it!=s.end();it++)
{
if(*it==x)
{
s.erase(it);
break;
}
}
}
else if(strcmp(command,"deleteFirst")==0)
{
s.erase(s.begin());
}
else if(strcmp(command,"deleteLast")==0)
{
s.pop_back();
}
}
ll size=s.size();
for(i=0;i<size;i++)
{
if(i!=size-1)
cout<< s[i] << " ";
else
cout << s[i] << endl;
}
return 0;
}

换成list

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <list>
#include <algorithm>
typedef long long ll;
using namespace std;
int main ()
{
ll x,n,i;
scanf("%lld",&n);
char command[20];
list<ll> s;
for(i=1;i<=n;i++)
{
scanf("%s",command);
if(strcmp(command,"insert")==0)
{
scanf("%lld",&x);
s.push_front(x);
}
else if(strcmp(command,"delete")==0)
{
scanf("%lld",&x);
list<ll>::iterator it = s.begin();
for(;it!=s.end();it++)
{
if(*it==x)
{
s.erase(it);
break;
}
}
}
else if(strcmp(command,"deleteFirst")==0)
{
s.pop_front();
}
else if(strcmp(command,"deleteLast")==0)
{
s.pop_back();
}
}
i=0;
list<ll>::iterator it=s.begin();
while(it!=s.end())
{
if(i++)
printf(" ");
printf("%lld",*it);
it++;
}
printf("n");
return 0;
}