What is the best way to handle the middle element in Design Front Middle Back Queue?

Track a middle pointer or maintain two balanced deques so that pushMiddle and popMiddle always operate on the frontmost middle node.

Can I solve this problem using only arrays?

Yes, for small constraints a single array works, but you must handle middle index carefully to avoid off-by-one errors and inefficient shifts.

Why is pointer manipulation important in this problem?

Pointer manipulation allows O(1) insertion and removal at middle positions, preventing costly array shifts and maintaining element order.

How do I maintain the correct middle after popFront or popBack?

Update the middle pointer according to the queue size after every operation, moving it forward or backward based on even or odd length changes.

Is there a dual-deque solution for Design Front Middle Back Queue?

Yes, splitting the queue into front and back halves allows efficient middle operations by treating the front deque's end as the middle, balancing after each insertion or removal.

#1670

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

设计前中后队列

请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。请你完成 FrontMiddleBack 类： FrontMiddleBack() 初始化队列。 void pushFront(int val) 将 val 添加到队列的最前面。 void pushMiddle(int …

数组链表设计队列数据流

题目描述

请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。

请你完成 FrontMiddleBack 类：

FrontMiddleBack() 初始化队列。
void pushFront(int val) 将 val 添加到队列的 最前面 。
void pushMiddle(int val) 将 val 添加到队列的 正中间 。
void pushBack(int val) 将 val 添加到队里的 最后面 。
int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。

请注意当有两个中间位置的时候，选择靠前面的位置进行操作。比方说：

将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。
从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。

示例 1：

输入：
["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
[[], [1], [2], [3], [4], [], [], [], [], []]
输出：
[null, null, null, null, null, 1, 3, 4, 2, -1]

解释：
FrontMiddleBackQueue q = new FrontMiddleBackQueue();
q.pushFront(1);   // [1]
q.pushBack(2);    // [1, 2]
q.pushMiddle(3);  // [1, 3, 2]
q.pushMiddle(4);  // [1, 4, 3, 2]
q.popFront();     // 返回 1 -> [4, 3, 2]
q.popMiddle();    // 返回 3 -> [4, 2]
q.popMiddle();    // 返回 4 -> [2]
q.popBack();      // 返回 2 -> []
q.popFront();     // 返回 -1 -> [] （队列为空）

提示：

1 <= val <= 10⁹
最多调用 1000 次 pushFront， pushMiddle， pushBack， popFront， popMiddle 和 popBack 。

lightbulb

解题思路

方法一：两个双端队列

我们用两个双端队列，其中 $q_1$ 存储前半部分，而 $q_2$ 存储后半部分。每次由 rebalance 函数来维护两个队列的平衡性，即保持 $q_2$ 的长度大于等于 $q_1$ 的长度，且长度之差不超过 $1$ 。

在 pushFront、pushMiddle 和 pushBack 函数中，我们只需要将元素添加到 $q_1$ 或 $q_2$ 中，并调用 rebalance 函数即可。

对于 popFront 函数，我们需要判断 $q_1$ 和 $q_2$ 是否为空，如果都为空，则返回 $-1$ ，否则我们需要判断 $q_1$ 是否为空，如果不为空，则弹出 $q_1$ 的队首元素，否则弹出 $q_2$ 的队首元素，并调用 rebalance 函数。

对于 popMiddle 函数，我们需要判断 $q_1$ 和 $q_2$ 是否为空，如果都为空，则返回 $-1$ ，否则我们需要判断 $q_1$ 和 $q_2$ 的长度是否相等，如果相等，则弹出 $q_1$ 的队尾元素，否则弹出 $q_2$ 的队首元素，并调用 rebalance 函数。

对于 popBack 函数，我们只需要判断 $q_2$ 是否为空，如果为空，则返回 $-1$ ，否则弹出 $q_2$ 的队尾元素，并调用 rebalance 函数。

以上操作的时间复杂度均为 $O(1)$ ，空间复杂度为 $O(n)$ ，其中 $n$ 是队列中的元素数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

class FrontMiddleBackQueue:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def pushFront(self, val: int) -> None:
        self.q1.appendleft(val)
        self.rebalance()

    def pushMiddle(self, val: int) -> None:
        self.q1.append(val)
        self.rebalance()

    def pushBack(self, val: int) -> None:
        self.q2.append(val)
        self.rebalance()

    def popFront(self) -> int:
        if not self.q1 and not self.q2:
            return -1
        if self.q1:
            val = self.q1.popleft()
        else:
            val = self.q2.popleft()
        self.rebalance()
        return val

    def popMiddle(self) -> int:
        if not self.q1 and not self.q2:
            return -1
        if len(self.q1) == len(self.q2):
            val = self.q1.pop()
        else:
            val = self.q2.popleft()
        self.rebalance()
        return val

    def popBack(self) -> int:
        if not self.q2:
            return -1
        val = self.q2.pop()
        self.rebalance()
        return val

    def rebalance(self):
        if len(self.q1) > len(self.q2):
            self.q2.appendleft(self.q1.pop())
        if len(self.q2) > len(self.q1) + 1:
            self.q1.append(self.q2.popleft())


# Your FrontMiddleBackQueue object will be instantiated and called as such:
# obj = FrontMiddleBackQueue()
# obj.pushFront(val)
# obj.pushMiddle(val)
# obj.pushBack(val)
# param_4 = obj.popFront()
# param_5 = obj.popMiddle()
# param_6 = obj.popBack()

speed

复杂度分析

指标	值
时间	and space depend on the implementation. A naive array-based solution has O(n) per middle operation due to shifting, while linked list or dual-deque approaches achieve O(1) amortized operations. Space is O(n) for storing all elements.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Pay attention to correctly identifying the frontmost middle for even-length queues.
question_mark
Emphasize pointer updates and balancing after each operation.
question_mark
Check boundary cases where the queue becomes empty or has only one element.

warning

常见陷阱

外企场景

error
Misidentifying the frontmost middle during pushMiddle or popMiddle.
error
Forgetting to update the middle pointer after front or back operations.
error
Assuming array indices map directly to middle positions without adjustments.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement a FrontBackQueue supporting only front and back operations for simplified pointer management.
arrow_right_alt
Support multiple middle operations in batch and analyze pointer consistency under bulk updates.
arrow_right_alt
Extend to a priority FrontMiddleBackQueue where elements have weights affecting their middle placement.

help

常见问题

外企场景

继续练习

#1472 设计浏览器历史记录 #1656 设计有序流 #641 设计循环双端队列