【队列】-----【简单的数据结构】

简单的数据结构

题目描述

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

1. a 从前面插入元素 a
2. 从前面删除一个元素
3. a 从后面插入一个元素
4. 从后面删除一个元素
5. 将整个容器头尾翻转
6. 输出个数和所有元素
7. 对所有元素进行从小到大排序

输入描述:

只有一组数据，第一行 $n\le 50000$, $m\le 200000$, $a\le 100000$ 代表最大数据数目和操作次数。

接下来每一行一个操作如上描述。保证所有操作合法（不会在容器为空时删除元素）。

输出描述:

当执行 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

---

题解1（双端队列+模拟）

一、问题分析

题目要求设计一个容器支持如下七种操作：

操作编号	操作说明
1	从前面插入元素 a
2	从前面删除一个元素
3	从后面插入元素 a
4	从后面删除一个元素
5	将整个容器头尾翻转
6	输出当前容器元素个数及所有元素
7	对所有元素从小到大排序

• 容器最初为空。操作均合法，不会出现删除空容器元素的情况。
• 操作 6 和 7 出现次数不超过 10 次，提示可以用排序和遍历。

---

二、核心思路

• 数据结构选择：
  由于需要支持两端插入删除，使用 deque（双端队列）最合适，C++ STL 已提供高效实现。

• 翻转操作（操作5）：
  直接调用 STL 的 reverse 对整个 deque 反转，时间复杂度 $O(n)$，题中操作次数及规模允许。

• 排序操作（操作7）：
  直接使用 STL 的 sort 对 deque 中元素排序，时间复杂度 $O(nlogn)$，最多出现10次，性能可接受。

• 输出操作（操作6）：
  输出元素个数后，依次输出元素，注意格式要求避免行末多余空格。

---

三、完整代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;signed main() 
{int n, m;// 读取最大数据数目 n 和操作次数 mcin >> n >> m;// 使用双端队列 deque 存储元素，支持两端高效插入和删除deque<int> qu;// 处理 m 次操作while (m--) {int a, b;// 读取操作编号 acin >> a;switch (a) {case 1:// 操作1：从前面插入元素 bcin >> b;qu.push_front(b);break;case 2:// 操作2：从前面删除一个元素qu.pop_front();break;case 3:// 操作3：从后面插入元素 bcin >> b;qu.push_back(b);break;case 4:// 操作4：从后面删除一个元素qu.pop_back();break;case 5:// 操作5：将整个容器头尾翻转// 这里直接调用 STL reverse 对 deque 中元素反转reverse(qu.begin(), qu.end());break;case 6:// 操作6：输出当前容器中元素的个数cout << qu.size() << endl;// 如果容器不为空，依次遍历所有元素并输出// 为避免输出行末多余空格，只有当当前元素不是最后一个时才输出空格if (!qu.empty()) {for (int i = 0; i < qu.size(); i++) {cout << qu[i];// 不是最后一个元素，输出空格分隔if (i != qu.size() - 1)  cout << ' ';}// 输出换行符，完成当前行输出cout << endl;  }break;case 7:// 操作7：对所有元素进行从小到大排序sort(qu.begin(), qu.end());break;}}return 0;
}

---

四、复杂度分析

• 插入/删除操作（1、2、3、4）：
  每次操作均为 $O(1)$，deque 支持高效两端操作。

• 翻转操作（5）：
  使用 STL reverse，单次 $O(n)$，由于 m 最大 200000，且翻转次数有限，性能可接受。

• 排序操作（7）：
  最多出现 10 次，每次 $O(nlogn)$，$n\le 50000$，性能允许。

• 输出操作（6）：
  最多出现 10 次，每次输出 $O(n)$，可接受。

---

五、总结

本题通过 STL 双端队列实现，结合直接调用 reverse 和 sort，简单模拟操作流程，代码简洁，逻辑清晰，满足题目要求。
注意输出格式，避免行末多余空格。
若性能有压力，可考虑维护反转状态标志优化翻转操作。

---

---

题解2 : $【O（1）$的翻转复杂度】

一、问题本质

实现一个支持七种操作的“长条形”容器：

操作编号	操作内容
1	从前面插入元素 a
2	从前面删除一个元素
3	从后面插入元素 a
4	从后面删除一个元素
5	将容器翻转（头尾交换）
6	输出当前元素个数 + 所有元素
7	对当前容器中元素排序（升序）

---

二、数据结构选择

使用 deque<int>（双端队列）：

• 插入删除操作的时间复杂度为 $O(1)$
• 支持从两端插入与删除，正好适配前后操作的需要

