Design Front Middle Back Queue - Problem

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

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

✓ Hash Map

⏱️ Time: N/A Space: N/A

Array with Shifting

⏱️ Time: O(n) Space: O(n)

Store elements in a dynamic array. For front/back operations, use standard array operations. For middle operations, calculate the middle index and insert/remove with element shifting.

Two Deques Approach

⏱️ Time: O(1) Space: O(n)

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

#define MAX_SIZE 100000

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
} Deque;

typedef struct {
    Deque left;
    Deque right;
} FrontMiddleBackQueue;

void initDeque(Deque* dq) {
    dq->front = MAX_SIZE / 2;
    dq->rear = MAX_SIZE / 2;
    dq->size = 0;
}

int dequeIsEmpty(Deque* dq) {
    return dq->size == 0;
}

void dequeAddFirst(Deque* dq, int val) {
    dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
    dq->data[dq->front] = val;
    dq->size++;
}

void dequeAddLast(Deque* dq, int val) {
    dq->data[dq->rear] = val;
    dq->rear = (dq->rear + 1) % MAX_SIZE;
    dq->size++;
}

int dequeRemoveFirst(Deque* dq) {
    if (dq->size == 0) return -1;
    int val = dq->data[dq->front];
    dq->front = (dq->front + 1) % MAX_SIZE;
    dq->size--;
    return val;
}

int dequeRemoveLast(Deque* dq) {
    if (dq->size == 0) return -1;
    dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
    int val = dq->data[dq->rear];
    dq->size--;
    return val;
}

void balance(FrontMiddleBackQueue* queue) {
    // Keep left.size() == right.size() or left.size() == right.size() + 1
    if (queue->left.size > queue->right.size + 1) {
        int val = dequeRemoveLast(&queue->left);
        dequeAddFirst(&queue->right, val);
    } else if (queue->right.size > queue->left.size) {
        int val = dequeRemoveFirst(&queue->right);
        dequeAddLast(&queue->left, val);
    }
}

FrontMiddleBackQueue* createFrontMiddleBackQueue() {
    FrontMiddleBackQueue* queue = malloc(sizeof(FrontMiddleBackQueue));
    initDeque(&queue->left);
    initDeque(&queue->right);
    return queue;
}

void pushFront(FrontMiddleBackQueue* queue, int val) {
    dequeAddFirst(&queue->left, val);
    balance(queue);
}

void pushMiddle(FrontMiddleBackQueue* queue, int val) {
    if (queue->left.size > queue->right.size) {
        int temp = dequeRemoveLast(&queue->left);
        dequeAddFirst(&queue->right, temp);
    }
    dequeAddLast(&queue->left, val);
    balance(queue);
}

void pushBack(FrontMiddleBackQueue* queue, int val) {
    dequeAddLast(&queue->right, val);
    balance(queue);
}

int popFront(FrontMiddleBackQueue* queue) {
    if (dequeIsEmpty(&queue->left) && dequeIsEmpty(&queue->right)) return -1;
    int val;
    if (!dequeIsEmpty(&queue->left)) {
        val = dequeRemoveFirst(&queue->left);
    } else {
        val = dequeRemoveFirst(&queue->right);
    }
    balance(queue);
    return val;
}

int popMiddle(FrontMiddleBackQueue* queue) {
    if (dequeIsEmpty(&queue->left) && dequeIsEmpty(&queue->right)) return -1;
    int val;
    if (!dequeIsEmpty(&queue->left)) {
        val = dequeRemoveLast(&queue->left);
    } else {
        // This should not happen given our balance invariant, but safety check
        val = dequeRemoveFirst(&queue->right);
    }
    balance(queue);
    return val;
}

int popBack(FrontMiddleBackQueue* queue) {
    if (dequeIsEmpty(&queue->left) && dequeIsEmpty(&queue->right)) return -1;
    int val;
    if (!dequeIsEmpty(&queue->right)) {
        val = dequeRemoveLast(&queue->right);
    } else {
        val = dequeRemoveLast(&queue->left);
    }
    balance(queue);
    return val;
}

void parseArray(const char* str, char results[][50], int* size) {
    *size = 0;
    if (strlen(str) < 2) return;
    
    const char* content = str + 1; // Skip '['
    int len = strlen(content) - 1; // Remove ']'
    
    if (len <= 0) return;
    
    char temp[2000];
    strncpy(temp, content, len);
    temp[len] = '\0';
    
    char* token = temp;
    char* end = temp + len;
    
    while (token < end) {
        while (token < end && (*token == ' ' || *token == ',')) token++;
        if (token >= end) break;
        
        char* start = token;
        if (*token == '"') {
            token++; // Skip opening quote
            start = token;
            while (token < end && *token != '"') token++;
            int itemLen = token - start;
            if (itemLen >= 50) itemLen = 49; // Safety check
            strncpy(results[*size], start, itemLen);
            results[*size][itemLen] = '\0';
            if (token < end) token++; // Skip closing quote
        } else {
            while (token < end && *token != ',' && *token != ' ') token++;
            int itemLen = token - start;
            if (itemLen >= 50) itemLen = 49; // Safety check
            strncpy(results[*size], start, itemLen);
            results[*size][itemLen] = '\0';
        }
        (*size)++;
        if (*size >= 100) break; // Safety check
    }
}

int main() {
    static char line1[2000], line2[2000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Remove newlines
    line1[strcspn(line1, "\n")] = '\0';
    line2[strcspn(line2, "\n")] = '\0';
    
    static char operations[100][50];
    static char values[100][50];
    int opCount, valCount;
    
    parseArray(line1, operations, &opCount);
    parseArray(line2, values, &valCount);
    
    static char results[100][50];
    int resultCount = 0;
    FrontMiddleBackQueue* queue = NULL;
    
    for (int i = 0; i < opCount; i++) {
        if (strcmp(operations[i], "FrontMiddleBackQueue") == 0) {
            queue = createFrontMiddleBackQueue();
            strcpy(results[resultCount++], "null");
        } else if (strcmp(operations[i], "pushFront") == 0) {
            pushFront(queue, atoi(values[i]));
            strcpy(results[resultCount++], "null");
        } else if (strcmp(operations[i], "pushMiddle") == 0) {
            pushMiddle(queue, atoi(values[i]));
            strcpy(results[resultCount++], "null");
        } else if (strcmp(operations[i], "pushBack") == 0) {
            pushBack(queue, atoi(values[i]));
            strcpy(results[resultCount++], "null");
        } else if (strcmp(operations[i], "popFront") == 0) {
            sprintf(results[resultCount++], "%d", popFront(queue));
        } else if (strcmp(operations[i], "popMiddle") == 0) {
            sprintf(results[resultCount++], "%d", popMiddle(queue));
        } else if (strcmp(operations[i], "popBack") == 0) {
            sprintf(results[resultCount++], "%d", popBack(queue));
        }
    }
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        if (i > 0) printf(",");
        printf("%s", results[i]);
    }
    printf("]\n");
    
    if (queue) free(queue);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

⚡ Linearithmic Space

28.1K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

💡 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