一起学习PHP中的DS数据结构扩展（一） php

在之前学习 SPL 相关的文章中，我们已经学习过 SPL 中的一些数据结构相关的数据结构对象，非常强大也非常好用，最主要的是 SPL 已经集成在 PHP 源码中不需要我们再单独地安装别的什么扩展。但是，今天我们要学习的这个 DataStruct 扩展库的内容则更加地丰富，不过相对应的，这套扩展是需要我们自己手动再进行安装的。如果大家对于数据结构的需求不高的话，使用 SPL 中的相关对象就够用了，但是如果需要更加丰富的数据结构类型的话，这套 DS 扩展是更好的选择。
DS 扩展的安装和其它普通的扩展安装没有什么区别，也不需要额外的操作系统上的组件支持，直接安装即可。
栈首先还是从栈这个最基本的数据结构说起。DS 中的栈结构非常地简单好用。

$stack = new \Ds\Stack(); var_dump($stack); // object(Ds\Stack)#1 (0) { // }$stack = new \Ds\Stack([1, 2, 3]); var_dump($stack); // object(Ds\Stack)#2 (3) { //[0]=> //int(3) //[1]=> //int(2) //[2]=> //int(1) //}

两种方式实例化栈对象，其实就是参数的不同，如果我们直接给构造函数传递一个数组的话，那么这个数组就会做为栈内部的元素供我们使用。

$stack->push(4); $stack->push(5); var_dump($stack); // object(Ds\Stack)#2 (5) { //[0]=> //int(5) //[1]=> //int(4) //[2]=> //int(3) //[3]=> //int(2) //[4]=> //int(1) //}var_dump($stack->pop()); // int(5) var_dump($stack->pop()); // int(4) var_dump($stack); // object(Ds\Stack)#2 (3) { //[0]=> //int(3) //[1]=> //int(2) //[2]=> //int(1) //}

push() 就是将数据压栈，pop() 则是将栈顶的元素弹出。关于栈的最主要的操作其实就是这两个方法函数了。

var_dump($stack->peek()); // int(3) // object(Ds\Stack)#2 (3) { //[0]=> //int(3) //[1]=> //int(2) //[2]=> //int(1) //}

peek() 这个函数是直接获取栈顶的数据，但是需要注意的是，它不会弹出栈顶的元素。也就是说，这个 peek() 方法只会取得数据的内容，不会改变栈内部的数据。

var_dump($stack->count()); // int(3) var_dump($stack->isEmpty()); // bool(false) var_dump($stack->toArray()); // array(3) { //[0]=> //int(3) //[1]=> //int(2) //[2]=> //int(1) //}$stack->clear(); var_dump($stack); // object(Ds\Stack)#2 (0) { // }

count() 返回栈内部元素的数量，isEmpty() 用于判断栈是否为空，toArray() 直接以数组的格式返回栈内部的数据，clear() 方法用于清空栈。这些方法函数都非常地简单，所以就不多做解释了。最后我们来看看栈对象的赋值拷贝操作。

$a = $stack; $a->push(4); var_dump($stack); // object(Ds\Stack)#2 (1) { //[0]=> //int(4) //}$b = $stack->copy(); $b->push(5); var_dump($stack); // object(Ds\Stack)#2 (1) { //[0]=> //int(4) //}var_dump($b); // object(Ds\Stack)#1 (2) { //[0]=> //int(5) //[1]=> //int(4) //}

\$stack 对象是实例化之后的对象，在普通的赋值操作中是引用传递的。上文中我们清空了 $stack ，然后在这里我们让 $a 等于这个 $stack ，然后操作 $a 相应地 $stack 里面的内容也发生了变化。对于引用传递这个问题，我们一般会使用 \_\_clone() 魔术方法来解决， Stack 类直接就为我们提供了一个 copy() 方法，直接可以获得一个栈对象的拷贝，也可以说是一个新的栈对象。就像上面代码中的 $b 一样，当使用 copy() 方法赋值给 $b 之后，它就成为了一个新的栈对象，任何 $b 的操作和 $stack 对象就没有什么关系了。我们可以看到对象id 也完全不同了。
队列对于队列来说，整体上的功能方法和栈的内容差不多，它们实现的方法基本上是一模一样的。具体在实现层面上的不同就体现在弹栈和出队的不同，也就是 push() 方法在实现中有差别。

