双端队列（Deque）原理及实现

labuladong原创约 1561 字

前置知识

阅读本文前，你需要先学习：

基本原理

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

java 🟢

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();
}

cpp 🤖

template<typename E>
class MyDeque {
public:
    // 从队头插入元素，时间复杂度 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 🤖

class MyDeque:
    # 从队头插入元素，时间复杂度 O(1)
    def add_first(self, e):
        pass

    # 从队尾插入元素，时间复杂度 O(1)
    def add_last(self, e):
        pass

    # 从队头删除元素，时间复杂度 O(1)
    def remove_first(self):
        pass

    # 从队尾删除元素，时间复杂度 O(1)
    def remove_last(self):
        pass

    # 查看队头元素，时间复杂度 O(1)
    def peek_first(self):
        pass

    # 查看队尾元素，时间复杂度 O(1)
    def peek_last(self):
        pass

go 🤖

// MyDeque represents a deque (double-ended queue) data structure
type MyDeque[E any] struct {
}

// 从队头插入元素，时间复杂度 O(1)
func (d *MyDeque[E]) AddFirst(e E) {
}

// 从队尾插入元素，时间复杂度 O(1)
func (d *MyDeque[E]) AddLast(e E) {
}

// 从队头删除元素，时间复杂度 O(1)
func (d *MyDeque[E]) RemoveFirst() E {
}

// 从队尾删除元素，时间复杂度 O(1)
func (d *MyDeque[E]) RemoveLast() E {
}

// 查看队头元素，时间复杂度 O(1)
func (d *MyDeque[E]) PeekFirst() E {
}

// 查看队尾元素，时间复杂度 O(1)
func (d *MyDeque[E]) PeekLast() E {
}

javascript 🤖

var MyDeque = function() {
    // 从队头插入元素，时间复杂度 O(1)
    this.addFirst = function(e) {};

    // 从队尾插入元素，时间复杂度 O(1)
    this.addLast = function(e) {};

    // 从队头删除元素，时间复杂度 O(1)
    this.removeFirst = function() {};

    // 从队尾删除元素，时间复杂度 O(1)
    this.removeLast = function() {};

    // 查看队头元素，时间复杂度 O(1)
    this.peekFirst = function() {};

    // 查看队尾元素，时间复杂度 O(1)
    this.peekLast = function() {};
};

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

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

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

用链表实现双端队列

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

java 🟢

import java.util.LinkedList;

public 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();
    }

    public static void main(String[] args) {
        MyListDeque<Integer> deque = new MyListDeque<>();
        deque.addFirst(1);
        deque.addFirst(2);
        deque.addLast(3);
        deque.addLast(4);

        System.out.println(deque.removeFirst()); // 2
        System.out.println(deque.removeLast()); // 4
        System.out.println(deque.peekFirst()); // 1
        System.out.println(deque.peekLast()); // 3
    }
}

cpp 🤖

#include <iostream>
#include <list>

template<typename E>
class MyListDeque {
    std::list<E> list;

public:
    // 从队头插入元素，时间复杂度 O(1)
    void addFirst(const E &e) {
        list.push_front(e);
    }

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

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

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

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

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

int main() {
    MyListDeque<int> deque;
    deque.addFirst(1);
    deque.addFirst(2);
    deque.addLast(3);
    deque.addLast(4);

    std::cout << deque.removeFirst() << std::endl; // 2
    std::cout << deque.removeLast() << std::endl; // 4
    std::cout << deque.peekFirst() << std::endl; // 1
    std::cout << deque.peekLast() << std::endl; // 3
    return 0;
}

go 🤖

package main

import (
	"container/list"
	"fmt"
)

type MyListDeque struct {
	list *list.List
}

func NewMyListDeque() *MyListDeque {
	return &MyListDeque{list: list.New()}
}

// 从队头插入元素，时间复杂度 O(1)
func (d *MyListDeque) AddFirst(e interface{}) {
	d.list.PushFront(e)
}

// 从队尾插入元素，时间复杂度 O(1)
func (d *MyListDeque) AddLast(e interface{}) {
	d.list.PushBack(e)
}

// 从队头删除元素，时间复杂度 O(1)
func (d *MyListDeque) RemoveFirst() interface{} {
	if elem := d.list.Front(); elem != nil {
		return d.list.Remove(elem)
	}
	return nil
}

// 从队尾删除元素，时间复杂度 O(1)
func (d *MyListDeque) RemoveLast() interface{} {
	if elem := d.list.Back(); elem != nil {
		return d.list.Remove(elem)
	}
	return nil
}

// 查看队头元素，时间复杂度 O(1)
func (d *MyListDeque) PeekFirst() interface{} {
	if elem := d.list.Front(); elem != nil {
		return elem.Value
	}
	return nil
}

// 查看队尾元素，时间复杂度 O(1)
func (d *MyListDeque) PeekLast() interface{} {
	if elem := d.list.Back(); elem != nil {
		return elem.Value
	}
	return nil
}

func main() {
	deque := NewMyListDeque()
	deque.AddFirst(1)
	deque.AddFirst(2)
	deque.AddLast(3)
	deque.AddLast(4)

	fmt.Println(deque.RemoveFirst()) // 2
	fmt.Println(deque.RemoveLast())  // 4
	fmt.Println(deque.PeekFirst())   // 1
	fmt.Println(deque.PeekLast())    // 3
}

python 🤖

# 用 Python 的 deque 模拟双链表
from collections import deque

class MyListDeque:
    def __init__(self):
        self.deque = deque()

