双端队列

---

题目链接

https://leetcode.cn/problems/design-circular-deque/

思路分析

内部实现

双端队列和双向链表的本质相同，直接采用 LinkedList 内部封装好的方法即可

数组实现

延续了用数组实现循环队列的思想，定义两个指针，L 表示头指针，R 表示尾指针，两个指针指向索引位置（区别于数组实现的栈、队列中的指针指向的位置）

头部操作

入队

（1）若 l = 0，则元素放在 k - 1 位置，l 来到 k - 1 位置

（2）若 l ≠ 0，则元素放在 l - 1 位置，l --

出队

（1）若 l = k -1，则 l 来到 0 位置

（2）若 l ≠ k - 1，则 l ++

尾部操作

入队

（1）若 r = k - 1，则元素放在 0 位置，r 来到 0 位置

（2）若 r ≠ k - 1，则元素放在 r + 1 位置，r ++

出队

（1）若 r = 0，则 r 来到 k - 1 位置

（2）若 r ≠ 0，则 r --

代码实现

内部实现

class MyCircularDeque {

    public Deque<Integer> deque = new LinkedList<>();
    public int size;
    public int limit;

    public MyCircularDeque(int k) {
        size = 0;
        limit = k;
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        } else {
            deque.addFirst(value);
            size++;
            return true;
        }
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        } else {
            deque.addLast(value);
            size++;
            return true;
        }
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        } else {
            deque.pollFirst();
            size--;
            return true;
        }
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        } else {
            deque.pollLast();
            size--;
            return true;
        }
    }

    public int getFront() {
        if (isEmpty()){
            return -1;
        }
        return deque.peekFirst();
    }

    public int getRear() {
        if (isEmpty()){
            return -1;
        }
        return deque.peekLast();
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == limit;
    }
}

数组实现

class MyCircularDeque {
    public int[] deque;
    public int l, r, size, limit;

    public MyCircularDeque(int k) {
        deque = new int[k];
        l = r = size = 0;
        limit = k;
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        } else {
            // 需要考虑初始为空的情况
            if (isEmpty()) {
                l = r = 0;
                deque[0] = value;
            } else {
                // 先移动指针，再放元素
                l = (l == 0) ? (limit - 1) : (l - 1);
                deque[l] = value;
            }
            size++;
            return true;
        }
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        } else {
            // 需要考虑初始为空的情况
            if (isEmpty()) {
                l = r = 0;
                deque[0] = value;
            } else {
                r = (r == limit - 1) ? 0 : (r + 1);
                deque[r] = value;
            }
            size++;
            return true;
        }
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        } else {
            l = (l == limit - 1) ? 0 : (l + 1);
            size--;
            return true;
        }
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        } else {
            r = (r == 0) ? (limit - 1) : (r - 1);
            size--;
            return true;
        }
    }

    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return deque[l];
    }

    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return deque[r];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == limit;
    }
}