1670. Design Front Middle Back Queue Solution

Q: Is Design Front Middle Back Queue easy or hard?

Design Front Middle Back Queue is classified as a Medium problem on LeetCode. The difficulty comes from maintaining the correct middle position while supporting constant-time operations. Once the idea of splitting the queue into two balanced halves is understood, the implementation becomes straightforward.

Q: Design Front Middle Back Queue Python/Java solution

Python solutions usually rely on collections.deque to maintain two balanced halves for constant-time operations. Java implementations often use a custom doubly linked list or two Deque objects such as ArrayDeque. Both approaches maintain O(1) time for push and pop operations at all three positions.

Q: How to solve Design Front Middle Back Queue in O(1)?

Split the queue into two deques representing the left and right halves. Maintain the invariant that the left deque size is either equal to the right deque size or exactly one larger. Perform operations on the appropriate deque and rebalance by moving a single element between them if needed, ensuring each operation stays O(1).

Q: What is the best approach for Design Front Middle Back Queue?

The most common solution uses two balanced deques. One deque stores the left half of the queue and the other stores the right half, while maintaining the invariant that the left side has either the same number of elements or one extra. This makes the middle position the boundary between the two structures, allowing all operations—push and pop at front, middle, and back—to run in O(1) time.

Q: Is Design Front Middle Back Queue asked at Google/Amazon/Meta?

Problems that require designing custom queues with additional operations frequently appear in interviews at large tech companies. Variants of queue design and double-ended data structures have been reported in interviews at companies like Amazon and Google because they test both data structure intuition and implementation skills.

Q: What data structure is used in Design Front Middle Back Queue?

Two primary structures work well: double-ended queues (deques) or a doubly linked list with a tracked middle pointer. The deque solution relies on maintaining two balanced halves, while the linked list version updates head, tail, and middle pointers after each operation.

Q: What is the time complexity of Design Front Middle Back Queue?

With the optimal design, every operation runs in O(1) time. The deque-based approach performs constant-time insertions and removals at both ends, and rebalancing moves at most one element between the two halves. Space complexity is O(n) because all elements must be stored.

The problem

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 <= 10⁹
At most 1000 calls will be made to pushFront, pushMiddle, pushBack, popFront, popMiddle, and popBack.

Approach overview

Problem Overview: Design a queue that supports insertion and deletion from three positions: the front, the middle, and the back. The data structure must expose operations like pushFront, pushMiddle, pushBack, and their corresponding pop operations while keeping the middle definition consistent as elements change.

Approach 1: Deque Based Approach (O(1) time, O(n) space)

The cleanest solution splits the queue into two balanced halves using two deque structures: left and right. The invariant is that left.size() is either equal to right.size() or exactly one larger. Front operations interact with the front of left, back operations interact with the end of right, and middle operations insert or remove from the boundary between them. After every operation, you rebalance by moving one element between the deques if the size difference breaks the invariant. Because deque operations like append, appendleft, pop, and popleft run in constant time, every queue operation also runs in O(1) time with O(n) space for stored elements.

This approach is practical in languages with efficient deque implementations such as Python and JavaScript. Conceptually it behaves like maintaining the left half and right half of the queue separately, which makes the "middle" position simply the boundary between them. It relies heavily on properties of a queue and efficient double-ended operations.

Approach 2: Linked List Based Approach (O(1) time, O(n) space)

A lower-level implementation uses a doubly linked list with explicit pointers to the head, tail, and middle node. Each insertion or deletion updates the relevant pointer and then adjusts the middle pointer depending on whether the size of the list becomes even or odd. For example, when inserting near the front while the size becomes odd, the middle pointer may move one step backward. When removing elements, similar pointer adjustments maintain the correct middle node.

This design mirrors how queues can be implemented from scratch without relying on built‑in containers. Every operation touches only a constant number of nodes and pointer updates, so the runtime remains O(1). Space usage is O(n) for the nodes themselves. It is a good exercise in pointer manipulation and fits naturally with classic design and data stream style problems.

