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

Basic Principle

If you understood the previous explanations, there isn't much new to say about the deque (double-ended queue). A deque mainly differs from a standard queue (FIFO - First In First Out queue) by offering additional operations:

java 🟢

class MyDeque<E> {
    // insert element at the head, time complexity O(1)
    void addFirst(E e);

    // insert element at the tail, time complexity O(1)
    void addLast(E e);

    // remove element from the head, time complexity O(1)
    E removeFirst();

    // remove element from the tail, time complexity O(1)
    E removeLast();

    // peek at the head element, time complexity O(1)
    E peekFirst();

    // peek at the tail element, time complexity O(1)
    E peekLast();
}

cpp 🤖

template<typename E>
class MyDeque {
public:
    // insert element from the front, time complexity O(1)
    void addFirst(E e);

    // insert element from the back, time complexity O(1)
    void addLast(E e);

    // remove element from the front, time complexity O(1)
    E removeFirst();

    // remove element from the back, time complexity O(1)
    E removeLast();

    // look at the front element, time complexity O(1)
    E peekFirst();

    // look at the back element, time complexity O(1)
    E peekLast();
};

python 🤖

class MyDeque:
    # insert an element at the front, time complexity O(1)
    def add_first(self, e):
        pass

    # insert an element at the back, time complexity O(1)
    def add_last(self, e):
        pass

    # remove an element from the front, time complexity O(1)
    def remove_first(self):
        pass

    # remove an element from the back, time complexity O(1)
    def remove_last(self):
        pass

    # peek at the front element, time complexity O(1)
    def peek_first(self):
        pass

    # peek at the back element, time complexity O(1)
    def peek_last(self):
        pass

go 🤖

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

// insert an element at the front of the deque, time complexity O(1)
func (d *MyDeque[E]) AddFirst(e E) {
}

// insert an element at the back of the deque, time complexity O(1)
func (d *MyDeque[E]) AddLast(e E) {
}

// remove an element from the front of the deque, time complexity O(1)
func (d *MyDeque[E]) RemoveFirst() E {
}

// remove an element from the back of the deque, time complexity O(1)
func (d *MyDeque[E]) RemoveLast() E {
}

// peek at the front element of the deque, time complexity O(1)
func (d *MyDeque[E]) PeekFirst() E {
}

// peek at the back element of the deque, time complexity O(1)
func (d *MyDeque[E]) PeekLast() E {
}

javascript 🤖

var MyDeque = function() {
    // insert element at the front, time complexity O(1)
    this.addFirst = function(e) {};

    // insert element at the rear, time complexity O(1)
    this.addLast = function(e) {};

    // remove element from the front, time complexity O(1)
    this.removeFirst = function() {};

    // remove element from the rear, time complexity O(1)
    this.removeLast = function() {};

    // peek at the front element, time complexity O(1)
    this.peekFirst = function() {};

    // peek at the rear element, time complexity O(1)
    this.peekLast = function() {};
};

A standard queue allows elements to be inserted only at the rear and removed only from the front, while a deque (double-ended queue) allows elements to be inserted or removed from both the front and the rear.

A standard queue is like standing in line to buy tickets: first come, first served. A deque, however, is like a pedestrian bridge where you can enter or exit from either end. Naturally, the elements in a deque do not follow the "first in, first out" principle due to its flexibility.

In algorithm problems, deques are not used very frequently. They seem to be more commonly used in Python since the Python standard library does not provide built-in stack and queue structures, so a deque is often used to simulate a standard queue.

Implementing a Deque with a Linked List

It's quite simple; just reuse the MyLinkedList we implemented before or the LinkedList provided by the standard library. A doubly linked list naturally supports O(1) time complexity for inserting and deleting elements at both the head and the tail:

java 🟢

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

    // insert element at the head of the deque, time complexity O(1)
    void addFirst(E e) {
        list.addFirst(e);
    }

    // insert element at the tail of the deque, time complexity O(1)
    void addLast(E e) {
        list.addLast(e);
    }

    // remove element from the head of the deque, time complexity O(1)
    E removeFirst() {
        return list.removeFirst();
    }

    // remove element from the tail of the deque, time complexity O(1)
    E removeLast() {
        return list.removeLast();
    }

    // peek at the head element of the deque, time complexity O(1)
    E peekFirst() {
        return list.getFirst();
    }

    // peek at the tail element of the deque, time complexity O(1)
    E peekLast() {
        return list.getLast();
    }
}

cpp 🤖

#include <list>

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

public:
    // insert element from the front of the deque, time complexity O(1)
    void addFirst(const E& e) {
        list.push_front(e);
    }

    // insert element from the back of the deque, time complexity O(1)
    void addLast(const E& e) {
        list.push_back(e);
    }

    // remove element from the front of the deque, time complexity O(1)
    E removeFirst() {
        E firstElement = list.front();
        list.pop_front();
        return firstElement;
    }

    // remove element from the back of the deque, time complexity O(1)
    E removeLast() {
        E lastElement = list.back();
        list.pop_back();
        return lastElement;
    }

    // peek at the front element, time complexity O(1)
    E peekFirst() {
        return list.front();
    }

    // peek at the back element, time complexity O(1)
    E peekLast() {
        return list.back();
    }
};

