一起學(xué)習(xí)PHP中的DS數(shù)據(jù)結(jié)構(gòu)擴(kuò)展（一）
在之前學(xué)習(xí) SPL 相關(guān)的文章中，我們已經(jīng)學(xué)習(xí)過(guò) SPL 中的一些數(shù)據(jù)結(jié)構(gòu)相關(guān)的數(shù)據(jù)結(jié)構(gòu)對(duì)象，非常強(qiáng)大也非常好用，最主要的是 SPL 已經(jīng)集成在 PHP 源碼中不需要我們?cè)賳为?dú)地安裝別的什么擴(kuò)展。但是，今天我們要學(xué)習(xí)的這個(gè) DataStruct 擴(kuò)展庫(kù)的內(nèi)容則更加地豐富，不過(guò)相對(duì)應(yīng)的，這套擴(kuò)展是需要我們自己手動(dòng)再進(jìn)行安裝的。如果大家對(duì)于數(shù)據(jù)結(jié)構(gòu)的需求不高的話，使用 SPL 中的相關(guān)對(duì)象就夠用了，但是如果需要更加豐富的數(shù)據(jù)結(jié)構(gòu)類型的話，這套 DS 擴(kuò)展是更好的選擇。
DS 擴(kuò)展的安裝和其它普通的擴(kuò)展安裝沒(méi)有什么區(qū)別，也不需要額外的操作系統(tǒng)上的組件支持，直接安裝即可。
棧
首先還是從棧這個(gè)最基本的數(shù)據(jù)結(jié)構(gòu)說(shuō)起。DS 中的棧結(jié)構(gòu)非常地簡(jiǎn)單好用。
$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)
// }
兩種方式實(shí)例化棧對(duì)象，其實(shí)就是參數(shù)的不同，如果我們直接給構(gòu)造函數(shù)傳遞一個(gè)數(shù)組的話，那么這個(gè)數(shù)組就會(huì)做為棧內(nèi)部的元素供我們使用。
$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() 就是將數(shù)據(jù)壓棧，pop() 則是將棧頂?shù)脑貜棾觥ｊP(guān)于棧的最主要的操作其實(shí)就是這兩個(gè)方法函數(shù)了。
var_dump($stack->peek()); // int(3)
// object(Ds\Stack)#2 (3) {
// [0]=>
// int(3)
// [1]=>
// int(2)
// [2]=>
// int(1)
// }
peek() 這個(gè)函數(shù)是直接獲取棧頂?shù)臄?shù)據(jù)，但是需要注意的是，它不會(huì)彈出棧頂?shù)脑?。也就是說(shuō)，這個(gè) peek() 方法只會(huì)取得數(shù)據(jù)的內(nèi)容，不會(huì)改變棧內(nèi)部的數(shù)據(jù)。
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() 返回棧內(nèi)部元素的數(shù)量，isEmpty() 用于判斷棧是否為空，toArray() 直接以數(shù)組的格式返回棧內(nèi)部的數(shù)據(jù)，clear() 方法用于清空棧。這些方法函數(shù)都非常地簡(jiǎn)單，所以就不多做解釋了。最后我們來(lái)看看棧對(duì)象的賦值拷貝操作。
$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 對(duì)象是實(shí)例化之后的對(duì)象，在普通的賦值操作中是引用傳遞的。上文中我們清空了 $stack ，然后在這里我們讓 $a 等于這個(gè) $stack ，然后操作 $a 相應(yīng)地 $stack 里面的內(nèi)容也發(fā)生了變化。對(duì)于引用傳遞這個(gè)問(wèn)題，我們一般會(huì)使用 __clone() 魔術(shù)方法來(lái)解決， Stack 類直接就為我們提供了一個(gè) copy() 方法，直接可以獲得一個(gè)棧對(duì)象的拷貝，也可以說(shuō)是一個(gè)新的棧對(duì)象。就像上面代碼中的 $b 一樣，當(dāng)使用 copy() 方法賦值給 $b 之后，它就成為了一個(gè)新的棧對(duì)象，任何 $b 的操作和 $stack 對(duì)象就沒(méi)有什么關(guān)系了。我們可以看到 對(duì)象id 也完全不同了。
隊(duì)列
對(duì)于隊(duì)列來(lái)說(shuō)，整體上的功能方法和棧的內(nèi)容差不多，它們實(shí)現(xiàn)的方法基本上是一模一樣的。具體在實(shí)現(xiàn)層面上的不同就體現(xiàn)在彈棧和出隊(duì)的不同，也就是 push() 方法在實(shí)現(xiàn)中有差別。
$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)
// }
可以看出，在隊(duì)列中，我們 push() 進(jìn)來(lái)的數(shù)據(jù)的順序是 1,2,3,4,5 這樣正序的，也就是將數(shù)據(jù)放到內(nèi)部這個(gè)數(shù)組的底部，出隊(duì) pop() 直接拿最頂上的數(shù)據(jù)也就實(shí)現(xiàn)了先進(jìn)先出的效果。對(duì)比上面棧的數(shù)據(jù)內(nèi)容，就可以發(fā)現(xiàn)棧的數(shù)據(jù)在 push() 的時(shí)候就是反過(guò)來(lái)的，5、4、3、2、1 這樣的，然后在 pop() 的時(shí)候其實(shí)也是從頂部拿出數(shù)據(jù)，只不過(guò)棧是將數(shù)據(jù) push() 到內(nèi)部數(shù)組的頂部的，然后從頂部直接拿出數(shù)據(jù)實(shí)現(xiàn)了 后進(jìn)先出 的效果。
優(yōu)先隊(duì)列
最重要的兩個(gè)數(shù)據(jù)結(jié)構(gòu)說(shuō)完了，我們?cè)賮?lái)看一個(gè)隊(duì)列的擴(kuò)展結(jié)構(gòu)，也就是優(yōu)先隊(duì)列的實(shí)現(xiàn)。其實(shí)這個(gè)隊(duì)列就是在 push() 數(shù)據(jù)的時(shí)候多了一個(gè)參數(shù)，也就是數(shù)據(jù)的優(yōu)先級(jí)，越大的越靠前，其它的方法和普通隊(duì)列以及棧的方法都沒(méi)什么太大的區(qū)別。
$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
最后我們來(lái)學(xué)習(xí)一個(gè) Map 數(shù)據(jù)結(jié)構(gòu)，其實(shí)也就是 HaspMap 這種 K/V 的鍵值對(duì)形式的數(shù)據(jù)結(jié)構(gòu)。只能說(shuō) PHP 中的數(shù)組實(shí)在是太強(qiáng)大了，完全兼容了這種數(shù)據(jù)結(jié)構(gòu)，所以使得單獨(dú)的 Map 結(jié)構(gòu)并沒(méi)有什么實(shí)際的意義。
$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 之類的語(yǔ)言中，數(shù)組 和 HashMap 是兩種東西，或者說(shuō)是兩種集合對(duì)象，比如 List<Obj> 就是一個(gè)數(shù)據(jù)集合，而 Map<Obj> 就是一個(gè) HashMap 集合。相對(duì)應(yīng)的，在 Java 的這種泛型集合中，我們需要添加和獲取數(shù)據(jù)就要像這個(gè) DS 擴(kuò)展中的 Map 一樣使用 get()、put()、remove() 類似的方法來(lái)實(shí)現(xiàn)。
Map 這個(gè)數(shù)據(jù)結(jié)構(gòu)與上面的棧、隊(duì)列之類的數(shù)據(jù)結(jié)構(gòu)中實(shí)現(xiàn)的方法差別還是挺大的。
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() 方法直接獲取第一個(gè)和最后一個(gè)數(shù)據(jù)元素。也有 sum() 方法獲得數(shù)據(jù)元素的個(gè)數(shù)，同時(shí)可以通過(guò) hasKey() 和 hasValue() 來(lái)判斷指定的鍵或者值是存在。是不是有點(diǎn)像 key_exists() 和 in_array() 這兩個(gè)方法。當(dāng)然，相對(duì)應(yīng)的我們也可以直接獲取這些 Key 和 Value 的內(nèi)容。
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() 返回的內(nèi)容是 Set 類型的對(duì)象，而 values() 返回的內(nèi)容是 Vector 類型的對(duì)象，這兩種也是 DS 中的數(shù)據(jù)結(jié)構(gòu)類型，我們將在下篇文章中再學(xué)習(xí)。除了 Key 和 Values 之外，它還可以直接返回一個(gè) Vector 類型的對(duì)象集合結(jié)構(gòu)，使用 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 對(duì)象中，還提供了一些為數(shù)據(jù)排序、合并兩個(gè) Map 以及截取一部分?jǐn)?shù)據(jù)的方法，直接貼出代碼吧。
$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)
// }
代碼內(nèi)容很多，展示的注釋內(nèi)容也就是我們執(zhí)行的結(jié)果?？梢钥闯?，Map 這個(gè)數(shù)據(jù)結(jié)構(gòu)提供的方法功能真的是非常豐富的。而且我們這里還沒(méi)有完全展示出來(lái)，它還有一些類似的方法，大家有興趣的可以自己多多地去探索。不過(guò)就像上面說(shuō)過(guò)的，PHP 中的數(shù)組實(shí)在是太方便了，所以這個(gè) Map 的應(yīng)用場(chǎng)景有限，或者某些特殊的必須需要對(duì)象來(lái)表示數(shù)組結(jié)構(gòu)的場(chǎng)景會(huì)有用。
總結(jié)
是不是有點(diǎn)意思呀，就像在開(kāi)頭時(shí)我們說(shuō)過(guò)的，了解學(xué)習(xí)可以，但如果真實(shí)業(yè)務(wù)中只是需要一些簡(jiǎn)單的?；蜿?duì)列的實(shí)現(xiàn)的話，直接使用 SPL 擴(kuò)展庫(kù)中的數(shù)據(jù)結(jié)構(gòu)就可以了。當(dāng)然，DS 中的內(nèi)容還沒(méi)有講完，Vector 和 Set 相信學(xué)習(xí)過(guò) Java 的同學(xué)一定不陌生，下篇文章我們將繼續(xù)學(xué)習(xí) DS 中剩余的數(shù)據(jù)結(jié)構(gòu)。
測(cè)試代碼：
https://github.com/zhangyue0503/dev-blog/blob/master/php/2021/02/source/2.一起學(xué)習(xí)PHP中的DS數(shù)據(jù)結(jié)構(gòu)擴(kuò)展（一）.php
參考文檔：
https://www./manual/zh/book.ds.php