Recommended for interviews: The two-deque solution is typically the expected answer. It demonstrates the key insight: keep the queue split into balanced halves so the middle element is always easy to access. A linked list version shows strong understanding of pointer-based data structures, but the deque approach communicates the idea faster and is easier to implement correctly under interview pressure.

Approach 1: Deque Based Approach

This approach utilizes two separate deques (or double-ended queues) to manage the elements efficiently. One deque manages the left half of the queue and the other manages the right half.

For operations concerning the front, we utilize the front of the left deque. For back operations, we utilize the back of the right deque.

For middle operations, we ensure that the deques remain balanced or have at most a one-element difference. The 'middle' element is the last element of the left deque when both deques have equal size, or the first element of the right deque otherwise.

Balancing the two deques efficiently allows you to perform middle operations in constant amortized time.

Python

from collections import deque

class FrontMiddleBackQueue:
    def __init__(self):
        self.left = deque()
        self.right = deque()

    def pushFront(self, val: int) -> None:
        self.left.appendleft(val)
        self.balance()

    def pushMiddle(self, val: int) -> None:
        if len(self.left) > len(self.right):
            self.right.appendleft(self.left.pop())
        self.left.append(val)

    def pushBack(self, val: int) -> None:
        self.right.append(val)
        self.balance()

    def popFront(self) -> int:
        if self.left:
            val = self.left.popleft()
            self.balance()
            return val
        if self.right:
            return self.right.popleft()
        return -1

    def popMiddle(self) -> int:
        if not self.left and not self.right:
            return -1
        if len(self.left) == len(self.right):
            return self.left.pop()
        return self.right.popleft()

    def popBack(self) -> int:
        if self.right:
            val = self.right.pop()
            self.balance()
            return val
        if self.left:
            return self.left.pop()
        return -1

    def balance(self):
        if len(self.left) > len(self.right) + 1:
            self.right.appendleft(self.left.pop())
        elif len(self.right) > len(self.left):
            self.left.append(self.right.popleft())

JavaScript

class FrontMiddleBackQueue {
    constructor() {
        this.left = [];
        this.right = [];
    }

    pushFront(val) {
        this.left.unshift(val);
        this.balance();
    }

    pushMiddle(val) {
        if (this.left.length > this.right.length) {
            this.right.unshift(this.left.pop());
        }
        this.left.push(val);
    }

    pushBack(val) {
        this.right.push(val);
        this.balance();
    }

    popFront() {
        if (this.left.length) return this.left.shift(), this.balance(), this.left[0] || -1;
        if (this.right.length) return this.right.shift();
        return -1;
    }

    popMiddle() {
        if (this.left.length + this.right.length === 0) return -1;
        if (this.left.length === this.right.length) return this.left.pop();
        return this.right.shift();
    }

    popBack() {
        if (this.right.length) return this.right.pop(), this.balance(), this.right[this.right.length - 1] || -1;
        if (this.left.length) return this.left.pop();
        return -1;
    }

    balance() {
        if (this.left.length > this.right.length + 1) {
            this.right.unshift(this.left.pop());
        } else if (this.right.length > this.left.length) {
            this.left.push(this.right.shift());
        }
    }
}

The implementation utilizes two deques from the Python standard library to efficiently manage operations at the front, middle, and back. By maintaining two separate deques for the left and right segments of the queue, the solution is able to balance the elements by moving elements between the deques when necessary.

The balance method ensures that the sizes of the deques differ by at most one, which is crucial for correct middle element operations.

Complexity

Time Complexity: The time complexity for each operation is O(1) due to the efficient re-balancing of the deques.
Space Complexity: O(N), where N is the number of elements in the queue.

Try this approach in the editor

Approach 2: Linked List Based Approach

This approach uses a doubly linked list to implement the queue, which allows efficient insertion and deletion from both ends and from the middle.

By keeping a pointer/reference to the middle node, operations that involve the middle element can be performed in constant time. The challenge is to keep the middle pointer updated correctly as elements are added or removed.