go 🤖

import (
    "container/list"
)

type MyListDeque struct {
    list *list.List
}

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

// Insert element at the front, time complexity O(1)
func (d *MyListDeque) AddFirst(e interface{}) {
    d.list.PushFront(e)
}

// Insert element at the end, time complexity O(1)
func (d *MyListDeque) AddLast(e interface{}) {
    d.list.PushBack(e)
}

// Remove element from the front, time complexity O(1)
func (d *MyListDeque) RemoveFirst() interface{} {
    if elem := d.list.Front(); elem != nil {
        return d.list.Remove(elem)
    }
    return nil
}

// Remove element from the end, time complexity O(1)
func (d *MyListDeque) RemoveLast() interface{} {
    if elem := d.list.Back(); elem != nil {
        return d.list.Remove(elem)
    }
    return nil
}

// Peek the front element, time complexity O(1)
func (d *MyListDeque) PeekFirst() interface{} {
    if elem := d.list.Front(); elem != nil {
        return elem.Value
    }
    return nil
}

// Peek the end element, time complexity O(1)
func (d *MyListDeque) PeekLast() interface{} {
    if elem := d.list.Back(); elem != nil {
        return elem.Value
    }
    return nil
}

Implementing a Deque with an Array

It’s quite simple. Just reuse the methods provided by the CycleArray we implemented in Circular Array Techniques. The complexity of adding or removing elements at both ends of a circular array is O(1):

java 🟢

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

    // insert element from the front of the deque, time complexity O(1)
    void addFirst(E e) {
        arr.addFirst(e);
    }

    // insert element from the end of the deque, time complexity O(1)
    void addLast(E e) {
        arr.addLast(e);
    }

    // remove element from the front of the deque, time complexity O(1)
    E removeFirst() {
        return arr.removeFirst();
    }

    // remove element from the end of the deque, time complexity O(1)
    E removeLast() {
        return arr.removeLast();
    }

    // peek at the front element of the deque, time complexity O(1)
    E peekFirst() {
        return arr.getFirst();
    }

    // peek at the end element of the deque, time complexity 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:
    // insert element from the front of the deque, time complexity O(1)
    void addFirst(E e) {
        arr.addFirst(e);
    }

    // insert element from the end of the deque, time complexity O(1)
    void addLast(E e) {
        arr.addLast(e);
    }

    // remove element from the front of the deque, time complexity O(1)
    E removeFirst() {
        return arr.removeFirst();
    }

    // remove element from the end of the deque, time complexity O(1)
    E removeLast() {
        return arr.removeLast();
    }

    // peek at the front element of the deque, time complexity O(1)
    E peekFirst() {
        return arr.getFirst();
    }

    // peek at the end element of the deque, time complexity O(1)
    E peekLast() {
        return arr.getLast();
    }
};

python 🤖

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

    # insert element from the front, time complexity O(1)
    def add_first(self, e):
        self.arr.add_first(e)

    # insert element from the back, time complexity O(1)
    def add_last(self, e):
        self.arr.add_last(e)

    # remove element from the front, time complexity O(1)
    def remove_first(self):
        return self.arr.remove_first()

    # remove element from the back, time complexity O(1)
    def remove_last(self):
        return self.arr.remove_last()

    # peek at the front element, time complexity O(1)
    def peek_first(self):
        return self.arr.get_first()

    # peek at the back element, time complexity 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]{}}
}

// insert element from the front of the deque, time complexity O(1)
func (d *MyArrayDeque[E]) AddFirst(e E) {
	d.arr.AddFirst(e)
}

// insert element from the back of the deque, time complexity O(1)
func (d *MyArrayDeque[E]) AddLast(e E) {
	d.arr.AddLast(e)
}

// remove element from the front of the deque, time complexity O(1)
func (d *MyArrayDeque[E]) RemoveFirst() E {
	return d.arr.RemoveFirst()
}

// remove element from the back of the deque, time complexity O(1)
func (d *MyArrayDeque[E]) RemoveLast() E {
	return d.arr.RemoveLast()
}

// view the front element of the deque, time complexity O(1)
func (d *MyArrayDeque[E]) PeekFirst() E {
	return d.arr.GetFirst()
}

// view the back element of the deque, time complexity O(1)
func (d *MyArrayDeque[E]) PeekLast() E {
	return d.arr.GetLast()
}

javascript 🤖

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

    // insert element from the front of the deque, time complexity O(1)
    this.addFirst = function(e) {
        this.arr.addFirst(e);
    };

    // insert element from the end of the deque, time complexity O(1)
    this.addLast = function(e) {
        this.arr.addLast(e);
    };

    // remove element from the front of the deque, time complexity O(1)
    this.removeFirst = function() {
        return this.arr.removeFirst();
    };

    // remove element from the end of the deque, time complexity O(1)
    this.removeLast = function() {
        return this.arr.removeLast();
    };

    // view the element at the front of the deque, time complexity O(1)
    this.peekFirst = function() {
        return this.arr.getFirst();
    };

    // view the element at the end of the deque, time complexity O(1)
    this.peekLast = function() {
        return this.arr.getLast();
    };
};