{x}
blog image

Design Front Middle Back Queue

Design a queue that supports push and pop operations in the front, middle, and back.

Implement the FrontMiddleBack class:

  • FrontMiddleBack() Initializes the queue.
  • void pushFront(int val) Adds val to the front of the queue.
  • void pushMiddle(int val) Adds val to the middle of the queue.
  • void pushBack(int val) Adds val to the back of the queue.
  • int popFront() Removes the front element of the queue and returns it. If the queue is empty, return -1.
  • int popMiddle() Removes the middle element of the queue and returns it. If the queue is empty, return -1.
  • int popBack() Removes the back element of the queue and returns it. If the queue is empty, return -1.

Notice that when there are two middle position choices, the operation is performed on the frontmost middle position choice. For example:

  • Pushing 6 into the middle of [1, 2, 3, 4, 5] results in [1, 2, 6, 3, 4, 5].
  • Popping the middle from [1, 2, 3, 4, 5, 6] returns 3 and results in [1, 2, 4, 5, 6].

 

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]

Explanation:
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 Explanation: Design Front Middle Back Queue

This problem requires designing a queue that supports efficient push and pop operations at the front, middle, and back. A naive approach using a single list would lead to O(n) complexity for middle operations. The optimal solution utilizes two deques (q1 and q2) for efficient handling.

Data Structure:

We use two double-ended queues (deques):

  • q1: Stores the first half of the queue (inclusive of the middle element if the total number of elements is odd).
  • q2: Stores the second half of the queue.

Algorithm:

The core idea is to maintain a balanced state between q1 and q2. The length difference between them should not exceed 1. This ensures all operations (front, middle, back) remain O(1) on average.

  1. pushFront(val): Add val to the beginning of q1. Then call rebalance() to adjust the lengths of q1 and q2.

  2. pushMiddle(val): Add val to the end of q1. Then call rebalance().

  3. pushBack(val): Add val to the end of q2. Then call rebalance().

  4. popFront(): Check if the queue is empty. If not, remove and return the first element from q1 (if not empty), otherwise from q2. Then call rebalance().

  5. popMiddle(): Check if the queue is empty. If not, remove and return the last element from q1 if lengths of q1 and q2 are equal; otherwise remove and return the first element from q2. Then call rebalance().

  6. popBack(): Check if q2 is empty. If not, remove and return the last element from q2. Then call rebalance().

  7. rebalance(): This function maintains the balance between q1 and q2.

    • If q1 becomes longer than q2, move the last element of q1 to the beginning of q2.
    • If q2 becomes more than one element longer than q1, move the first element of q2 to the end of q1.

Time Complexity:

  • All push and pop operations, including rebalance(), have a time complexity of O(1) on average because deque operations (push/pop from front/back) are constant time. The rebalance function only moves at most one element, preserving the O(1) complexity.

Space Complexity:

O(n), where n is the number of elements in the queue, since we store all elements in the two deques.

Code Examples (Python3, Java, C++, Go, TypeScript, Javascript): The code examples are provided in the original response and demonstrate the implementation of the algorithm described above. Each example uses a deque data structure (or its equivalent in the language) to achieve O(1) time complexity for front, middle, and back operations. The rebalance function is crucial for maintaining this efficiency.