STL——简单的数据结构

题目描述

栗酱有一天在网上冲浪的时候发现了一道很有意思的数据结构题。
该数据结构形如长条形。
一开始该容器为空，有以下七种操作。

1 a从前面插入元素a

2 从前面删除一个元素

3 a从后面插入一个元素

4 从后面删除一个元素

5 将整个容器头尾翻转

6 输出个数和所有元素

7 对所有元素进行从小到大排序

输入描述：

只有一组数据，第一行n≤50000,m≤200000, a≤100000 代表最大数据数目和操作次数。
接下来每一行一个操作如上描述。保证所有操作合法（不会在容器为空时删除元素）。
6、7操作共计不会超过10次。

输出描述：

当执行6操作时，第一行先输出当前的个数，然后从头到尾按顺序输出，每两个元素之间用一个空格隔开，末尾不能有空格。

示例

输入

10 9
1 1
3 5
3 4
6
4
5
6
7
6

输出

3
1 5 4
2
5 1
2
1 5

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main()
{int n,m,a;vector<int> s;vector<int> :: iterator it;cin>>n>>m;while(m--){cin>>a;int b;switch(a){case 1:cin>>b;it=s.begin();s.insert(it,b);break;case 2:it=s.begin();s.erase(it);break;case 3:cin>>b;s.push_back(b);break;case 4:s.pop_back();break;case 5:reverse(s.begin(),s.end());break;case 6:cout<<s.size()<<endl;for(int i=0;i<s.size();i++){if(i!=s.size()-1){printf("%d ",s[i]);}else{printf("%d\n",s[i]);}}break;case 7:sort(s.begin(),s.end());break;}}return 0;
}

分析

这题我用的是vector，要注意的是vector不能使用push_front()和pop_front()，但是双端队列deque可以使用，而这题也可以使用双端队列来写。