This design achieves a consistent constant time complexity for all operations, though it requires careful handling of pointers due to frequent updates, especially in middle operations.

Java

class FrontMiddleBackQueue {
    class Node {
        int val;
        Node prev, next;
        Node(int val) { this.val = val; }
    }

    private Node head, tail, middle;
    private int size;

    public FrontMiddleBackQueue() {
        head = tail = middle = null;
        size = 0;
    }

    public void pushFront(int val) {
        Node node = new Node(val);
        if (size == 0) {
            head = tail = middle = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
            if (size % 2 == 0) middle = middle.prev;
        }
        size++;
    }

    public void pushMiddle(int val) {
        Node node = new Node(val);
        if (size == 0) {
            head = tail = middle = node;
        } else if (size % 2 == 0) {
            node.prev = middle;
            node.next = middle.next;
            if (middle.next != null) middle.next.prev = node;
            middle.next = node;
            if (tail == middle) tail = node;
            middle = node;
        } else {
            node.next = middle;
            node.prev = middle.prev;
            if (middle.prev != null) middle.prev.next = node;
            middle.prev = node;
            if (head == middle) head = node;
        }
        size++;
    }

    public void pushBack(int val) {
        Node node = new Node(val);
        if (size == 0) {
            head = tail = middle = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
            if (size % 2 != 0) middle = middle.next;
        }
        size++;
    }

    public int popFront() {
        if (size == 0) return -1;
        int val = head.val;
        head = head.next;
        if (head != null) head.prev = null;
        if (size % 2 != 0) middle = middle.next;
        if (--size == 0) tail = middle = null;
        return val;
    }

    public int popMiddle() {
        if (size == 0) return -1;
        int val = middle.val;
        if (middle.prev != null) middle.prev.next = middle.next;
        if (middle.next != null) middle.next.prev = middle.prev;
        Node oldMiddle = middle;
        if (--size % 2 == 0) middle = middle.prev;
        else middle = middle.next;
        if (size == 0) head = tail = middle = null;
        return val;
    }

    public int popBack() {
        if (size == 0) return -1;
        int val = tail.val;
        tail = tail.prev;
        if (tail != null) tail.next = null;
        if (size % 2 == 0) middle = middle.prev;
        if (--size == 0) head = middle = null;
        return val;
    }
}

C++

#include <iostream>

class FrontMiddleBackQueue {
private:
    struct Node {
        int val;
        Node* prev;
        Node* next;
        Node(int v) : val(v), prev(nullptr), next(nullptr) {}
    };
    Node* head;
    Node* tail;
    Node* middle;
    int size;

public:
    FrontMiddleBackQueue() : head(nullptr), tail(nullptr), middle(nullptr), size(0) {}

    void pushFront(int val) {
        Node* node = new Node(val);
        if (size == 0) {
            head = tail = middle = node;
        } else {
            node->next = head;
            head->prev = node;
            head = node;
            if (size % 2 == 0) middle = middle->prev; // decrease, if size even before
        }
        ++size;
    }

    void pushMiddle(int val) {
        Node* node = new Node(val);
        if (size == 0) {
            head = tail = middle = node;
        } else if (size % 2 == 0) { // even size, middle shifts left
            node->prev = middle;
            node->next = middle->next;
            if (middle->next) middle->next->prev = node;
            middle->next = node;
            if (tail == middle) tail = node;
            middle = node;
        } else { // odd size, middle shifts right
            node->next = middle;
            node->prev = middle->prev;
            if (middle->prev) middle->prev->next = node;
            middle->prev = node;
            if (head == middle) head = node;
        }
        ++size;
    }

    void pushBack(int val) {
        Node* node = new Node(val);
        if (size == 0) {
            head = tail = middle = node;
        } else {
            tail->next = node;
            node->prev = tail;
            tail = node;
            if (size % 2 != 0) middle = middle->next; // increase, if size odd before
        }
        ++size;
    }

