简单的数据结构
题目描述
栗酱有一天在网上冲浪的时候发现了一道很有意思的数据结构题。
该数据结构形如长条形。
一开始该容器为空，有以下七种操作。
- a 从前面插入元素 a
- 从前面删除一个元素
- a 从后面插入一个元素
- 从后面删除一个元素
- 将整个容器头尾翻转
- 输出个数和所有元素
- 对所有元素进行从小到大排序
输入描述:
只有一组数据，第一行 n ≤ 50000 n \le 50000 n≤50000, m ≤ 200000 m \le 200000 m≤200000, a ≤ 100000 a \le 100000 a≤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 ) O(n) O(n)，题中操作次数及规模允许。排序操作（操作7）：
直接使用 STL 的sort对 deque 中元素排序，时间复杂度 O ( n l o g n ) O(n log n) O(nlogn)，最多出现10次，性能可接受。输出操作（操作6）：
输出元素个数后，依次输出元素，注意格式要求避免行末多余空格。
三、完整代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
int n, m;
// 读取最大数据数目 n 和操作次数 m
cin >> n >> m;
// 使用双端队列 deque 存储元素，支持两端高效插入和删除
deque<int> qu;
// 处理 m 次操作
while (m--)
{
int a, b;
// 读取操作编号 a
cin >> a;
switch (a)
{
case 1:
// 操作1：从前面插入元素 b
cin >> b;
qu.push_front(b);
break;
case 2:
// 操作2：从前面删除一个元素
qu.pop_front();
break;
case 3:
// 操作3：从后面插入元素 b
cin >> 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 ) O(1) O(1)，deque 支持高效两端操作。翻转操作（5）：
使用 STLreverse，单次 O ( n ) O(n) O(n)，由于 m 最大 200000，且翻转次数有限，性能可接受。排序操作（7）：
最多出现 10 次，每次 O ( n l o g n ) O(nlog n) O(nlogn)， n ≤ 50000 n ≤ 50000 n≤50000，性能允许。输出操作（6）：
最多出现 10 次，每次输出 O ( n ) O(n) O(n)，可接受。
五、总结
本题通过 STL 双端队列实现，结合直接调用 reverse 和 sort，简单模拟操作流程，代码简洁，逻辑清晰，满足题目要求。
注意输出格式，避免行末多余空格。
若性能有压力，可考虑维护反转状态标志优化翻转操作。
题解2 : 【 O （ 1 ） 【O（1） 【O（1）的翻转复杂度】
一、问题本质
实现一个支持七种操作的“长条形”容器：
| 操作编号 | 操作内容 |
|---|---|
| 1 | 从前面插入元素 a |
| 2 | 从前面删除一个元素 |
| 3 | 从后面插入元素 a |
| 4 | 从后面删除一个元素 |
| 5 | 将容器翻转（头尾交换） |
| 6 | 输出当前元素个数 + 所有元素 |
| 7 | 对当前容器中元素排序（升序） |
二、数据结构选择
使用 deque<int>（双端队列）：
- 插入删除操作的时间复杂度为 O ( 1 ) O(1) 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（无实际用途）和操作次数 m
cin >> n >> m;
deque<int> qu; // 双端队列，支持两端插入/删除
bool reversed = false; // 标记当前容器的逻辑顺序是否被翻转（true 表示从尾到头）
while (m--)
{
int op, x;
cin >> op; // 读取操作编号
switch (op)
{
case 1:
// 操作 1：从前面插入元素 x
cin >> 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：从后面插入元素 x
cin >> 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(1) |
| 翻转（标志） | O ( 1 ) O(1) O(1) |
| 输出 | O ( n ) O(n) O(n)（最多 10 次） |
| 排序 | O ( n log n ) O(n\log n) O(nlogn)（最多 10 次） |
整体处理在最坏情况下也能通过数据规模限制。
八、总结
- 合理使用 deque 双端队列
- 引入 reversed 标志模拟逻辑顺序
- 排序操作结合 reversed 状态实现“伪排序视角对冲”，简洁高效
- 不对容器进行频繁 reverse，避免多余代价
- 输出操作逻辑清晰、无冗余空格处理精妙