1670. Design Front Middle Back Queue #

题目 #

请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。

请你完成 FrontMiddleBack 类：

FrontMiddleBack() 初始化队列。
void pushFront(int val) 将 val 添加到队列的 最前面 。
void pushMiddle(int val) 将 val 添加到队列的 正中间 。
void pushBack(int val) 将 val 添加到队里的 最后面 。
int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。
int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。

思路 #

代码 #

class FrontMiddleBackQueue {

    private class ListNode {
        int val;
        ListNode prev;
        ListNode next;

        ListNode(int value, ListNode prev, ListNode next) {
            this.val = value;
            this.prev = prev;
            this.next = next;
        }
    }

    private int size;
    ListNode sentinel;
    ListNode middle;

    public FrontMiddleBackQueue() {
        this.size = 0;
        this.sentinel = new ListNode(-1, null, null);
        this.sentinel.prev = this.sentinel.next = this.sentinel;

        this.middle = this.sentinel;
    }
    
    public void pushFront(int val) {
        this.sentinel.next = new ListNode(val, this.sentinel, this.sentinel.next);
        this.sentinel.next.next.prev = this.sentinel.next;

        /** 对于 pushFront 操作：
         *  若插入前链表长度为偶数，则 middle 指针不移动
         *  若插入前链表长度为奇数，则 middle 指针需向前移动一位
         */
        if (this.size == 0) this.middle = this.sentinel.next;
        else if (this.size % 2 == 1) this.middle = this.middle.prev;

        this.size += 1;
    }
    
    public void pushMiddle(int val) {
        if (this.size == 0) {
            this.sentinel.next = new ListNode(val, this.sentinel, this.sentinel);
            this.sentinel.prev = this.sentinel.next;
            this.middle = this.sentinel.next;
            this.size += 1;
        }
        else if (this.size % 2 == 1) {
            this.middle.prev.next = new ListNode(val, this.middle.prev, this.middle);
            this.middle.prev = this.middle.prev.next;
            this.middle = this.middle.prev;
            this.size += 1;
        }
        else {
            this.middle.next = new ListNode(val, this.middle, this.middle.next);
            this.middle.next.next.prev = this.middle.next;
            this.middle = this.middle.next;
            this.size += 1;
        }
    }
    
    public void pushBack(int val) {
        this.sentinel.prev = new ListNode(val, this.sentinel.prev, this.sentinel);
        this.sentinel.prev.prev.next = this.sentinel.prev;

        /** 对于 pushBack 操作：
         *  若插入前链表长度为偶数，则 middle 指针需向后移动一位
         *  若插入前链表长度为奇数，则 middle 指针不移动
         */
         if (this.size == 0) this.middle = this.sentinel.next;
         else if (this.size % 2 == 0) this.middle = this.middle.next;

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

        int result = this.sentinel.next.val;

        this.sentinel.next = this.sentinel.next.next;
        this.sentinel.next.prev = this.sentinel;

        if (this.size == 1) this.middle = this.sentinel;
        else if (this.size % 2 == 0) this.middle = this.middle.next;

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

        int result = this.middle.val;

        this.middle.prev.next = this.middle.next;
        this.middle.next.prev = this.middle.prev;

        if (this.size == 1) this.middle = this.sentinel;
        else if (this.size % 2 == 0) this.middle = this.middle.next;
        else if (this.size % 2 == 1) this.middle = this.middle.prev;

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

        int result = this.sentinel.prev.val;

        this.sentinel.prev = this.sentinel.prev.prev;
        this.sentinel.prev.next = this.sentinel;

        if (this.size == 1) this.middle = this.sentinel;
        else if (this.size % 2 == 1) this.middle = this.middle.prev;

        this.size -= 1;
        return result;
    }
}