Design Front Middle Back Queue — Editorial

Opening the reading…

Intuitionturning one difficult middle into two easy ends

A middle operation is awkward only when the queue is stored as one sequence: inserting or removing near the center shifts everything after it. Split the sequence into a left half and a right half instead. The boundary between the halves is the middle, so every required operation can touch an endpoint of one deque.

Keep the left deque with either the same number of elements as the right deque or exactly one more. The full queue is left followed by right. When the total size is odd, the extra element belongs at the back of left, so that element is the frontmost middle. When the total size is even, the two middle positions are left.back() and right.front(), and the frontmost one is left.back().

The split makes the middle an endpoint.

Approachone invariant controls every operation

Create left and right deques, interpreting the full queue as left followed by right, because this makes the front, middle, and back reachable at deque endpoints.

Define rebalance so it moves left.back() to right.front() when left has more than one extra element, or right.front() to left.back() when right is larger; without this repair, later middle decisions would refer to the wrong positions.

For pushFront, insert into left.front(), then rebalance, because the new front belongs in the left half even when it temporarily makes that half too large.

For pushBack, insert into right.back(), then rebalance, because the new back belongs in the right half and the invariant determines whether one boundary element must move.

For pushMiddle, if left is larger, move left.back() to right.front() first, then append the new value to left; this places the value before the old middle when two middle positions existed, while equal-sized halves already allow direct insertion at left.back().

For popFront, remove left.front() when it exists and otherwise right.front(), because left contains the front of the full queue; rebalance afterward so the next operation sees a valid split.

For popMiddle, remove left.back() when left has at least as many elements as right, otherwise remove right.front(); this selects the frontmost middle in both parity cases, and rebalance restores the invariant after removal.

For popBack, remove right.back() when right is nonempty and otherwise left.back(), then rebalance, because right normally contains the back but an odd one-element queue has no right half. Return -1 before any removal when both deques are empty.

Complexityconstant work per operation

MEASURE	BOUND	WHY
Time	O(n) total, O(1) amortized per operation	Each operation performs a constant number of deque endpoint insertions, removals, and size checks. Rebalancing moves at most one boundary element because each update changes the size difference by at most one, so no element is repeatedly scanned or shifted.
Space	O(n) extra space	The two deques hold the live queue state, which can contain O(n) values in the worst case when pushes dominate. The returned vector of strings is required output and is excluded from the extra-space bound.

Here n is the number of operations in execute. The queue can contain at most n inserted values.

Annotated solutionC++ · two deques · the invariant lives in one helper

CPPThe complete implementation stores the queue as left followed by right and repairs the split after each update.

#include <deque>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> execute(vector<string>& operations, vector<vector<int>>& args) {
        deque<int> left;
        deque<int> right;

        auto rebalance = [&]() {
            if (left.size() > right.size() + 1) {
                right.push_front(left.back());
                left.pop_back();
            } else if (left.size() < right.size()) {
                left.push_back(right.front());
                right.pop_front();
            }
        };

        vector<string> result;

        for (int i = 0; i < static_cast<int>(operations.size()); ++i) {
            const string& operation = operations[i];

            if (operation == "FrontMiddleBackQueue") {
                result.push_back("null");
            } else if (operation == "pushFront") {
                left.push_front(args[i][0]);
                rebalance();
                result.push_back("null");
            } else if (operation == "pushMiddle") {
                if (left.size() > right.size()) {
                    right.push_front(left.back());
                    left.pop_back();
                }
                left.push_back(args[i][0]);
                rebalance();
                result.push_back("null");
            } else if (operation == "pushBack") {
                right.push_back(args[i][0]);
                rebalance();
                result.push_back("null");
            } else if (operation == "popFront") {
                if (left.empty() && right.empty()) {
                    result.push_back("-1");
                } else {
                    int value;
                    if (!left.empty()) {
                        value = left.front();
                        left.pop_front();
                    } else {
                        value = right.front();
                        right.pop_front();
                    }
                    rebalance();
                    result.push_back(to_string(value));
                }
            } else if (operation == "popMiddle") {
                if (left.empty() && right.empty()) {
                    result.push_back("-1");
                } else {
                    int value;
                    if (left.size() >= right.size()) {
                        value = left.back();
                        left.pop_back();
                    } else {
                        value = right.front();
                        right.pop_front();
                    }
                    rebalance();
                    result.push_back(to_string(value));
                }
            } else if (operation == "popBack") {
                if (left.empty() && right.empty()) {
                    result.push_back("-1");
                } else {
                    int value;
                    if (!right.empty()) {
                        value = right.back();
                        right.pop_back();
                    } else {
                        value = left.back();
                        left.pop_back();
                    }
                    rebalance();
                    result.push_back(to_string(value));
                }
            }
        }

        return result;
    }
};

The special handling in pushMiddle is the key placement detail. If left is already larger, its last element is the old frontmost middle; moving that element to the front of right creates equal halves, so appending the new value to left puts it before the old middle. If the halves are equal, appending directly to left makes the new value the sole middle or the frontmost of two.