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

在之前学习 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