    # 从队头插入元素，时间复杂度 O(1)
    def add_first(self, e):
        self.deque.appendleft(e)

    # 从队尾插入元素，时间复杂度 O(1)
    def add_last(self, e):
        self.deque.append(e)

    # 从队头删除元素，时间复杂度 O(1)
    def remove_first(self):
        return self.deque.popleft()

    # 从队尾删除元素，时间复杂度 O(1)
    def remove_last(self):
        return self.deque.pop()

    # 查看队头元素，时间复杂度 O(1)
    def peek_first(self):
        return self.deque[0]

    # 查看队尾元素，时间复杂度 O(1)
    def peek_last(self):
        return self.deque[-1]

# 使用示例
my_deque = MyListDeque()

my_deque.add_first(1)
my_deque.add_first(2)
my_deque.add_last(3)
my_deque.add_last(4)

print(my_deque.remove_first())  # 2
print(my_deque.remove_last())  # 4
print(my_deque.peek_first())  # 1
print(my_deque.peek_last())  # 3

javascript 🤖

class MyListDeque {
    constructor() {
        // JavaScript 中没有提供双链表，我们暂且用数组来模拟
        // 但是要注意，数组的头部插入和删除元素的时间复杂度是 O(n)，不是 O(1)
        // 所以下面 addFirst 和 removeFirst 方法的时间复杂度实际应该是 O(n)
        // 如果你手动实现一个双链表，那么所有的方法的复杂度就是 O(1) 了
        this.deque = [];
    }

    // 从队头插入元素，时间复杂度 O(1)
    addFirst(e) {
        this.deque.unshift(e);
    }

    // 从队尾插入元素，时间复杂度 O(1)
    addLast(e) {
        this.deque.push(e);
    }

    // 从队头删除元素，时间复杂度 O(1)
    removeFirst() {
        return this.deque.shift();
    }

    // 从队尾删除元素，时间复杂度 O(1)
    removeLast() {
        return this.deque.pop();
    }

    // 查看队头元素，时间复杂度 O(1)
    peekFirst() {
        return this.deque[0];
    }

    peekLast() {
        return this.deque[this.deque.length - 1];
    }
}

// 使用示例
const myDeque = new MyListDeque();

myDeque.addFirst(1);
myDeque.addFirst(2);
myDeque.addLast(3);
myDeque.addLast(4);

console.log(myDeque.removeFirst()); // 2
console.log(myDeque.removeLast()); // 4
console.log(myDeque.peekFirst()); // 1
console.log(myDeque.peekLast()); // 3

用数组实现双端队列

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

java 🟢

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();
    }
}

cpp 🤖

template <typename E>
class CycleArray {
public:
    void addFirst(E e);
    void addLast(E e);
    E removeFirst();
    E removeLast();
    E getFirst();
    E getLast();
};

template <typename E>
class MyArrayDeque {
private:
    CycleArray<E> arr;

public:
    // 从队头插入元素，时间复杂度 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();
    }
};

python 🤖

class MyArrayDeque:
    def __init__(self):
        self.arr = CycleArray()

    # 从队头插入元素，时间复杂度 O(1)
    def add_first(self, e):
        self.arr.add_first(e)

    # 从队尾插入元素，时间复杂度 O(1)
    def add_last(self, e):
        self.arr.add_last(e)

    # 从队头删除元素，时间复杂度 O(1)
    def remove_first(self):
        return self.arr.remove_first()

    # 从队尾删除元素，时间复杂度 O(1)
    def remove_last(self):
        return self.arr.remove_last()

    # 查看队头元素，时间复杂度 O(1)
    def peek_first(self):
        return self.arr.get_first()

    # 查看队尾元素，时间复杂度 O(1)
    def peek_last(self):
        return self.arr.get_last()

go 🤖

// MyArrayDeque is a generic deque implemented using a CycleArray
type MyArrayDeque[E any] struct {
	arr CycleArray[E]
}

// NewMyArrayDeque creates a new MyArrayDeque
func NewMyArrayDeque[E any]() *MyArrayDeque[E] {
	return &MyArrayDeque[E]{arr: CycleArray[E]{}}
}

// 从队头插入元素，时间复杂度 O(1)
func (d *MyArrayDeque[E]) AddFirst(e E) {
	d.arr.AddFirst(e)
}

// 从队尾插入元素，时间复杂度 O(1)
func (d *MyArrayDeque[E]) AddLast(e E) {
	d.arr.AddLast(e)
}

// 从队头删除元素，时间复杂度 O(1)
func (d *MyArrayDeque[E]) RemoveFirst() E {
	return d.arr.RemoveFirst()
}

// 从队尾删除元素，时间复杂度 O(1)
func (d *MyArrayDeque[E]) RemoveLast() E {
	return d.arr.RemoveLast()
}

// 查看队头元素，时间复杂度 O(1)
func (d *MyArrayDeque[E]) PeekFirst() E {
	return d.arr.GetFirst()
}

// 查看队尾元素，时间复杂度 O(1)
func (d *MyArrayDeque[E]) PeekLast() E {
	return d.arr.GetLast()
}

javascript 🤖

var MyArrayDeque = function() {
    this.arr = new CycleArray();

    // 从队头插入元素，时间复杂度 O(1)
    this.addFirst = function(e) {
        this.arr.addFirst(e);
    };

    // 从队尾插入元素，时间复杂度 O(1)
    this.addLast = function(e) {
        this.arr.addLast(e);
    };

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

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

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

    // 查看队尾元素，时间复杂度 O(1)
    this.peekLast = function() {
        return this.arr.getLast();
    };
};