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.
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
— TypeDeque{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.
Usage
The Deque
implements the following methods:
==(x::Deque, y::Deque)
empty!(d::Deque{T}) where T
first(d::Deque)
isempty(d::Deque)
last(d::Deque)
length(d::Deque)
pop!(d::Deque{T}) where T
popfirst!(d::Deque{T}) where T
push!(d::Deque{T}, x) where T
pushfirst!(d::Deque{T}, x) where T
Base.:==
— Method==(x::Deque, y::Deque)
Verify if the deques x
and y
are equal in terms of their contents.
Base.empty!
— Methodempty!(d::Deque{T}) where T
Reset the deque d
.
Base.first
— Methodfirst(d::Deque)
Returns the first element of the deque d
.
Base.isempty
— Methodisempty(d::Deque)
Verifies if deque d
is empty.
Base.last
— Methodlast(d::Deque)
Returns the last element of the deque d
.
Base.length
— Methodlength(d::Deque)
Returns the number of elements in deque d
.
Base.pop!
— Methodpop!(d::Deque{T}) where T
Remove the element at the back of deque d
.
Base.popfirst!
— Methodpopfirst!(d::Deque{T}) where T
Remove the element at the front of deque d
.
Base.push!
— Methodpush!(d::Deque{T}, x) where T
Add an element to the back of deque d
.
Base.pushfirst!
— Methodpushfirst!(d::Deque{T}, x) where T
Add an element to the front of deque d
.