$queue = new \Ds\Queue(); var_dump($queue); // object(Ds\Queue)#3 (0) { // }$queue = new \Ds\Queue([1, 2, 3]); var_dump($queue); // object(Ds\Queue)#4 (3) { //[0]=> //int(1) //[1]=> //int(2) //[2]=> //int(3) //}$queue->push(4); $queue->push(5); var_dump($queue); // object(Ds\Queue)#4 (5) { //[0]=> //int(1) //[1]=> //int(2) //[2]=> //int(3) //[3]=> //int(4) //[4]=> //int(5) //}var_dump($queue->pop()); // int(1) var_dump($queue->pop()); // int(2) var_dump($queue); // object(Ds\Queue)#4 (3) { //[0]=> //int(3) //[1]=> //int(4) //[2]=> //int(5) //}

可以看出，在队列中，我们 push() 进来的数据的顺序是 1,2,3,4,5 这样正序的，也就是将数据放到内部这个数组的底部，出队 pop() 直接拿最顶上的数据也就实现了先进先出的效果。对比上面栈的数据内容，就可以发现栈的数据在 push() 的时候就是反过来的，5、4、3、2、1 这样的，然后在 pop() 的时候其实也是从顶部拿出数据，只不过栈是将数据 push() 到内部数组的顶部的，然后从顶部直接拿出数据实现了后进先出的效果。
优先队列最重要的两个数据结构说完了，我们再来看一个队列的扩展结构，也就是优先队列的实现。其实这个队列就是在 push() 数据的时候多了一个参数，也就是数据的优先级，越大的越靠前，其它的方法和普通队列以及栈的方法都没什么太大的区别。

$pQueue = new \Ds\PriorityQueue(); $pQueue->push(1, 100); $pQueue->push(2, 101); $pQueue->push(3, 99); var_dump($pQueue); // object(Ds\PriorityQueue)#3 (3) { //[0]=> //int(2) //[1]=> //int(1) //[2]=> //int(3) //}var_dump($pQueue->pop()); // int(2) var_dump($pQueue->pop()); // int(1) var_dump($pQueue->pop()); // int(3)

Map 最后我们来学习一个 Map 数据结构，其实也就是 HaspMap 这种 K/V 的键值对形式的数据结构。只能说 PHP 中的数组实在是太强大了，完全兼容了这种数据结构，所以使得单独的 Map 结构并没有什么实际的意义。

$map = new \Ds\Map(['a'=>1, 2, 5=>3]); var_dump($map); // object(Ds\Map)#5 (3) { //[0]=> //object(Ds\Pair)#6 (2) { //["key"]=> //string(1) "a" //["value"]=> //int(1) //} //[1]=> //object(Ds\Pair)#7 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[2]=> //object(Ds\Pair)#8 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //}var_dump($map->get(0)); // int(2) var_dump($map->get(5)); // int(3)$map->put('b', '4'); $map->put('c', [1, 2, 3]); $map->put('d', new class{public $t = 't'; }); var_dump($map); // object(Ds\Map)#5 (6) { //[0]=> //object(Ds\Pair)#7 (2) { //["key"]=> //string(1) "a" //["value"]=> //int(1) //} //[1]=> //object(Ds\Pair)#6 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[2]=> //object(Ds\Pair)#9 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //[3]=> //object(Ds\Pair)#10 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "4" //} //[4]=> //object(Ds\Pair)#11 (2) { //["key"]=> //string(1) "c" //["value"]=> //array(3) { //[0]=> //int(1) //[1]=> //int(2) //[2]=> //int(3) //} //} //[5]=> //object(Ds\Pair)#12 (2) { //["key"]=> //string(1) "d" //["value"]=> //object(class@anonymous)#8 (1) { //["t"]=> //string(1) "t" //} //} //}$map->remove('d'); $map->remove('c'); var_dump($map); // object(Ds\Map)#5 (4) { //[0]=> //object(Ds\Pair)#8 (2) { //["key"]=> //string(1) "a" //["value"]=> //int(1) //} //[1]=> //object(Ds\Pair)#12 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[2]=> //object(Ds\Pair)#11 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //[3]=> //object(Ds\Pair)#10 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "4" //} //}

