The Deque class
(No version information available, might only be in Git)
소개
A Deque (pronounced “deck”) is a sequence of values
in a contiguous buffer that grows and shrinks automatically.
The name is a common abbreviation of “double-ended queue” and is used
internally by Ds\Queue.
Two pointers are used to keep track of a head and a tail. The pointers can
“wrap around” the end of the buffer, which avoids the need to move other
values around to make room. This makes shift and unshift very fast —
something a Ds\Vector can’t compete with.
Accessing a value by index requires a translation between the index and its
corresponding position in the buffer: ((head + position) % capacity)
.
Strengths
- Supports array syntax (square brackets).
- Uses less overall memory than an array for the same number of values.
- Automatically frees allocated memory when its size drops low enough.
-
get(),
set(),
push(),
pop(),
shift(), and
unshift() are all O(1).
Weaknesses
- Capacity must be a power of 2.
-
insert() and
remove() are O(n).
클래스 개요
Ds\Deque
implements
Ds\Sequence
{
public void clear
(
void
)
public Ds\Deque copy
(
void
)
public mixed first
(
void
)
public mixed get
(
int $index
)
public void insert
(
int $index
[,
mixed $...values
] )
public string join
([
string $glue
] )
public mixed last
(
void
)
public mixed pop
(
void
)
public mixed remove
(
int $index
)
public void rotate
(
int $rotations
)
public void set
(
int $index
,
mixed $value
)
public mixed shift
(
void
)
public Ds\Deque slice
(
int $index
[,
int $length
] )
public number sum
(
void
)
}
예약 상수
Ds\Deque::MIN_CAPACITY
-
Table of Contents
There are no user contributed notes for this page.