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