PHP 双端队列函数

双端队列是连续缓冲区中的一系列值，可以自动增长和收缩。它是“双端队列”的常见缩写，可由 Ds\Queue 内部使用。

可以使用两个指针来跟踪头部和尾部。指针可以环绕缓冲区的末尾，从而避免需要移动其他值来腾出空间。这可以使换档和取消换档变得非常快。

通过索引访问值可能需要索引与其在缓冲区中的相应位置之间的转换：（（头 + 位置）% 容量）。

优势

• 支持数组语法（方括号）。
• 对于相同数量的值，使用的总体内存少于数组。
• 当分配的内存大小足够低时，自动释放分配的内存。
• get()、set()、push()、pop()、shift() 和 unshift() 都是 O(1)。

弱点

• 容量必须是 2 的幂。
• insert() 和remove() 的时间复杂度为O(n)。

句法

Ds\Deque implements Ds\Sequence {
   /* Constants */
   const int MIN_CAPACITY = 8 ;

   /* Methods */
   public void allocate( int $capacity )
   public void apply( callable $callback )
   public int capacity( void )
   public void clear( void )
   public bool contains([ mixed $...values ] )
   public Ds\Deque copy( void )
   public Ds\Deque filter([ callable $callback ] )
   public mixed find( mixed $value )
   public mixed first( void )
   public mixed get( int $index )
   public void insert( int $index [, mixed $...values ] )
   public bool isEmpty( void )
   public string join([ string $glue ] )
   public mixed last( void )
   public Ds\Deque map( callable $callback )
   public Ds\Deque merge( mixed $values )
   public mixed pop( void )
   public void push([ mixed $...values ] )
   public mixed reduce( callable $callback [, mixed $initial ] )
   public mixed remove( int $index )
   public void reverse( void )
   public Ds\Deque reversed( void )
   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 void sort([ callable $comparator ] )
   public Ds\Deque sorted([ callable $comparator ] )
   public number sum( void )
   public array toArray( void )
   public void unshift([ mixed $values ] )
}

预定义常量

Ds\Deque::MIN_CAPACITY