牛客 简单的数据结构 （deque，vector，数组模拟）

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

1 从前面插入元素a

2 从前面删除一个元素

3 从后面插入一个元素

4 从后面删除一个元素

5 将整个容器头尾翻转

6 输出个数和所有元素

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

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

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

输出

3
1 5 4
2
5 1
2
1 5

deque题解

PS： 刚刚看到这个题目的时候我第一想到的就是双向队列，因为这个题目就是一个deque的模板题，奈何当时对deque不是很熟悉，之前只遇到过一次，但是这个打算详细说一下，并且记录一下

1.deque就是一个两头操作的队列。
2.有头插，尾插：push_front()/push_back()。
3.有头删，尾删：pop_front()/pop_back()。
4.然后再用一些工作性算法：sort（排序），reverse（倒置）。

接下来就是一个显而易见的代码了

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
char c[maxn];
deque<int> q;
int main()
{
   
    int n, m, x, y;
    scanf("%d%d", &n, &m);
    while (m--)
    {
   
        scanf("%d", &x);
        {
   
            if (x == 1)
            {
   
                scanf("%d", &y);
                q.push_front(y);
            }
            else if (x == 2)
                q.pop_front();
            else if (x == 3)
            {
   
                scanf("%d", &y);
                q.push_back(y);
            }
            else if (x == 4)
                q.pop_back();
            else if (x == 5)
                reverse(q.begin(), q.end());
            else if (x == 6)
            {
   
                printf("%d\n", q.size());
                for (int i = 0; i < q.size(); ++i)
                    printf("%d ", q[i]);
                puts("");
            }
            else
                sort(q.begin(), q.end());
        }
    }
}

vector题解

不得不说vector的功能是在太强大！！！
vector首先它是一个动态数组也就是我们口头的“会变长的数组”，如果你定义了一个vector数组，但是题目给的数据以及超过了这个范围，怎么办？这时候不用担心了，vector会自己变长，他首先会开辟一个是之前两倍的新的空间，然后把之前的数据复制一遍，然后在多的空间继续填空。
vector的下标默认是从零开始的！！，并且它的默认删除和插入都是对开头进行操作

上代码

#include <bits/stdc++.h>
using namespace std;
vector<int> v;

int main()
{
   
    int n, m, op, x;
    scanf("%d%d", &n, &m);
    while (m--)
    {
   
        scanf("%d", &op);
        if (op == 1)
            scanf("%d", &x), v.insert(v.begin(), x);
        else if (op == 2)
            v.erase(v.begin());
        else if (op == 3)
            scanf("%d", &x), v.push_back(x);
        else if (op == 4)
            v.pop_back();
        else if (op == 5)
            reverse(v.begin(), v.end());
        else if (op == 7)
            sort(v.begin(), v.end());
        else
        {
   
            printf("%d\n", v.size());
            for (auto it = v.begin(); it != v.end(); ++it) //auto是一个可以识别变量类型的一种类型
                printf("%d ", *it);                        //因为在数组里面存的都是元素的地址，在地址前面加个*就代表当前数组元素的值
            puts("");
        }
    }
    return 0;
}

数组模拟题解

数组模拟是我没想到的，而且这个模拟处理的很巧妙，从中间开始慢慢填数
数组开两倍（因为如果一直从前插入从0开始下标就是负数了，数组会越界），然后双指针，l记录头的位置，r记录尾的位置，因为排序不超过十次，所以sort（nlogn）不会超时的。
最开始l在2e5的位置（只要数组够大，l再往后一些也是可以的），r=l;

模拟以下操作

1.a从前面插入元素（就是a[–l]=x,如果r=l+1的话，就可以用a[l–]=x）；
2.从前面删除一个元素（++l就相当于删掉最前面的元素）；
3.a从后面插入一个元素（就是a[r++]=x）；
4.从后面删除一个元素（r–就相当于删掉最后面的元素）；
5.将整个容器头尾翻转 ，reverse（a+l,a+r）；
6.输出个数和所有元素 （遍历数组下标l到r输出就好了）；
7.对所有元素进行从小到大排序，sort（a+l,a+r）；

代码

#include <bits/stdc++.h>
using namespace std;
int a[400100];
int main()
{
   
    int l = 200001, r = 200001;
    int n, m, x, y;
    scanf("%d%d", &n, &m);
    while (m--)
    {
   
        scanf("%d", &x);
        if (x == 1)
        {
   
            scanf("%d", &y);
            a[--l] = y;
        }
        else if (x == 2)
            l++;
        else if (x == 3)
        {
   
            scanf("%d", &y);
            a[r++] = y;
        }
        else if (x == 4)
            r--;
        else if (x == 5)
            reverse(a + l, a + r);
        else if (x == 6)
        {
   
            printf("%d\n", r - l);
            for (int i = l; i < r; i++) //这里说明一下，r这个位置为什么不可取，因为在数组里面++，--在前面是先进行运行的，在外面不管在前面和后面效果都是一样的
                                        //因为刚开始从左边放入一个数就是--在变量前面，所以数组左下标在赋值之前已经移动了，而++在变量后面，这下操作是在赋完值后才移动的，所以数组右边界不会到r，而是r-1
                printf("%d ", a[i]);
            puts("");
        }
        else
            sort(a + l, a + r);
    }
    return 0;
}