跳至主要內容

 

labuladong原创约 697 字大约 2 分钟

基本原理

如果你理解了前面讲解的内容,这个双端队列其实没啥可讲的了。所谓双端队列,主要是对比标准队列(FIFO 先进先出队列)多了一些操作罢了:

class MyDeque<E> {
    // 从队头插入元素,时间复杂度 O(1)
    void addFirst(E e);

    // 从队尾插入元素,时间复杂度 O(1)
    void addLast(E e);

    // 从队头删除元素,时间复杂度 O(1)
    E removeFirst();

    // 从队尾删除元素,时间复杂度 O(1)
    E removeLast();

    // 查看队头元素,时间复杂度 O(1)
    E peekFirst();

    // 查看队尾元素,时间复杂度 O(1)
    E peekLast();
}

标准队列 只能在队尾插入元素,队头删除元素,而双端队列的队头和队尾都可以插入或删除元素。

普通队列就好比排队买票,先来的先买,后来的后买;而双端队列就好比一个过街天桥,两端都可以随意进出。当然,双端队列的元素就不再满足「先进先出」了,因为它比较灵活嘛。

在做算法题的场景中,双端队列用的不算很多。感觉只有 Python 用到的多一些,因为 Python 标准库没有提供内置的栈和队列,一般会用双端队列来模拟标准队列。

用链表实现双端队列

很简单吧,直接复用 我们之前实现的 MyLinkedList 或者标准库提供的 LinkedList 就行了。因为双链表本就支持 O(1) 时间复杂度在链表的头尾增删元素:

class MyListDeque<E> {
    private LinkedList<E> list = new LinkedList<>();

    // 从队头插入元素,时间复杂度 O(1)
    void addFirst(E e) {
        list.addFirst(e);
    }

    // 从队尾插入元素,时间复杂度 O(1)
    void addLast(E e) {
        list.addLast(e);
    }

    // 从队头删除元素,时间复杂度 O(1)
    E removeFirst() {
        return list.removeFirst();
    }

    // 从队尾删除元素,时间复杂度 O(1)
    E removeLast() {
        return list.removeLast();
    }

    // 查看队头元素,时间复杂度 O(1)
    E peekFirst() {
        return list.getFirst();
    }

    // 查看队尾元素,时间复杂度 O(1)
    E peekLast() {
        return list.getLast();
    }
}

用数组实现双端队列

也很简单吧,直接复用我们在 环形数组技巧 中实现的 CycleArray 提供的方法就行了。环形数组头尾增删元素的复杂度都是 O(1)

class MyArrayDeque<E> {
    private CycleArray<E> arr = new CycleArray<>();

    // 从队头插入元素,时间复杂度 O(1)
    void addFirst(E e) {
        arr.addFirst(e);
    }

    // 从队尾插入元素,时间复杂度 O(1)
    void addLast(E e) {
        arr.addLast(e);
    }

    // 从队头删除元素,时间复杂度 O(1)
    E removeFirst() {
        return arr.removeFirst();
    }

    // 从队尾删除元素,时间复杂度 O(1)
    E removeLast() {
        return arr.removeLast();
    }

    // 查看队头元素,时间复杂度 O(1)
    E peekFirst() {
        return arr.getFirst();
    }

    // 查看队尾元素,时间复杂度 O(1)
    E peekLast() {
        return arr.getLast();
    }
}
上次编辑于: