简单的数据结构 (deque的应用)

杨鹏伟

发布于 2020-09-10 23:51:55

5290

发布于 2020-09-10 23:51:55

文章被收录于专栏：ypw

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

1 a从前面插入元素a

2 从前面删除一个元素

3 a从后面插入一个元素

4 从后面删除一个元素

5 将整个容器头尾翻转

6 输出个数和所有元素

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

输入描述: 只有一组数据，第一行n≤50000,m≤200000, a≤100000 代表最大数据数目和操作次数。接下来每一行一个操作如上描述。保证所有操作合法（不会在容器为空时删除元素）。 6、7操作共计不会超过10次。输出描述: 当执行6操作时，第一行先输出当前的个数，然后从头到尾按顺序输出，每两个元素之间用一个空格隔开，末尾不能有空格。

思路：这个题完全是为双向队列而出题的！

#include<bits/stdc++.h>
#define IOS ios::sync_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

deque<int> st;
int main(){
	//IOS;
	int n,m;
	cin>>n>>m;
	while(m--){
		int k;
		cin>>k;
		int res;
		if(k==1){
		 cin>>res;
		 st.push_front(res);
		}
		if(k==2){
			st.pop_front(); 
		}
		if(k==3){
			cin>>res;
			st.push_back(res);
		}
		if(k==4){
			st.pop_back();
		}
		if(k==5){
			reverse(st.begin(),st.end() );
		}
		if(k==6){
			cout<<st.size()<<endl;
			for(auto i=st.begin();i!=st.end();i++){
				cout<<*i<<" ";
			}
			cout<<endl;
		}
		if(k==7){
			sort(st.begin(),st.end());
		} 
	} 
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/06/01 ，如有侵权请联系 cloudcommunity@tencent.com 删除

容器