关于php:一起学习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 数据结构，其实也就是 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

栈

队列

优先队列

Map

总结