在之前学习 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\<Obj\> 就是一个数据汇合，而 Map\<Obj\> 就是一个 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"// }// }在 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