Beats 100% | Beginner-Friendly Front Middle Back Queue Implementation Using Singly Linked List
IntuitionThe problem requires implementing a queue that supports operations to push and pop elements from the front, middle, and back. A singly linked list is a
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires implementing a queue that supports operations to push and pop elements from the front, middle, and back. A **singly linked list** is a suitable data structure for this because it allows efficient insertion and deletion at the front and back. However, inserting or deleting from the middle requires traversing the list to find the middle node.

# Approach
<!-- Describe your approach to solving the problem. -->
1. **Data Structure:**

- Use a singly linked list with ```head``` and ```tail``` pointers to keep track of the front and back of the queue.

- Maintain a ```size``` variable to efficiently determine the middle position.

2. **Operations:**

- **Push Front**: Insert a new node at the beginning of the list.

- **Push Middle**: Insert a new node at the middle of the list.

- **Push Back**: Insert a new node at the end of the list.

- **Pop Front**: Remove and return the node at the beginning of the list.

- **Pop Middle**: Remove and return the node at the middle of the list.

- **Pop Back**: Remove and return the node at the end of the list.

3. **Middle Calculation:**

- For ```pushMiddle``` and ```popMiddle```, calculate the middle position using the formula ```size / 2``` or `(size - 1) / 2`, respectively.

4. **Edge Cases:**

- Handle cases where the list is empty or has only one node.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
`pushFront, popFront`: O(1)

`pushMiddle, popMiddle`: O(n) (due to traversing to the middle)

`pushBack, popBack`: O(1) (with `tail` pointer)

Space complexity:
<!--Add your space complexity here, e.g. $$O(n)$$ -->
`O(n)` (space used by the linked list)

# Code
```java []
class FrontMiddleBackQueue {
    // Node class for the linked list
    class Node {
        int val;
        Node next;
        
        public Node(int val) {
            this.val = val;
            this.next = null;
        }
        
        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    private Node head; // Points to the front of the queue
    private Node tail; // Points to the back of the queue
    private int size;  // Tracks the number of elements in the queue

    // Constructor initializes an empty queue
    public FrontMiddleBackQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    // Push a value to the front of the queue
    public void pushFront(int val) {
        Node newNode = new Node(val, head); // Create a new node pointing to the current head
        head = newNode; // Update head to the new node
        if (tail == null) { // If the queue was empty, update tail as well
            tail = head;
        }
        size++; // Increment size
    }

    // Push a value to the middle of the queue
    public void pushMiddle(int val) {
        if (size == 0) { // If the queue is empty, push to the front
            pushFront(val);
            return;
        }

        int mid = size / 2; // Calculate the middle position
        Node prev = null;
        Node curr = head;

        // Traverse to the middle node
        for (int i = 0; i < mid; i++) {
            prev = curr;
            curr = curr.next;
        }

        // Insert the new node in the middle
        Node newNode = new Node(val, curr);
        if (prev != null) {
            prev.next = newNode;
        } else {
            head = newNode; // If prev is null, update head
        }
        size++; // Increment size
    }

    // Push a value to the back of the queue
    public void pushBack(int val) {
        Node newNode = new Node(val); // Create a new node
        if (tail == null) { // If the queue is empty, update both head and tail
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode; // Append to the end
            tail = newNode; // Update tail
        }
        size++; // Increment size
    }

    // Pop a value from the front of the queue
    public int popFront() {
        if (head == null) { // If the queue is empty, return -1
            return -1;
        }
        int val = head.val; // Get the value at the front
        head = head.next; // Move head to the next node
        if (head == null) { // If the queue becomes empty, update tail
            tail = null;
        }
        size--; // Decrement size
        return val;
    }

    // Pop a value from the middle of the queue
    public int popMiddle() {
        if (head == null) { // If the queue is empty, return -1
            return -1;
        }

        int mid = (size - 1) / 2; // Calculate the middle position
        Node prev = null;
        Node curr = head;

        // Traverse to the middle node
        for (int i = 0; i < mid; i++) {
            prev = curr;
            curr = curr.next;
        }

        int val = curr.val; // Get the value at the middle
        if (prev != null) {
            prev.next = curr.next; // Remove the middle node
        } else {
            head = curr.next; // If prev is null, update head
        }

        if (curr == tail) { // If the middle node was the tail, update tail
            tail = prev;
        }

        size--; // Decrement size
        return val;
    }

    // Pop a value from the back of the queue
    public int popBack() {
        if (head == null) { // If the queue is empty, return -1
            return -1;
        }

        int val;
        if (head == tail) { // If there's only one node, remove it
            val = head.val;
            head = null;
            tail = null;
        } else {
            Node curr = head;
            // Traverse to the second last node
            while (curr.next != tail) {
                curr = curr.next;
            }
            val = tail.val; // Get the value at the tail
            curr.next = null; // Remove the tail
            tail = curr; // Update tail
        }

        size--; // Decrement size
        return val;
    }
}
```
# Visualisation of Operations
**Initial State:**
```
head -> null
tail -> null
size = 0
 ```

**After `pushFront(1)`:**

```
head -> [1] -> null
tail -> [1]
size = 1
```

**After `pushMiddle(2)`:**
```
head -> [2] -> [1] -> null
tail -> [1]
size = 2
 ```

**After `pushBack(3)`:**
```
head -> [2] -> [1] -> [3] -> null
tail -> [3]
size = 3
 ```

**After `popFront()`:**
```
head -> [1] -> [3] -> null
tail -> [3]
size = 2
 ```

**After `popMiddle()`:**
```
head -> [1] -> null
tail -> [1]
size = 1
 ```

**After ```popBack()```:**

```
head -> null
tail -> null
size = 0
 ```

## Please Upvote if Helpful
































































































































































































['Linked List', 'Queue', 'Java']