자료구조 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를 구현합니다.

목차