在 Java 之类的语言中，数组和 HashMap 是两种东西，或者说是两种集合对象，比如 List\ 就是一个数据集合，而 Map\ 就是一个 HashMap 集合。相对应的，在 Java 的这种泛型集合中，我们需要添加和获取数据就要像这个 DS 扩展中的 Map 一样使用 get()、put()、remove() 类似的方法来实现。
Map 这个数据结构与上面的栈、队列之类的数据结构中实现的方法差别还是挺大的。

var_dump($map->first()); // object(Ds\Pair)#8 (2) { //["key"]=> //string(1) "a" //["value"]=> //int(1) //}var_dump($map->last()); // object(Ds\Pair)#8 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //}var_dump($map->sum()); // int(10)var_dump($map->hasKey('b')); // bool(true) var_dump($map->haskey('bb')); // bool(false)var_dump($map->hasValue('4')); // bool(true) var_dump($map->hasValue(4)); // bool(false)

它有 first() 和 last() 方法直接获取第一个和最后一个数据元素。也有 sum() 方法获得数据元素的个数，同时可以通过 hasKey() 和 hasValue() 来判断指定的键或者值是存在。是不是有点像 key_exists() 和 in_array() 这两个方法。当然，相对应的我们也可以直接获取这些 Key 和 Value 的内容。

var_dump($map->keys()); // object(Ds\Set)#10 (4) { //[0]=> //string(1) "a" //[1]=> //int(0) //[2]=> //int(5) //[3]=> //string(1) "b" //}var_dump($map->values()); // object(Ds\Vector)#10 (4) { //[0]=> //int(1) //[1]=> //int(2) //[2]=> //int(3) //[3]=> //string(1) "4" //}

我们可以看到，keys() 返回的内容是 Set 类型的对象，而 values() 返回的内容是 Vector 类型的对象，这两种也是 DS 中的数据结构类型，我们将在下篇文章中再学习。除了 Key 和 Values 之外，它还可以直接返回一个 Vector 类型的对象集合结构，使用 paris() 方法。

var_dump($map->pairs()); // object(Ds\Vector)#9 (4) { //[0]=> //object(Ds\Pair)#10 (2) { //["key"]=> //string(1) "a" //["value"]=> //int(1) //} //[1]=> //object(Ds\Pair)#11 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[2]=> //object(Ds\Pair)#12 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //[3]=> //object(Ds\Pair)#8 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "4" //} //}

【一起学习PHP中的DS数据结构扩展（一）】在 Map 对象中，还提供了一些为数据排序、合并两个 Map 以及截取一部分数据的方法，直接贴出代码吧。

