Formatted question description: https://leetcode.ca/all/1670.html

1670. Design Front Middle Back Queue

Level

Medium

Description

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

Solution

Easy way, to use 2 queues.

class FrontMiddleBackQueue {
    Deque<Integer> left;
    Deque<Integer> right;

    public FrontMiddleBackQueue() {
        left = new LinkedList<>();
        right = new LinkedList<>();
    }

    public void pushFront(int val) {
        left.offerFirst(val);

        // right is 1-more than left, or equal
        if (left.size() > right.size()) right.offerFirst(left.pollLast());
    }

    public void pushMiddle(int val) {
        if (left.size() == right.size()) right.offerFirst(val);
        else left.offerLast(val);
    }

    public void pushBack(int val) {
        if (left.size() < right.size()) left.offerLast(right.pollFirst());
        right.offerLast(val);
    }

    public int popFront() {
        if (left.size() < right.size()) left.offerLast(right.pollFirst());
        return left.isEmpty() ? -1 : left.pollFirst();
    }

    public int popMiddle() {
        if (left.size() == right.size()) return left.isEmpty() ? -1 : left.pollLast();
        else return right.isEmpty() ? -1 : right.pollFirst();
    }

    public int popBack() {
        if (left.size() == right.size() && !left.isEmpty()) right.offerFirst(left.pollLast());
        return right.isEmpty() ? -1 : right.pollLast();
    }
}

Define a class Node that links to both its previous node and its next node.

In FrontMiddleBackQueue class, maintain the size, the start node, the end node and the middle node. Initially, the size is 0, and the start node, the end node and the middle node are all null.

When pushing a value, update the nodes accordingly and increase the size by 1.

When popping a value, update the nodes accordingly and decrease the size by 1.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class FrontMiddleBackQueue {

    private Deque<Integer> fDeq, rDeq;
    private int size;

    public FrontMiddleBackQueue() {
        fDeq = new ArrayDeque<>();
        rDeq = new ArrayDeque<>();
    }

    public void pushFront(int val) {
        fDeq.offerFirst(val);
        adjust();
        size++;
    }

    public void pushMiddle(int val) {
        fDeq.offerLast(val);
        adjust();
        size++;
    }

    public void pushBack(int val) {
        rDeq.offerLast(val);
        adjust();
        size++;
    }

    public int popFront() {
        if (size == 0) {
            return -1;
        }

        // 注意要判断一下前队列是否空
        int res = !fDeq.isEmpty() ? fDeq.pollFirst() : rDeq.pollFirst();
        adjust();
        size--;
        return res;
    }

    public int popMiddle() {
        if (size == 0) {
            return -1;
        }

        // 如果两个队列size一样，则pop前队列队尾，否则pop后队列队头
        int res = fDeq.size() == rDeq.size() ? fDeq.pollLast() : rDeq.pollFirst();
        adjust();
        size--;
        return res;
    }

    public int popBack() {
        if (size == 0) {
            return -1;
        }

        int res = rDeq.pollLast();
        adjust();
        size--;
        return res;
    }

    // 用于调整两个队列的size，保持后半始终不少于前半，并且多不超过1个
    private void adjust() {
        if (rDeq.size() - fDeq.size() >= 2) {
            fDeq.offerLast(rDeq.pollFirst());
        }
        if (rDeq.size() < fDeq.size()) {
            rDeq.offerFirst(fDeq.pollLast());
        }
    }
}

class FrontMiddleBackQueue {
    int size;
    Node start;
    Node end;
    Node middle;

    public FrontMiddleBackQueue() {
        size = 0;
        start = null;
        end = null;
        middle = null;
    }
    
    public void pushFront(int val) {
        Node node = new Node(val);
        if (size == 0) {
            start = node;
            end = node;
            middle = node;
        } else {
            node.next = start;
            start.prev = node;
            start = node;
            if (size % 2 == 1)
                middle = middle.prev;
        }
        size++;
    }
    
    public void pushMiddle(int val) {
        Node node = new Node(val);
        if (size == 0) {
            start = node;
            end = node;
            middle = node;
            size++;
        } else if (size == 1)
            pushFront(val);
        else {
            if (size % 2 == 0) {
                Node next = middle.next;
                middle.next = node;
                node.prev = middle;
                next.prev = node;
                node.next = next;
            } else {
                Node prev = middle.prev;
                middle.prev = node;
                node.next = middle;
                prev.next = node;
                node.prev = prev;
            }
            middle = node;
            size++;
        }
    }
    
    public void pushBack(int val) {
        Node node = new Node(val);
        if (size == 0) {
            start = node;
            end = node;
            middle = node;
        } else {
            node.prev = end;
            end.next = node;
            end = node;
            if (size % 2 == 0)
                middle = middle.next;
        }
        size++;
    }
    
    public int popFront() {
        if (size == 0)
            return -1;
        int val = start.val;
        if (size == 1) {
            start = null;
            end = null;
            middle = null;
            size--;
            return val;
        } else {
            start.next.prev = null;
            start = start.next;
            if (size % 2 == 0)
                middle = middle.next;
            size--;
            return val;
        }
    }
    
    public int popMiddle() {
        if (size == 0)
            return -1;
        int val = middle.val;
        if (size == 1) {
            start = null;
            end = null;
            middle = null;
            size--;
            return val;
        } else if (size == 2)
            return popFront();
        else {
            Node prev = middle.prev, next = middle.next;
            prev.next = next;
            next.prev = prev;
            if (size % 2 == 1)
                middle = prev;
            else
                middle = next;
            size--;
            return val;
        }
    }
    
    public int popBack() {
        if (size == 0)
            return -1;
        int val = end.val;
        if (size == 1) {
            start = null;
            end = null;
            middle = null;
            size--;
            return val;
        } else {
            end.prev.next = null;
            end = end.prev;
            if (size % 2 == 1)
                middle = middle.prev;
            size--;
            return val;
        }
    }
}

class Node {
    int val;
    Node prev;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}

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

All Problems

All Solutions