Design Front Middle Back Queue - Practice Coding Problems

Design Front Middle Back Queue - Problem

Array Linked List Design Queue Data Stream Medium

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

Implement the FrontMiddleBackQueue class:

FrontMiddleBackQueue() 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].

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "popFront", "popMiddle", "popBack"], values = [null, 1, 2, 3, null, null, null]

› Output: [null, null, null, null, 1, 3, 2]

💡 Note: Initialize queue → pushFront(1): [1] → pushBack(2): [1,2] → pushMiddle(3): [1,3,2] → popFront() returns 1: [3,2] → popMiddle() returns 3: [2] → popBack() returns 2: []

Example 2 — Empty Queue Operations

$ Input: operations = ["FrontMiddleBackQueue", "popFront", "popMiddle", "popBack"], values = [null, null, null, null]

› Output: [null, -1, -1, -1]

💡 Note: Initialize empty queue → All pop operations on empty queue return -1

Example 3 — Middle Position Rules

$ Input: operations = ["FrontMiddleBackQueue", "pushMiddle", "pushMiddle", "pushMiddle", "popMiddle"], values = [null, 1, 2, 3, null]

› Output: [null, null, null, null, 2]

💡 Note: pushMiddle(1): [1] → pushMiddle(2): [2,1] → pushMiddle(3): [2,3,1] → popMiddle() returns 3 (frontmost middle): [2,1]

Constraints

1 ≤ val ≤ 10⁹
At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of push/pop operations at front, middle, back positions

Process

Queue maintains elements with efficient access to all three positions

Output

Results of operations, with -1 for empty queue pops

Key Takeaway

🎯 Key Insight: Use two deques to balance the queue and enable O(1) operations at all three positions

Asked in

G Google 25 f Facebook 20 a Amazon 18 M Microsoft 15

The key insight is to split the queue into two deques (left and right) and maintain a size balance. This allows O(1) operations at both ends while making middle operations efficient by accessing the boundary between deques. Best approach uses Two Deques with rebalancing. Time: O(1) amortized, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Deques Approach	O(1)	O(n)	Use two deques to balance operations and achieve O(1) amortized time
Array with Shifting	O(n)	O(n)	Use a dynamic array and shift elements for middle operations

Two Deques Approach — Algorithm Steps

Split queue into left and right deques
Maintain size invariant: |left| <= |right| + 1 and |right| <= |left|
Rebalance after operations to maintain invariant
Middle operations work on the boundary between deques

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Empty left and right deques

After Operations

Elements distributed maintaining balance

Middle Access

Middle elements at deque boundaries

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    printf("[null,null,null,null,-1,3,1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

All operations are O(1) amortized due to deque properties and minimal rebalancing

✓ Linear Growth

Space Complexity

O(n)

Two deques store n elements total

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Deques Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler