Design Front Middle Back Queue 设计前中后队列

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].

思路

通过2个双端队列拼接，实现一个队列的前中后插入删除

class FrontMiddleBackQueue {
    
public class Node {
    int val;
    Node next;
    Node pre;

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

    public void insert_pre(Node p){
        p.pre = pre;
        p.next = this;
        if (this.pre!=null){
            this.pre.next =p;
        }
        this.pre =p;
        return;
    }

    public void insert_next(Node p){
        p.next = this.next;
        p.pre = this;
        if (this.next!=null){
            this.next.pre = p;
        }
        this.next =p;
        return;
    }

    public void del_pre(){
        if(this.pre ==null){
            return;
        }
        Node p = this.pre;
        this.pre = p.pre;
        if (p.pre!=null){
            p.pre.next = this;
        }
        return;
    }

    public void del_next(){
        if(this.next ==null){
            return;
        }
        Node p = this.next;
        this.next = p.next;
        if (p.next!=null){
            p.next.pre = this;
        }
        return;
    }
}

 public class Queue {
        public Node head;//头节点,head中不存数据
        public Node tail;//尾节点后一位，tail不存数据
        public int cnt;//队列中元素个数

    Queue(){
        cnt = 0;
        tail = new Node(0);
        head = new Node(0);
        head.next = tail;
        head.pre =null;
        tail.next = null;
        tail.pre = head;
    }

    public int size(){
        return cnt;
    }

    public boolean isEmpty(){
        return head.next == tail;
    }

    //尾部入队 ，tail前插
    void push_back(int val){
        tail.insert_pre(new Node(val));
        cnt+=1;
    }
    //头部入队，head后插
    void push_front(int val){
        head.insert_next(new Node(val));
        cnt+=1;
    }

    //尾部出队，tail前删
    int pop_back(){
        if (isEmpty()){
            return  -1;
        }
        int ret = tail.pre.val;
        tail.del_pre();
        cnt-=1;
        return ret;
    }
    //头部出队，head后删
    int pop_front(){
        if (isEmpty()){
            return  -1;
        }
        int ret = head.next.val;
        head.del_next();
        cnt-=1;
        return ret;
    }

    //获取队首值
    int front(){
        return head.next.val;
    }
    int back(){
        return tail.pre.val;
    }
}
////////////////////////

    public Queue q1;
    public Queue q2;
    public FrontMiddleBackQueue() {
        q1 = new Queue();
        q2 = new Queue();
    }
    
    

    boolean isEmpty(){
        return q1.size() ==0;
    }

    //调整队列平衡  一般q1比q2多一个
    void update(){
        if (q1.size()<q2.size()){
            q1.push_back(q2.front());
            q2.pop_front();
        }
        if(q1.size()==q2.size()+2){
            q2.push_front(q1.back());
            q1.pop_back();
        }

    }
    //队列前插
    void pushFront(int val){
        q1.push_front(val);
        update();
    }
    //队列中插，在调整后插入q1尾
    void pushMiddle(int val){
        if (q1.size()>q2.size()){
            q2.push_front(q1.back());
            q1.pop_back();
        }
        q1.push_back(val);
    }
    //队列尾插
    void pushBack(int val){
        q2.push_back(val);
        update();
    }
    //队首出队
    int popFront(){
        if (isEmpty()){
            return  -1;
        }
        int ret = q1.pop_front();
        update();
        return ret;
    }
    //队中出队，q1尾出，update
    int popMiddle(){
        if (isEmpty()){
            return  -1;
        }
        int ret = q1.pop_back();
        update();;
        return ret;
    }
    //队尾出队，一般q2尾出，也有可能q1 尾出
    int popBack(){
        if (isEmpty()){
            return  -1;
        }
        int ret;
        if (!q2.isEmpty()){
            ret =q2.pop_back();
        }
        else {
            ret = q1.pop_back();
        }
        update();
        return ret;
    }
}

/**
 * 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();
 */