    int popFront() {
        if (size == 0) return -1;
        int val = head->val;
        Node* temp = head;
        head = head->next;
        if (head) head->prev = nullptr;
        delete temp;
        if (size % 2 != 0) middle = middle->next; // increase, if size odd before
        if (--size == 0) tail = middle = nullptr;
        return val;
    }

    int popMiddle() {
        if (size == 0) return -1;
        int val = middle->val;
        if (middle->prev) middle->prev->next = middle->next;
        if (middle->next) middle->next->prev = middle->prev;
        Node* temp = middle;
        if (--size % 2 == 0) middle = middle->prev; // decrease, size becomes one less after pop
        else middle = middle->next; // increase 
        if (size == 0) head = tail = middle = nullptr;
        delete temp;
        return val;
    }

    int popBack() {
        if (size == 0) return -1;
        int val = tail->val;
        Node* temp = tail;
        tail = tail->prev;
        if (tail) tail->next = nullptr;
        delete temp;
        if (size % 2 == 0) middle = middle->prev; // decrease, if size even after
        if (--size == 0) head = middle = nullptr;
        return val;
    }
};

The Java implementation uses a custom doubly linked list structure to manage the queue. This allows for efficient insertion and removal from the front, middle, or back of the queue. Each node has references to its previous and next nodes, enabling O(1) operation times.

Similar to the C++ implementation, a middle node is used to track the middle of the list, which is updated after each modification to the list.

Complexity

Time Complexity: O(1) per operation, as linked list pointers allow direct access and modification.
Space Complexity: O(N), where N is the number of elements held in the queue.

Try this approach in the editor

Approach 3: 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.

In the pushFront, pushMiddle, and pushBack functions, we only need to add elements to q_1 or q_2, and call the rebalance function.

For the popFront function, we need to check whether q_1 and q_2 are empty. If both are empty, return -1. Otherwise, we need to check whether q_1 is empty. If not, pop the front element of q_1, otherwise pop the front element of q_2, and call the rebalance function.

For the popMiddle function, we need to check whether q_1 and q_2 are empty. If both are empty, return -1. Otherwise, we need to check whether the lengths of q_1 and q_2 are equal. If they are equal, pop the last element of q_1, otherwise pop the front element of q_2, and call the rebalance function.

For the popBack function, we only need to check whether q_2 is empty. If it is empty, return -1. Otherwise, pop the last element of q_2, and call the rebalance function.

The time complexity of the above operations is O(1), and the space complexity is O(n), where n is the number of elements in the queue.

TypeScript

class FrontMiddleBackQueue {
    private q1: Deque<number>;
    private q2: Deque<number>;

    constructor() {
        this.q1 = new Deque<number>();
        this.q2 = new Deque<number>();
    }

    pushFront(val: number): void {
        this.q1.pushFront(val);
        this.rebalance();
    }

    pushMiddle(val: number): void {
        this.q1.pushBack(val);
        this.rebalance();
    }

    pushBack(val: number): void {
        this.q2.pushBack(val);
        this.rebalance();
    }

    popFront(): number {
        if (this.q1.isEmpty() && this.q2.isEmpty()) {
            return -1;
        }
        const val = this.q1.isEmpty() ? this.q2.popFront() : this.q1.popFront();
        this.rebalance();
        return val!;
    }

    popMiddle(): number {
        if (this.q1.isEmpty() && this.q2.isEmpty()) {
            return -1;
        }
        const val =
            this.q1.getSize() === this.q2.getSize() ? this.q1.popBack() : this.q2.popFront();
        this.rebalance();
        return val!;
    }

    popBack(): number {
        if (this.q2.isEmpty()) {
            return -1;
        }
        const val = this.q2.popBack();
        this.rebalance();
        return val!;
    }

    private rebalance(): void {
        if (this.q1.getSize() > this.q2.getSize()) {
            this.q2.pushFront(this.q1.popBack()!);
        }
        if (this.q2.getSize() > this.q1.getSize() + 1) {
            this.q1.pushBack(this.q2.popFront()!);
        }
    }
}

