# Deque

A double-ended queue, or deque (pronounced deck), is an abstract data type representing a sequence of values, where elements may be added or removed from both the head or tail of the sequence.

The deque can be thought of as a queue , with the removal of the limitation that elements may only be added to the back and removed from the front of the sequence.

## Common operations

Name Description
size() gets the number of elements stored in the deque
first() gets the element at the head of the deque
last() gets the element at the tail of the deque
addFirst(e) inserts element e at the head of the deque
addLast(e) inserts element e at the tail of the deque
removeFirst() removes and returns the element at the head of the deque
removeLast() removes and returns the element at the tail of the deque

## Doubly-linked list implementation

The interface of a deque may be implemented as a doubly-linked list , which allows performing all deque operations in $\mathcal{O}(1)$-time.

1public class LinkedDeque<E> extends DoubleLinkedList<E> {}