LeetCode - 1670 设计前中后队列(设计 - 两个双端队列）

两个双端队列

class FrontMiddleBackQueue {
    
    //将所有值分为两部分
    //前半部分放在deque1 
    private Deque<Integer> deque1;
    //后半部分放在deque2
    private Deque<Integer> deque2;
    //使deque1的值个数要不与deque2的值个数相等(值个数为偶数) 要不比deque2多一个(值个数为奇数)
    public FrontMiddleBackQueue() {
    
        deque1 = new LinkedList<>();
        deque2 = new LinkedList<>();
    }
    public void makeBalance(){
    
        //使deque1的值个数要不与deque2的值个数相等(值个数为偶数) 要不比deque2多一个(值个数为奇数)
        //不满足的情况只有两种
        //deque1的值个数比deque2的值个数多两个
        if(deque1.size() > deque2.size()+1)
           deque2.offerFirst(deque1.pollLast());
           //deque2的值个数比deque1的值个数多一个
        if(deque2.size() > deque1.size())
          deque1.offerLast(deque2.pollFirst());
    }
    public void pushFront(int val) {
    
        //放在deque1的前面
        deque1.offerFirst(val);
        //维持一下平衡
        makeBalance();
    }
    
    public void pushMiddle(int val) {
    
        //若现有值为1 3 2
        //经过makeBalance deque1 1 3 deque2 2
        //此时pushMiddle 4
        //但是当值为奇数个时 pushMiddle是放在 3 之前的 所以要先把3 放入deque2 再把 4 放入deque1
        // deque1 1 4 deque2 3 2 
       if(deque1.size() > deque2.size())
           deque2.offerFirst(deque1.pollLast());
        //若现有值为1 4 3 2 
        //则deque1 1 4 deque2 3 2
        //pushMiddle 5
        //直接把5放入deque1
        //deque1 1 4 5 deque2 3 2
       deque1.offerLast(val);
    }
    
    public void pushBack(int val) {
    
        //直接放入deque2 末端
        deque2.offerLast(val);
        //维持平衡
        makeBalance();
    }
    
    public int popFront() {
    
        //在deque1不为空的情况下 直接返回deque1首端值
        if(deque1.size() != 0){
    
           int val =  deque1.pollFirst();
           makeBalance();
           return val;
        }
        //因为deque1的值个数一定比deque2值个数多 如果deque1为空的话说明当前值个数为0
        else
           return -1;
    }
    
    public int popMiddle() {
    
        //当值是奇数个
        //1 3 5 7 9
        // deque1 1 3 5 deque2 7 9
        //当值是偶数个
        // 1 3 5 7
        // deque1 1 3 deque2 5 7
        //不管怎么样 middle 都是deque1的末端值
        if(deque1.size() != 0){
    
            int val = deque1.pollLast();
            makeBalance();
             return val;
        }
        else
          return -1;
    }
    
    public int popBack() {
    
        //当值个数为0时 deque1 和deque2 都为空时 返回-1
       if(deque1.size() == 0 && deque2.size() == 0){
    
           return -1;
       }
       else if(deque2.size() != 0){
     //当值个数大于等于2时 deque2中一定有值 返回 deque2末端值
           int val = deque2.pollLast();
           makeBalance();
           return val;
       }else{
    // 当值个数为1 时 deque1.size() == 1 deque2.size() == 0 返回deque1的末端值
            int val = deque1.pollLast();
           makeBalance();
           return 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(); */