class Node<T> {
    value: T;
    next: Node<T> | null;
    prev: Node<T> | null;

    constructor(value: T) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class Deque<T> {
    private front: Node<T> | null;
    private back: Node<T> | null;
    private size: number;

    constructor() {
        this.front = null;
        this.back = null;
        this.size = 0;
    }

    pushFront(val: T): void {
        const newNode = new Node(val);
        if (this.isEmpty()) {
            this.front = newNode;
            this.back = newNode;
        } else {
            newNode.next = this.front;
            this.front!.prev = newNode;
            this.front = newNode;
        }
        this.size++;
    }

    pushBack(val: T): void {
        const newNode = new Node(val);
        if (this.isEmpty()) {
            this.front = newNode;
            this.back = newNode;
        } else {
            newNode.prev = this.back;
            this.back!.next = newNode;
            this.back = newNode;
        }
        this.size++;
    }

    popFront(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }
        const value = this.front!.value;
        this.front = this.front!.next;
        if (this.front !== null) {
            this.front.prev = null;
        } else {
            this.back = null;
        }
        this.size--;
        return value;
    }

    popBack(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }
        const value = this.back!.value;
        this.back = this.back!.prev;
        if (this.back !== null) {
            this.back.next = null;
        } else {
            this.front = null;
        }
        this.size--;
        return value;
    }

    frontValue(): T | undefined {
        return this.front?.value;
    }

    backValue(): T | undefined {
        return this.back?.value;
    }

    getSize(): number {
        return this.size;
    }

    isEmpty(): boolean {
        return this.size === 0;
    }
}

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

type FrontMiddleBackQueue struct {
	q1, q2 Deque
}

func Constructor() FrontMiddleBackQueue {
	return FrontMiddleBackQueue{}
}

func (this *FrontMiddleBackQueue) PushFront(val int) {
	this.q1.PushFront(val)
	this.rebalance()
}

func (this *FrontMiddleBackQueue) PushMiddle(val int) {
	this.q1.PushBack(val)
	this.rebalance()
}

func (this *FrontMiddleBackQueue) PushBack(val int) {
	this.q2.PushBack(val)
	this.rebalance()
}

func (this *FrontMiddleBackQueue) PopFront() int {
	if this.q1.Empty() && this.q2.Empty() {
		return -1
	}
	var val int
	if !this.q1.Empty() {
		val = this.q1.PopFront()
	} else {
		val = this.q2.PopFront()
	}
	this.rebalance()
	return val
}

func (this *FrontMiddleBackQueue) PopMiddle() int {
	if this.q1.Empty() && this.q2.Empty() {
		return -1
	}
	var val int
	if this.q1.Size() == this.q2.Size() {
		val = this.q1.PopBack()
	} else {
		val = this.q2.PopFront()
	}
	this.rebalance()
	return val
}

func (this *FrontMiddleBackQueue) PopBack() int {
	if this.q2.Empty() {
		return -1
	}
	val := this.q2.PopBack()
	this.rebalance()
	return val
}

func (this *FrontMiddleBackQueue) rebalance() {
	if this.q1.Size() > this.q2.Size() {
		this.q2.PushFront(this.q1.PopBack())
	}
	if this.q2.Size() > this.q1.Size()+1 {
		this.q1.PushBack(this.q2.PopFront())
	}
}

// template
type Deque struct{ l, r []int }

func (q Deque) Empty() bool {
	return len(q.l) == 0 && len(q.r) == 0
}

func (q Deque) Size() int {
	return len(q.l) + len(q.r)
}

func (q *Deque) PushFront(v int) {
	q.l = append(q.l, v)
}

func (q *Deque) PushBack(v int) {
	q.r = append(q.r, v)
}

func (q *Deque) PopFront() (v int) {
	if len(q.l) > 0 {
		q.l, v = q.l[:len(q.l)-1], q.l[len(q.l)-1]
	} else {
		v, q.r = q.r[0], q.r[1:]
	}
	return
}

