#1670

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Design Front Middle Back Queue

Implement a queue that efficiently handles push and pop operations at the front, middle, and back using pointer manipulation.

array linked list design queue data stream

Problem Statement

Design a queue that allows adding and removing elements from three positions: the front, the middle, and the back. Implement a FrontMiddleBackQueue class with methods to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack. When the queue has two middle choices, always operate on the frontmost middle.

For example, performing pushMiddle or popMiddle must correctly identify the frontmost middle index in cases of even length. You must ensure all operations maintain correct element ordering and handle empty states properly. Optimize for clarity and pointer manipulation, as naive indexing may fail in middle operations.

Examples

Example 1

Input: ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"] [[], [1], [2], [3], [4], [], [], [], [], []]

Output: [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(); // return 1 -> [4, 3, 2] q.popMiddle(); // return 3 -> [4, 2] q.popMiddle(); // return 4 -> [2] q.popBack(); // return 2 -> [] q.popFront(); // return -1 -> [] (The queue is empty)

Constraints

1 <= val <= 109
At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

Solution Approach

Use a Linked List with Pointers

Maintain a doubly linked list to track elements, keeping pointers to the head, tail, and middle. Update the middle pointer whenever an element is added or removed to ensure middle operations access the correct node. This approach emphasizes pointer manipulation and avoids array shifting overhead.

Dual-Deque Approach

Split the queue into two deques representing the front and back halves. Maintain balance such that the front deque always contains the frontmost half of elements. Middle insertions and removals then correspond to pushing or popping from the end of the front deque, simulating pointer-based middle access efficiently.

Array-Based Brute Force

For low operation constraints, a single array can be used. Perform pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack via array inserts and removals. Be careful with middle index calculation to always select the frontmost middle. This approach is simple but emphasizes failure modes if middle positions are miscalculated.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Two Deques

We use two deques, where $q_1$ stores the first half, and $q_2$ stores the second half. The `rebalance` function is used to maintain the balance between the two queues, i.e., keeping the length of $q_2$ greater than or equal to the length of $q_1$, and the difference in length does not exceed $1$.

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

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()

Continue Practicing

#1472 design browser history #1656 design an ordered stream #641 design circular deque