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