func (q *Deque) PopBack() (v int) {
	if len(q.r) > 0 {
		q.r, v = q.r[:len(q.r)-1], q.r[len(q.r)-1]
	} else {
		v, q.l = q.l[0], q.l[1:]
	}
	return
}

func (q Deque) Front() int {
	if len(q.l) > 0 {
		return q.l[len(q.l)-1]
	}
	return q.r[0]
}

func (q Deque) Back() int {
	if len(q.r) > 0 {
		return q.r[len(q.r)-1]
	}
	return q.l[0]
}

func (q Deque) Get(i int) int {
	if i < len(q.l) {
		return q.l[len(q.l)-1-i]
	}
	return q.r[i-len(q.l)]
}

/**
 * Your FrontMiddleBackQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.PushFront(val);
 * obj.PushMiddle(val);
 * obj.PushBack(val);
 * param_4 := obj.PopFront();
 * param_5 := obj.PopMiddle();
 * param_6 := obj.PopBack();
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Deque Based Approach	Time Complexity: The time complexity for each operation is O(1) due to the efficient re-balancing of the deques. Space Complexity: O(N), where N is the number of elements in the queue.
Linked List Based Approach	Time Complexity: O(1) per operation, as linked list pointers allow direct access and modification. Space Complexity: O(N), where N is the number of elements held in the queue.
Two Deques	–

Complexity analysis

Approach	Time	Space	When to Use
Two Deques (Balanced Halves)	O(1) per operation	O(n)	Best practical solution when a language provides efficient deque operations
Doubly Linked List with Middle Pointer	O(1) per operation	O(n)	Useful when implementing custom data structures or practicing pointer manipulation

Frequently asked questions

Is Design Front Middle Back Queue easy or hard?

Design Front Middle Back Queue is classified as a Medium problem on LeetCode. The difficulty comes from maintaining the correct middle position while supporting constant-time operations. Once the idea of splitting the queue into two balanced halves is understood, the implementation becomes straightforward.

Design Front Middle Back Queue Python/Java solution

Python solutions usually rely on collections.deque to maintain two balanced halves for constant-time operations. Java implementations often use a custom doubly linked list or two Deque objects such as ArrayDeque. Both approaches maintain O(1) time for push and pop operations at all three positions.

How to solve Design Front Middle Back Queue in O(1)?

Split the queue into two deques representing the left and right halves. Maintain the invariant that the left deque size is either equal to the right deque size or exactly one larger. Perform operations on the appropriate deque and rebalance by moving a single element between them if needed, ensuring each operation stays O(1).

What is the best approach for Design Front Middle Back Queue?

The most common solution uses two balanced deques. One deque stores the left half of the queue and the other stores the right half, while maintaining the invariant that the left side has either the same number of elements or one extra. This makes the middle position the boundary between the two structures, allowing all operations—push and pop at front, middle, and back—to run in O(1) time.

Is Design Front Middle Back Queue asked at Google/Amazon/Meta?

Problems that require designing custom queues with additional operations frequently appear in interviews at large tech companies. Variants of queue design and double-ended data structures have been reported in interviews at companies like Amazon and Google because they test both data structure intuition and implementation skills.

What data structure is used in Design Front Middle Back Queue?

Two primary structures work well: double-ended queues (deques) or a doubly linked list with a tracked middle pointer. The deque solution relies on maintaining two balanced halves, while the linked list version updates head, tail, and middle pointers after each operation.

What is the time complexity of Design Front Middle Back Queue?

With the optimal design, every operation runs in O(1) time. The deque-based approach performs constant-time insertions and removals at both ends, and rebalancing moves at most one element between the two halves. Space complexity is O(n) because all elements must be stored.

Design Front Middle Back Queue solution and explanation

The problem

Approach overview

Approach 1: Deque Based Approach

Approach 2: Linked List Based Approach

Approach 3: Two Deques

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design Front Middle Back Queue solution and explanation

The problem

Approach overview

Approach 1: Deque Based Approach

Approach 2: Linked List Based Approach

Approach 3: Two Deques

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems