Design Front Middle Back Queue - Leetcode Solution

Problem Statement:

Design a queue that supports push, pop, peek, and getMiddle operations. The getMiddle operation returns the middle element of the queue.

If there are even elements in the queue, return the second middle element.

You are required to implement the following methods:

• void push(int value) - inserts value into queue
• int pop() - removes and returns the element at the front of the queue
• int peek() - returns the element at the front of the queue without removing it
• int getMiddle() - returns the middle element of the queue
• void addLast(int value) - inserts value at the end of the queue
• void removeLast() - removes the last element of the queue

Solution:

To solve this problem, we can use a double-linked list and maintain a pointer to the middle node. This approach allows us to get the middle element in constant time and push, pop, and peek elements in constant time as well.

The implementation details for each operation are as follows:

1. void push(int value) - inserts value into queue

This operation adds a new node with the given value to the front of the double-linked list. If the queue is empty, the new node becomes both the front and middle nodes. If the queue is not empty, we update the pointers of the new node, the previous front node, and the current middle node.

2. int pop() - removes and returns the element at the front of the queue

This operation removes the front node of the double-linked list and updates the pointers of the new front node and the current middle node.

3. int peek() - returns the element at the front of the queue without removing it

This operation returns the value of the front node of the double-linked list without removing it.

4. int getMiddle() - returns the middle element of the queue

This operation returns the value of the middle node of the double-linked list.

5. void addLast(int value) - inserts value at the end of the queue

This operation adds a new node with the given value to the end of the double-linked list. If the queue is empty, the new node becomes both the front and middle nodes. If the queue is not empty, we update the pointers of the new node, the previous back node, and the current middle node.

6. void removeLast() - removes the last element of the queue

This operation removes the back node of the double-linked list and updates the pointers of the new back node and the current middle node.

Code Implementation:

class Node { public: int val; Node* prev; Node* next;

Node(int v) {
    val = v;
    prev = NULL;
    next = NULL; 
}

};

class FrontMiddleBackQueue { public: Node* front; Node* middle; Node* back; int size;

FrontMiddleBackQueue() { front = NULL; middle = NULL; back = NULL; size = 0; }

void push(int value) { Node* new_node = new Node(value);

// If the queue is empty, the new node becomes both the front and middle nodes.
if (size == 0) {
    front = middle = back = new_node;
}

// If the queue has odd elements, the new node becomes the front node and the middle node is updated.
else if (size % 2 == 1) {
    new_node->next = front;
    front->prev = new_node;
    front = new_node;
    middle = middle->prev;
}

// If the queue has even elements, the new node becomes the front node, the middle node remains the same, and the back node is updated.
else {
    new_node->next = front;
    front->prev = new_node;
    front = new_node;
    back = back->prev;
}

size++;

}

int pop() { int value = front->val;

// If the queue has one element, remove it.
if (size == 1) {
    delete front;
    front = middle = back = NULL;
}

// If the queue has odd elements, remove the front node and update the pointers of the new front node and the current middle node.
else if (size % 2 == 1) {
    Node* new_front = front->next;
    delete front;
    front = new_front;
    front->prev = NULL;
    middle = middle->next;
}

// If the queue has even elements, remove the front node, update the pointers of the new front node and the current middle node, and update the back node.
else {
    Node* new_front = front->next;
    delete front;
    front = new_front;
    front->prev = NULL;
    back = back->next;
}

size--;
return value;

}

int peek() { return front->val; }

int getMiddle() { return middle->val; }

void addLast(int value) { Node* new_node = new Node(value);

// If the queue is empty, the new node becomes both the front and middle nodes.
if (size == 0) {
    front = middle = back = new_node;
}

// If the queue has odd elements, the new node becomes the back node, the middle node remains the same, and the front node is updated.
else if (size % 2 == 1) {
    back->next = new_node;
    new_node->prev = back;
    back = new_node;
    front = front->next;
    middle = middle->next;
}

// If the queue has even elements, the new node becomes the back node and the middle node is updated.
else {
    back->next = new_node;
    new_node->prev = back;
    back = new_node;
    middle = middle->next;
}

size++;

}

void removeLast() { // If the queue has one element, remove it. if (size == 1) { delete front; front = middle = back = NULL; }

// If the queue has odd elements, remove the back node, update the pointers of the new back node and the current middle node, and update the front node.
else if (size % 2 == 1) {
    Node* new_back = back->prev;
    delete back;
    back = new_back;
    back->next = NULL;
    front = front->prev;
    middle = middle->prev;
}

// If the queue has even elements, remove the back node and update the pointers of the new back node and the current middle node.
else {
    Node* new_back = back->prev;
    delete back;
    back = new_back;
    back->next = NULL;
    middle = middle->prev;
}

size--;

} };

1