---

三、核心设计：逻辑顺序与物理顺序分离

引入变量：

bool reversed = false;

用来表示当前容器逻辑顺序是否被翻转：

• false 表示顺序为：左 → 右
• true 表示顺序为：右 → 左（反转视角）

为什么这样设计？

• 避免每次翻转都真正调用 reverse()，节省时间
• 后续插入、删除、输出、排序都通过逻辑顺序判断来模拟真实操作

---

四、各操作的逻辑处理

操作编号	实际处理逻辑
1	如果未反转 → push_front(a)；反转后 → push_back(a)
2	如果未反转 → pop_front()；反转后 → pop_back()
3	如果未反转 → push_back(a)；反转后 → push_front(a)
4	如果未反转 → pop_back()；反转后 → pop_front()
5	逻辑顺序反转：reversed = !reversed（不实际 reverse）
6	输出元素个数与所有元素： - 若未反转 → 正向输出 - 若反转 → 反向输出
7	为了让输出结果满足“升序”， - 若未反转 → 升序排序 - 若已反转 → 降序排序（反向视角看为升序）

---

五、操作 7 的优化与核心思路

题目只要求输出升序，不要求容器保持升序

因此：

• 在 reversed = false 时：直接升序排序；
• 在 reversed = true 时：降序排序，保证后续以反向顺序输出时结果为升序。

---

六、完整代码

优化代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;signed main() {int n, m;// 读取最大容量 n（无实际用途）和操作次数 mcin >> n >> m;deque<int> qu;         // 双端队列，支持两端插入/删除bool reversed = false; // 标记当前容器的逻辑顺序是否被翻转（true 表示从尾到头）while (m--) {int op, x;cin >> op;  // 读取操作编号switch (op) {case 1:// 操作 1：从前面插入元素 xcin >> x;// 如果逻辑顺序未翻转，正常 push_front，否则视为 push_back（逻辑前面变成实际尾部）reversed ? qu.push_back(x) : qu.push_front(x);break;case 2:// 操作 2：从前面删除一个元素// 同理，逻辑前面在 reversed 状态下是容器尾部reversed ? qu.pop_back() : qu.pop_front();break;case 3:// 操作 3：从后面插入元素 xcin >> x;// 如果 reversed 为 true，逻辑“后面”实际是容器头部reversed ? qu.push_front(x) : qu.push_back(x);break;case 4:// 操作 4：从后面删除一个元素reversed ? qu.pop_front() : qu.pop_back();break;case 5:// 操作 5：将逻辑顺序翻转（不真正 reverse 容器，只切换逻辑标志）reversed = !reversed;break;case 6:// 操作 6：输出当前元素个数和所有元素（按当前逻辑顺序）cout << qu.size() << "\n";// 输出元素时根据 reversed 决定是正向遍历还是反向遍历if (!qu.empty()) {if (!reversed) {// 正常顺序，从前往后输出for (int i = 0; i < (int)qu.size(); i++) {cout << qu[i];if (i != (int)qu.size() - 1) cout << ' ';}} else {// 反转顺序，从后往前输出for (int i = (int)qu.size() - 1; i >= 0; i--) {cout << qu[i];if (i != 0) cout << ' ';}}cout << "\n";  // 换行}break;case 7:// 操作 7：对容器中所有元素进行排序// 题目要求输出升序序列// 所以：// - 如果当前为正向逻辑，则直接升序排序// - 如果当前为 reversed 状态，则降序排序，保证反向视角看到的是升序if (reversed) {sort(qu.begin(), qu.end(), greater<int>());  // 降序排列} else {sort(qu.begin(), qu.end());  // 升序排列}// 注意：此种排序方式是为了配合当前 reversed 状态下的“逻辑升序输出”// 容器底层顺序并非始终升序，但能保证操作 6 输出符合题意要求break;}}return 0;
}

每次都根据 reversed 标志来决定“逻辑上的前/后”，以此实现逻辑一致性与物理性能兼顾。

---

七、复杂度分析

操作	时间复杂度
插入/删除	$O(1)$
翻转（标志）	$O(1)$
输出	$O(n)$（最多 10 次）
排序	$O(n\log n)$（最多 10 次）

整体处理在最坏情况下也能通过数据规模限制。

---

八、总结

• 合理使用 deque 双端队列
• 引入 reversed 标志模拟逻辑顺序
• 排序操作结合 reversed 状态实现“伪排序视角对冲”，简洁高效
• 不对容器进行频繁 reverse，避免多余代价
• 输出操作逻辑清晰、无冗余空格处理精妙

---