乐趣区

关于php:PHP-Data-Structures-扩展介绍

在 PHP 中因为数组太过弱小,把这些数据结构都囊括进来了,所以不太须要去关注这些数据结构,长此以往这些概念也就淡化了,不是说 PHP 中没有数据结构。

在 PHP 中有个扩大 Data Structures,这个扩大蕴含了这些常见的 数据结构,具体的能够查看连贯 数据结构

PHP 数据结构

  • 优先级队列 PriorityQueue
  • 双端队列 Deque
  • 队列 FIFO(先进先出)
  • 栈 LIFO(先进后出)
  • 散列表 Hash

    • Set 汇合
    • Map 字典

数据结构介绍

优先级队列 PriorityQueue

PriorityQueue 与 Queue 十分类似。值被推入具备指定优先级的队列中,具备最高优先级的值将始终位于队列的后面。

留神

  • 对于具备雷同优先级的值,保留“先进先出”程序。
  • 迭代 PriorityQueue 是破坏性的,相当于间断弹出操作,直到队列为空。

设置容量

默认容量是 8,能够手动设置容量, 这个容量不是指队列的长度,而是说存储空间。再调配容量时确保有足够的内存

  • 如果该值小于或等于以后容量,容量将放弃不变。

    $queue = new Ds\PriorityQueue(); 
    $queue->allocate(8);

获取容量

  • 以后手动设置了容量时,如果设置的容量大于理论占用容量,则返回设置的容量。反之,返回理论的容量。

    $queue = new Ds\PriorityQueue(); 
    // 此时返回默认值 8
    $queue->capacity();

    设置优先级

    数值越大优先级越高

    $queue = new Ds\PriorityQueue(); 
    $queue->push('value1', 1);
    $queue->push('value2', 2);

    示例

    $queue = new Ds\PriorityQueue(); 
    $queue->push('沙僧', 2);
    $queue->push('唐僧', 5);
    $queue->push('白龙马', 1);
    $queue->push('猪八戒', 3);
    $queue->push('孙悟空', 4);
    $cout = $queue->count();
    for($i=0; $i<$cout; $i++) {echo $queue->pop();
      echo PHP_EOL;
    }

输入

 唐僧
孙悟空
猪八戒
沙僧
白龙马 

利用场景

  • MySQL 查问时为了放慢查问速度,防止排序无奈应用索引,没有进行排序,在服务端代码层面进行手动排序再返回。
  • 其余利用场景 …

双端队列 Deque

有两个指针别离指向头部和尾部。别离能够在头部和尾部进行插入和弹出。

长处

  • 反对数组语法(方括号)。
  • 对于雷同数量的值,比数组占用更少的内存。
  • 当其大小降落到足够低时,主动开释调配的内存。
  • get()、set()、push()、pop()、shift() 和 unshift() 都是 O(1)。

毛病

  • 设置的容量数值,必须是 2 的幂次方值,默认值是 8。比方 2^2
  • insert() 和 remove() 是 O(n)。

类办法阐明

双端队列 Deque

示例

$deque = new Ds\Deque();
$deque->push(...['唐僧', '孙悟空', '猪八戒', '沙僧', '白龙马']);
$clone = $deque->copy();
$count = $deque->count();
echo '头:'.$deque->first().PHP_EOL;
echo '尾:'.$deque->last().PHP_EOL;
echo '--- 从队尾开始 ----'.PHP_EOL;
for($i=0; $i<$count; $i++) {echo $deque->pop();
    echo PHP_EOL;
}

echo '--- 从队头开始 ----'.PHP_EOL;
for($i=0; $i<$count; $i++) {echo $clone->shift();
    echo PHP_EOL;
}

输入

 头:唐僧
尾:白龙马
--- 从队尾开始 ----
白龙马
沙僧
猪八戒
孙悟空
唐僧
--- 从队头开始 ----
唐僧
孙悟空
猪八戒
沙僧
白龙马 

利用场景

  • 多种利用场景

队列 FIFO(先进先出)

队列是“先进先出”或“FIFO”汇合,它只容许拜访队列后面的值。

示例

$queue = new Ds\Queue(); 
$queue->push('唐僧');
$queue->push(...['孙悟空', '猪八戒']);
$queue->push(['沙僧', '白龙马']);
print_r($queue);

输入

Ds\Queue Object
([0] => 唐僧
    [1] => 孙悟空
    [2] => 猪八戒
    [3] => Array
        ([0] => 沙僧
            [1] => 白龙马
        )
)

栈 LIFO(先进后出)

Stack 是一个“后进先出”或“LIFO”汇合,它只容许拜访构造顶部的值。

示例

$Stack = new Ds\Stack(); 
$Stack->push('唐僧');
$Stack->push(...['孙悟空', '猪八戒']);
$Stack->push(...['沙僧', '白龙马']);

$cout = $Stack->count();
for($i=0; $i<$cout; $i++) {echo $Stack->pop();
    echo PHP_EOL;
}

输入

 白龙马
沙僧
猪八戒
孙悟空
唐僧 

Map 字典

Map 是键值对 [key=>value] 的程序汇合,与数组类似。键能够是任何类型,但必须是惟一的。如果应用雷同的键将值增加到地图,后增加的则会替换之前的值。

长处

  • 键和值能够是任何类型,包含对象
  • 反对数组语法。
  • 保留插入程序。
  • 性能和内存效率与数据类似。
  • 当大小降落到足够低时主动开释调配的内存。

毛病

  • 当对象作为键时,不能转换为数组。

Set 汇合

Set 是一系列惟一值,只有一组 key 不存储 value,而且 key 不能反复。

长处

  • 值能够是任何类型,包含对象。
  • 反对数组语法。
  • 保留插入程序。
  • 当大小降落到足够低时主动开释调配的内存。
  • add()、remove() 和 contains() 复杂度都是 O(1)。

毛病

  • 不反对 push()、pop()、insert()、shift() 或 unshift()
  • 如果在被拜访的索引之前缓冲区中有被删除的值,则 get() 为 O(n),否则为 O(1)。

Map 和 Set 的区别

  1. 存储形式不同。Map 存储的是 [key => value] 模式,Set 存储的是 […keys];
  2. Map 和 Set 都是通过 key 来保障有序性的,所以是不容许批改 key 的。
退出移动版