Deque Implementation

labuladongOriginalAbout 2318 words

Prerequisite Knowledge

Before reading this article, you should first learn about:

Basic Principles

If you have understood the content explained earlier, there isn't much left to discuss about the deque. The main distinction of a deque, compared to a standard queue (FIFO - First In First Out queue), is that it offers 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 element insertion only at the back and element removal only from the front. In contrast, a deque (double-ended queue) allows insertion and removal of elements at both the front and the back.

A regular queue is similar to standing in line to buy tickets: first come, first served. A deque, however, is like a pedestrian bridge where you can enter and exit freely from both ends. Naturally, elements in a deque do not adhere to the "first in, first out" principle due to its flexibility.

In algorithmic problem-solving, deques are not used extensively. They are more commonly utilized in Python since the Python standard library does not include built-in stack and queue implementations, often using a deque to simulate a standard queue.

Implementing a Deque with a Linked List

It's quite straightforward; you can directly reuse our previously implemented MyLinkedList or use the standard library's LinkedList. A doubly linked list inherently supports $O(1)$ time complexity for adding and removing elements at both ends of the list:

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

go 🤖

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
}

python 🤖

# Use Python's deque to simulate a doubly linked list
from collections import deque

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

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

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

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

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

    # peek at the front element, time complexity O(1)
    def peek_first(self):
        return self.deque[0]

    # peek at the back element, time complexity O(1)
    def peek_last(self):
        return self.deque[-1]

# 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

javascript 🤖

class MyListDeque {
    constructor() {
        // JavaScript does not provide a doubly linked list, so we use an array to simulate it
        // however, note that the time complexity of inserting
        // and deleting elements at the head of an array is O(n),
        // so the time complexity of the addFirst and removeFirst methods below should be O(n)
        // If you manually implement a doubly linked
        // list, the complexity of all methods will be
        this.deque = [];
    }

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

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

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

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

    // peek at the front element, time complexity O(1)
    peekFirst() {
        return this.deque[0];
    }

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

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

It's quite simple. We can directly reuse the methods provided by the CycleArray, which we implemented in Circular Array Techniques. The complexity of adding or removing elements from the front or back 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();
    };
};