GitHub

Deque

A Deque (short for Double-ended Queue) is an abstract data type that generalizes a Queue for which elements can be added to or removed from both the front (head) and the back (tail) in $O(1)$ time complexity.

The type Deque implements the Double-ended Queue as a list of fixed-size blocks using an unrolled linked list.

Note

Julia's Vector type also provides this interface, and thus can be used as a deque. However, the Deque type in DataStructures.jl is implemented as a list of contiguous blocks (default size = 1 kilo-byte). As a Deque grows, new blocks are created and linked to existing blocks. This approach prevents copying operations that take place when growing a Vector.

Benchmark shows that the performance of Deque is comparable to Vector on push!, but is noticeably faster on pushfirst! (by about 30% to 40%).

Constructors

DataStructures.Deque — Type
Deque{T}
Deque{T}(blksize::Int) where T

Constructs Deque object for elements of type T.

Parameters

T::Type Deque element data type.

blksize::Int Deque block size (in bytes). Default = 1024.

source

Usage

The Deque implements the following methods:

Base.:== — Method
==(x::Deque, y::Deque)

Verify if the deques x and y are equal in terms of their contents.

source
Base.first — Method
first(d::Deque)

Returns the first element of the deque d.

source
Base.last — Method
last(d::Deque)

Returns the last element of the deque d.

source
Base.length — Method
length(d::Deque)

Returns the number of elements in deque d.

source
Base.pop! — Method
pop!(d::Deque{T}) where T

Remove the element at the back of deque d.

source
Base.popfirst! — Method
popfirst!(d::Deque{T}) where T

Remove the element at the front of deque d.

source
Base.push! — Method
push!(d::Deque{T}, x) where T

Add an element to the back of deque d.

source
Base.pushfirst! — Method
pushfirst!(d::Deque{T}, x) where T

Add an element to the front of deque d.

source