你好，同学！欢迎来到 NOI 数据结构专题强化训练。

今天我们要挑战的是一个极具实战意义的题目：设计前中后队列。这道题在 LeetCode 上考查的是对双端队列的运用，但在 NOI 竞赛中，它代表了 “动态中位数维护” 和 “双结构平衡” 这一类重要算法模型。

一、 预备知识点

在动手前，请确保你已经掌握：

1. 双端队列（Deque）：支持在首尾两端以 $O(1)$ 时间复杂度进行插入和删除。
2. C++ STL std::deque：常用操作包括 push_front, push_back, pop_front, pop_back 以及 size()。
3. 双队列平衡思想：使用两个队列（左队列 $L$ 和右队列 $R$）来维护一个线性结构，通过控制两个队列的长度差，使得中点操作变得高效。

二、 NOI 竞赛题目描述

题目名称：设计前中后队列 (Design Front Middle Back Queue) 时间限制：1.0s 内存限制：256MB

【问题描述】 请你设计一个队列，支持在前、中、后三个位置进行插入和弹出操作。 具体需要实现以下 6 种操作：

1. pushFront(val)：将 val 添加到队列最前面。
2. pushMiddle(val)：将 val 添加到队列的正中间。
3. pushBack(val)：将 val 添加到队列最后面。
4. popFront()：从队列最前面弹出元素并返回。
5. popMiddle()：从队列正中间弹出元素并返回。
6. popBack()：从队列最后面弹出元素并返回。

【关于中点的定义】：

• 插入中点：如果队列长度为 $n$，新元素插入后的索引应为 $n / 2$（下标从 0 开始）。
• 弹出中点：如果队列长度为 $n$，应弹出索引为 $(n - 1) / 2$ 的元素。
• 注意：如果队列为空，弹出操作均返回 $-1$。

【输入格式】 第一行包含一个整数 $Q$，表示操作总数。 接下来的 $Q$ 行，每行为一个操作命令及参数（如有）。

【输出格式】 对于每个 pop 类操作，输出其返回的整数值，每个结果占一行。

【样例输入】

12
pushFront 1
pushBack 2
pushMiddle 3
pushMiddle 4
popFront
popMiddle
popMiddle
popBack
popFront

(注：此处样例简化，实际输入对应 12 次操作)

【样例输出】

1
3
4
2
-1

【数据规模与约定】

• $1 \le Q \le 1000$
• $1 \le val \le 10^9$
• 所有操作均在合法整数范围内。

三、 启发式思路引导：草稿纸上的推演

在 NOI 中，如果要实现 $O(1)$ 或 $O(1)$ 均摊时间复杂度的中点操作，最好的办法是**“对半开”**。

1. 核心模型：天平平衡法

想象两个容器：Left (L) 和 Right (R)。

• 我们规定一个平衡条件：右队列 $R$ 的长度始终等于左队列 $L$ 的长度，或者比 $L$ 多 1 个。
• 即：$L.size() \le R.size() \le L.size() + 1$。

2. 草稿模拟：插入 1, 2, 3

1. 初始：$L = (), R = ()$
2. pushBack 1：加入 $R \rightarrow L = (), R = (1)$。平衡。
3. pushBack 2：加入 $R \rightarrow L = (), R = (1, 2)$。不平衡（$R$ 太长），将 $R$ 的首位移动到 $L$ 末尾 $\rightarrow L = (1), R = (2)$。平衡。
4. pushBack 3：加入 $R \rightarrow L = (1), R = (2, 3)$。平衡。

3. 中点操作推演

• 插入中点 (pushMiddle)：
  • 如果 $L.size() < R.size()$，说明总数是奇数。为了插入到 $n/2$，我们需要把 $R$ 的第一个元素挪到 $L$ 后，再把新元素放进 $R$ 的最前面。
• 弹出中点 (popMiddle)：
  • 根据平衡条件，中点元素要么是 $L$ 的最后一个，要么是 $R$ 的第一个。具体取决于总数的奇偶性。

四、 算法流程图（伪代码逻辑）

为了在考场上写出逻辑清晰的代码，请参考以下“双队列平衡维护”流程。

graph TD
    subgraph Balance_Logic
    B1{L.size 大于 R.size} -- 是 --> B2(L尾移动到R头)
    B1 -- 否 --> B3{R.size 大于 L.size 加 1}
    B3 -- 是 --> B4(R头移动到L尾)
    B4 --> End(平衡结束)
    B2 --> End
    B3 -- 否 --> End
    end

    subgraph Push_Middle
    P1(开始 pushMiddle x) --> P2{L.size 等于 R.size}
    P2 -- 是 --> P3(直接 R.push_front x)
    P2 -- 否 --> P4(L.push_back x)
    P3 --> Balance_Logic
    P4 --> Balance_Logic
    end

    subgraph Pop_Middle
    M1(开始 popMiddle) --> M2{总数为 0?}
    M2 -- 是 --> M3(返回 -1)
    M2 -- 否 --> M4{L.size 等于 R.size?}
    M4 -- 是 --> M5(弹出 L 尾部元素并返回)
    M4 -- 否 --> M6(弹出 R 头部元素并返回)
    M5 --> Balance_Logic
    M6 --> Balance_Logic
    end

五、 复杂度分析与优化建议

• 时间复杂度：
  • 所有操作均为 $O(1)$。
  • 原因：std::deque 的首尾操作是常数时间的，而我们每次操作后最多只进行一次跨队列的元素移动（平衡维护）。
• 空间复杂度：$O(Q)$。存储所有输入的元素。
• NOI 考场建议：
  • 如果 $Q$ 规模较小（如 1000），使用 std::vector 并在 $O(N)$ 插入也是可以接受的。但如果 $Q$ 达到 $10^5$ 以上，必须使用双 deque 或手动维护链表。

六、 读题关键词总结

1. “中点” (Middle)：只要涉及到线性结构的中点动态变化，优先思考**“对半分割”**（双栈、双队列或双堆）。
2. “索引 $n/2$”：这是平衡条件的数学依据，决定了多出的那个元素该放在左边还是右边。
3. “弹出并返回”：注意空队列时的特殊处理（返回 $-1$）。

教练寄语： 这道题是“数据结构解构”的经典案例。我们把一个复杂的“前中后”队列拆解成两个简单的“双端”队列，通过一个简单的“平衡规则”将复杂度从 $O(N)$ 降到了 $O(1)$。这就是算法竞赛中**“分治与平衡”**的魅力。去写出你的代码实现吧！