자료구조 Deque 클래스
(사용 가능한 버전 정보가 없으며 Git에만 있을 수 있음)
소개
Deque("deck"으로 발음)는 자동으로 증가하고 축소되는 연속 버퍼의 값 시퀀스입니다. 이름은 "양방향 대기열"의 일반적인 약어이며 Ds\Queue에서 내부적으로 사용됩니다.
두 개의 포인터는 머리와 꼬리를 추적하는 데 사용됩니다. 포인터는 버퍼의 끝을 "wrap around" 수 있으므로 공간을 만들기 위해 다른 값을 이동할 필요가 없습니다. 이를 통해 변속 및 변속 해제가 매우 빨라집니다. — Ds\Queue가 경쟁할 수 없는 것입니다.
인덱스로 값에 액세스하려면 인덱스와 버퍼의 해당 위치(((head + position) % capacity)
) 간의 변환이 필요합니다.
강점
- 배열 구문(대괄호)을 지원합니다.
- 동일한 수의 값에 대해 배열보다 적은 전체 메모리를 사용합니다.
- 크기가 충분히 낮아지면 할당된 메모리를 자동으로 해제합니다.
- get(), set(), push(), pop(), shift() 및 unshift()는 모두 O(1)입니다.
약점
- 용량은 2의 거듭제곱이어야 합니다.
- insert() 및 remove()는 모두 O(n)입니다.
클래스 개요
class Ds\Deque implements Ds\Sequence, ArrayAccess {
/* Constants */
const int MIN_CAPACITY = 8;
/* Methods */
public allocate(int $capacity): void
public apply(callable $callback): void
public capacity(): int
public clear(): void
public contains(mixed ...$values): bool
public copy(): Ds\Deque
public filter(callable $callback = ?): Ds\Deque
public find(mixed $value): mixed
public first(): mixed
public get(int $index): mixed
public insert(int $index, mixed ...$values): void
public isEmpty(): bool
public join(string $glue = ?): string
public last(): mixed
public map(callable $callback): Ds\Deque
public merge(mixed $values): Ds\Deque
public pop(): mixed
public push(mixed ...$values): void
public reduce(callable $callback, mixed $initial = ?): mixed
public remove(int $index): mixed
public reverse(): void
public reversed(): Ds\Deque
public rotate(int $rotations): void
public set(int $index, mixed $value): void
public shift(): mixed
public slice(int $index, int $length = ?): Ds\Deque
public sort(callable $comparator = ?): void
public sorted(callable $comparator = ?): Ds\Deque
public sum(): int|float
public toArray(): array
public unshift(mixed $values = ?): void
}
미리 정의된 상수
Ds\Deque::MIN_CAPACITY
변경 로그
버전 | 설명 |
---|---|
PECL ds 1.3.0 | 클래스는 이제 ArrayAccess를 구현합니다. |
목차
- Ds\Deque::allocate — 필요한 용량에 충분한 메모리 할당
- Ds\Deque::apply — 각 값에 콜백 함수를 적용하여 모든 값을 업데이트합니다.
- Ds\Deque::capacity — 현재 용량을 반환합니다.
- Ds\Deque::clear — 데크에서 모든 값을 제거합니다.
- Ds\Deque::__construct — 새 인스턴스를 만듭니다.
- Ds\Deque::contains — 데크에 주어진 값이 포함되어 있는지 확인
- Ds\Deque::copy — 데크의 얕은 복사본을 반환합니다.
- Ds\Deque::count — 컬렉션의 값 수를 반환합니다.
- Ds\Deque::filter — 포함할 값을 결정하기 위해 콜러블을 사용하여 새 데크를 만듭니다.
- Ds\Deque::find — Attempts to find a value's index
- Ds\Deque::first — Returns the first value in the deque
- Ds\Deque::get — Returns the value at a given index
- Ds\Deque::insert — Inserts values at a given index
- Ds\Deque::isEmpty — Returns whether the deque is empty
- Ds\Deque::join — Joins all values together as a string
- Ds\Deque::jsonSerialize — Returns a representation that can be converted to JSON
- Ds\Deque::last — Returns the last value
- Ds\Deque::map — Returns the result of applying a callback to each value
- Ds\Deque::merge — Returns the result of adding all given values to the deque
- Ds\Deque::pop — Removes and returns the last value
- Ds\Deque::push — Adds values to the end of the deque
- Ds\Deque::reduce — Reduces the deque to a single value using a callback function
- Ds\Deque::remove — Removes and returns a value by index
- Ds\Deque::reverse — Reverses the deque in-place
- Ds\Deque::reversed — Returns a reversed copy
- Ds\Deque::rotate — Rotates the deque by a given number of rotations
- Ds\Deque::set — Updates a value at a given index
- Ds\Deque::shift — Removes and returns the first value
- Ds\Deque::slice — Returns a sub-deque of a given range
- Ds\Deque::sort — Sorts the deque in-place
- Ds\Deque::sorted — Returns a sorted copy
- Ds\Deque::sum — Returns the sum of all values in the deque
- Ds\Deque::toArray — Converts the deque to an array
- Ds\Deque::unshift — Adds values to the front of the deque