题解 | #简单的数据结构#

简单的数据结构

https://ac.nowcoder.com/acm/problem/14661

链接：https://ac.nowcoder.com/acm/contest/22904/1012
来源：牛客网

题目描述

栗酱有一天在网上冲浪的时候发现了一道很有意思的数据结构题。

该数据结构形如长条形。

一开始该容器为空，有以下七种操作。

1 a从前面插入元素a

2 从前面删除一个元素

3 a从后面插入一个元素

4 从后面删除一个元素

5 将整个容器头尾翻转

6 输出个数和所有元素

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

输入描述:

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

输出描述:

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

看到这一题是在秋季算法入门班的第五章习题：优先队列与并查集里面，当时想了好久怎么用优先队列做，然后放弃了，还是双端队列完美的契合这一题

双端队列的一些基本操作如下

1.push_back()：在队列尾部添加元素，无返回值。这个操作跟普通队列（queue）的push()方法类似，在队列的尾部添加一个元素；
2.push_front()：在队列头部添加元素，无返回值；
3.pop_back()：删除队列尾部的元素，无返回值；
4.pop_front()：删除队列头部的元素，无返回值；
5.front() ：获得队列头部元素。此函数返回值为队列的头部元素，常与pop_front()函数一起，先通过front()获得队列头部元素，然后用pop_front()将其从队列中删除；
6.back()：获得队列尾部元素。此函数返回值为队列的尾部元素，常与pop_back()函数一起，先通过back()获得队列头部元素，然后用pop_back()将其从队列中删除；
7.size()：获得队列大小。此函数返回队列的大小，返回值是“size_t”类型的数据，“size_t”是“unsigned int”的别名；
8.empty() ：判断队列是否为空。此函数返回队列是否为空，返回值是bool类型。队列空：返回true；不空：返回false。

本题用到上面的1,2,3,4,5,7

对于升序排序，可以用STL库里的sort()函数排序，但是要注意写法

对于前后倒置，可以用STL库里的reverse()函数排序，其格式为reverse(dq.begin(),dq.end()); 其中dp为deque的队列名（自己取的）

最后按情况1,2,3,4,5,6,7的顺序依次写代码就行了

代码如下：

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int main(){
    deque<int>dq;
    int n,m,a,tmp,da;
    scanf("%d %d",&n,&m);
    while(m--){
        scanf("%d",&tmp);
        if(tmp==1){
            scanf("%d",&da);
            dq.push_front(da);
        }
        if(tmp==2) dq.pop_front();
        if(tmp==3){
            scanf("%d",&da);
            dq.push_back(da);
        }
        if(tmp==4) dq.pop_back();
        if(tmp==5) reverse(dq.begin(),dq.end()); //reverse函数是这样写哦
        if(tmp==6){
            printf("%d\n",dq.size());
            if(dq.size()){
                printf("%d",dq[0]);
                for(int i=1;i<dq.size();i++){
                    printf(" %d",dq[i]); //注意末尾不要有空格
                }
                printf("\n");
            }
        }
        if(tmp==7) sort(dq.begin(),dq.end()); //sort排序是这样写哦
    }
    return 0;
}

P.S.：期末考试终于考完了，有时间继续学习算法啦，开心Ciallo～(∠・ω< )⌒☆