題目描述

栗醬有一天在網上沖浪的時候發現了一道很有意思的數據結構題。

這個數據結構形如一個“長條形”的容器，一開始該容器是空的，有以下七種操作：

$1$ $a$：從前面插入一個元素 $a$

$2$：從前面刪除一個元素

$3$ $a$：從后面插入一個元素 $a$

$4$：從后面刪除一個元素

$5$：將整個容器頭尾翻轉

$6$：輸出當前容器中元素的個數和所有元素

$7$：將所有元素從小到大排序

請你模擬這個數據結構的所有操作。

輸入格式

第一行包含兩個整數 $n,m$，其中：

$n$ 表示容器中最多可以存儲的元素個數（保證不會超過 $n$）

$m$ 表示操作的總次數

接下來 $m$ 行，每行表示一個操作，格式如上所述。所有操作保證合法（例如不會在容器為空時刪除元素）。

特別地，操作 $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

說明/提示

【數據范圍】：

• $1\le n\le 50000$

• $1\le m\le 200000$

• 所有插入的 $a$ 滿足 $1\le a\le 100000$

提交鏈接

簡單的數據結構

思路分析

deque 就是一個兩頭操作的隊列。

• 有頭插，尾插：push_front()/push_back()
• 有頭刪，尾刪：pop_front()/pop_back()
• 工作性算法：sort（排序），reverse（倒置）

? 操作 1：從前插入

if (op == 1) {cin >> a;q.push_front(a);
}

插入到容器前端，時間復雜度 $O(1)$。

? 操作 2：從前刪除

else if (op == 2) {q.pop_front();
}

刪除容器前端第一個元素，時間復雜度 $O(1)$。

? 操作 3：從后插入

else if (op == 3) {cin >> a;q.push_back(a);
}

插入到容器末尾，時間復雜度 $O(1)$。

? 操作 4：從后刪除

else if (op == 4) {q.pop_back();
}

刪除容器尾部元素，時間復雜度 $O(1)$。

? 操作 5：整體翻轉容器

else if (op == 5) {reverse(q.begin(), q.end());
}

使用 reverse() 函數直接反轉整個 deque。

時間復雜度 O(n)，但題目說明操作次數較少（最多 $10$ 次），完全可以接受。

? 操作 6：輸出容器內容

else if (op == 6) {cout << q.size() << endl;for (int x : q)cout << x << " ";cout << endl;
}

輸出容器當前大小及所有元素。

完整代碼

#include <bits/stdc++.h>
using namespace std;
int main()
{int n, m;cin >> n >> m;deque<int> q;while (m--) // m次操作{int op, a;cin >> op; // 操作幾 1~7if (op == 1){cin >> a;q.push_front(a);}else if (op == 2){q.pop_front();}else if (op == 3){cin >> a;q.push_back(a);}else if (op == 4){q.pop_back();}else if (op == 5){reverse(q.begin(), q.end());}else if (op == 6){cout << q.size() << endl;for (int x : q)cout << x << " ";cout << endl;}else{sort(q.begin(), q.end());}}return 0;
}