$map->ksort(); var_dump($map); // object(Ds\Map)#5 (4) { //[0]=> //object(Ds\Pair)#9 (2) { //["key"]=> //string(1) "a" //["value"]=> //int(1) //} //[1]=> //object(Ds\Pair)#8 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[2]=> //object(Ds\Pair)#12 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "4" //} //[3]=> //object(Ds\Pair)#11 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //}$map->reverse(); var_dump($map); // object(Ds\Map)#5 (4) { //[0]=> //object(Ds\Pair)#11 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //[1]=> //object(Ds\Pair)#12 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "4" //} //[2]=> //object(Ds\Pair)#8 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[3]=> //object(Ds\Pair)#9 (2) { //["key"]=> //string(1) "a" //["value"]=> //int(1) //} //}$newMap = new \Ds\Map(); $newMap->put('a', 'a'); $newMap->put('b', 'b'); $newMap->put('e', 'e'); var_dump($map->diff($newMap)); // object(Ds\Map)#8 (2) { //[0]=> //object(Ds\Pair)#12 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //[1]=> //object(Ds\Pair)#11 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //}var_dump($map->union($newMap)); // object(Ds\Map)#8 (5) { //[0]=> //object(Ds\Pair)#11 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //[1]=> //object(Ds\Pair)#12 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "b" //} //[2]=> //object(Ds\Pair)#10 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[3]=> //object(Ds\Pair)#6 (2) { //["key"]=> //string(1) "a" //["value"]=> //string(1) "a" //} //[4]=> //object(Ds\Pair)#7 (2) { //["key"]=> //string(1) "e" //["value"]=> //string(1) "e" //} //}var_dump($map->xor($newMap)); // object(Ds\Map)#8 (3) { //[0]=> //object(Ds\Pair)#7 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //[1]=> //object(Ds\Pair)#6 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[2]=> //object(Ds\Pair)#10 (2) { //["key"]=> //string(1) "e" //["value"]=> //string(1) "e" //} //}var_dump($map->intersect($newMap)); // object(Ds\Map)#8 (2) { //[0]=> //object(Ds\Pair)#10 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "4" //} //[1]=> //object(Ds\Pair)#6 (2) { //["key"]=> //string(1) "a" //["value"]=> //int(1) //} //}$map->putAll($newMap); var_dump($map); // object(Ds\Map)#5 (5) { //[0]=> //object(Ds\Pair)#8 (2) { //["key"]=> //int(5) //["value"]=> //int(3) //} //[1]=> //object(Ds\Pair)#6 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "b" //} //[2]=> //object(Ds\Pair)#10 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //[3]=> //object(Ds\Pair)#7 (2) { //["key"]=> //string(1) "a" //["value"]=> //string(1) "a" //} //[4]=> //object(Ds\Pair)#12 (2) { //["key"]=> //string(1) "e" //["value"]=> //string(1) "e" //} //}var_dump($map->slice(1, 2)); // object(Ds\Map)#12 (2) { //[0]=> //object(Ds\Pair)#7 (2) { //["key"]=> //string(1) "b" //["value"]=> //string(1) "b" //} //[1]=> //object(Ds\Pair)#10 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //} //}var_dump($map->skip(2)); // object(Ds\Pair)#12 (2) { //["key"]=> //int(0) //["value"]=> //int(2) //}

代码内容很多，展示的注释内容也就是我们执行的结果。可以看出，Map 这个数据结构提供的方法功能真的是非常丰富的。而且我们这里还没有完全展示出来，它还有一些类似的方法，大家有兴趣的可以自己多多地去探索。不过就像上面说过的，PHP 中的数组实在是太方便了，所以这个 Map 的应用场景有限，或者某些特殊的必须需要对象来表示数组结构的场景会有用。
总结是不是有点意思呀，就像在开头时我们说过的，了解学习可以，但如果真实业务中只是需要一些简单的栈或队列的实现的话，直接使用 SPL 扩展库中的数据结构就可以了。当然，DS 中的内容还没有讲完，Vector 和 Set 相信学习过 Java 的同学一定不陌生，下篇文章我们将继续学习 DS 中剩余的数据结构。
测试代码：
https://github.com/zhangyue0503/dev-blog/blob/master/php/2021/02/source/2.一起学习PHP中的DS数据结构扩展（一）.php
参考文档：
https://www.php.net/manual/zh/book.ds.php