Data Structures
PHP マニュアル

The Deque class

はじめに

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
class Ds\Deque implements Ds\Sequence, ArrayAccess {
/* 定数 */
const int Ds\Deque::MIN_CAPACITY = 8;
/* メソッド */
public void allocate(int $capacity)
public void apply(callable $callback)
public int capacity()
public void clear()
public bool contains(mixed ...$values)
public Ds\Deque copy()
public Ds\Deque filter(callable $callback = ?)
public mixed find(mixed $value)
public mixed first()
public mixed get(int $index)
public void insert(int $index, mixed ...$values)
public bool isEmpty()
public string join(string $glue = ?)
public mixed last()
public Ds\Deque map(callable $callback)
public Ds\Deque merge(mixed $values)
public mixed pop()
public void push(mixed ...$values)
public mixed reduce(callable $callback, mixed $initial = ?)
public mixed remove(int $index)
public void reverse()
public Ds\Deque reversed()
public void rotate(int $rotations)
public void set(int $index, mixed $value)
public mixed shift()
public Ds\Deque slice(int $index, int $length = ?)
public void sort(callable $comparator = ?)
public Ds\Deque sorted(callable $comparator = ?)
public intfloat sum()
public array toArray()
public void unshift(mixed $values = ?)
}

定義済み定数

Ds\Deque::MIN_CAPACITY

変更履歴

バージョン 説明
PECL ds 1.3.0 The class now implements ArrayAccess.

目次