PHP Deque功能

Deque是一个可以自动增长和缩小的连续缓冲区值序列。它是”双端队列”的常用缩写，可以在Ds\Queue内部使用。

可以使用两个指针来跟踪头部和尾部。这些指针可以在缓冲区的末尾环绕，从而避免移动其他值以腾出空间。这可以使移动和插入操作非常快速。

通过索引访问值可能需要在索引和缓冲区中对应位置之间进行转换：((head + position) % capacity)。

优点

• 支持数组语法（方括号）。
• 对于相同数量的值，使用的内存比数组少。
• 在大小降低到足够低时，自动释放已分配的内存。
• 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( callablecallback )
   public int capacity( void )
   public void clear( void )
   public bool contains([ mixed ...values ] )
   public Ds\Deque copy( void )
   public Ds\Deque filter([ callablecallback ] )
   public mixed find( mixed value )
   public mixed first( void )
   public mixed get( intindex )
   public void insert( int index [, mixed...values ] )
   public bool isEmpty( void )
   public string join([ string glue ] )
   public mixed last( void )
   public Ds\Deque map( callablecallback )
   public Ds\Deque merge( mixed values )
   public mixed pop( void )
   public void push([ mixed...values ] )
   public mixed reduce( callable callback [, mixedinitial ] )
   public mixed remove( int index )
   public void reverse( void )
   public Ds\Deque reversed( void )
   public void rotate( introtations )
   public void set( int index , mixedvalue )
   public mixed shift( void )
   public Ds\Deque slice( int index [, intlength ] )
   public void sort([ callable comparator ] )
   public Ds\Deque sorted([ callablecomparator ] )
   public number sum( void )
   public array toArray( void )
   public void unshift([ mixed $values ] )
}

预定义常量

Ds\Deque::MIN_CAPACITY