Deque Implementation

labuladongOriginalAbout 2248 words

Prerequisites

Before reading this article, you should first study:

Basic Principle

If you have understood the previous content, there is not much new to discuss about the deque. A double-ended queue (deque) is just a queue that allows more operations compared to a standard queue (FIFO):

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

// 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 only allows inserting elements at the tail and removing elements from the head. In contrast, a deque allows inserting and removing elements from both the head and the tail.

A normal queue is like lining up to buy tickets: first come, first served. A deque is like a pedestrian bridge where you can enter or exit from either end. Of course, the elements in a deque no longer follow the "first in, first out" rule, because it is more flexible.

In algorithm problems, deques are not used very often. They are a bit more common in Python because the Python standard library does not provide built-in stack and queue types, so a deque is often used to simulate a standard queue.

Implementing a Deque with a Linked List

This is simple. Just reuse the MyLinkedList class we implemented earlier, or use the doubly linked list structure provided by your programming language's standard library. A doubly linked list naturally supports $O(1)$ time complexity for adding and removing elements at the head and tail:

java

import java.util.LinkedList;

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

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

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

python

class MyListDeque:
    def __init__(self):
        # use the `MyLinkedList` class we implemented before
        self.list = MyLinkedList()

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

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

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

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

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

    # peek at the back element, time complexity O(1)
    def peek_last(self):
        return self.list.get_last()

# usage example
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

package main

import (
	"container/list"
	"fmt"
)

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
}

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
}

javascript

class MyListDeque {
    constructor() {
        // JavaScript does not provide a doubly linked list, so we
        // use the `MyLinkedList` class we implemented before
        this.list = new MyLinkedList();
    }

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

    // insert element at the back, time complexity O(1)
    addLast(e) {
        this.list.addLast(e);
    }

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

    // remove element from the back, time complexity O(1)
    removeLast() {
        return this.list.removeLast();
    }

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

    peekLast() {
        return this.list.getLast();
    }
}

// usage example
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

Implementing a Deque with an Array

This is also straightforward. Just reuse the methods we wrote for CycleArray in Circular Array Techniques. Both adding and removing elements at the head and tail of a circular array are $O(1)$ operations:

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

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