PHP - SplQueue 队列 - 学习/实践

ゞ浴缸里的玫瑰 2022-12-15 02:54 100阅读 0赞

1.应用场景

<table> 
 <tbody> 
 <tr> 
 <td> 主要用于学习PHP扩展库实践队列的功能与用法. 使用PHP语言解决问题，比如算法面试题等. </td> 
 </tr> 
 </tbody> 
</table>

2.学习/操作

<table> 
 <tbody> 
 <tr> 
 <td> 1.文档阅读 <a href="https://blog.csdn.net/wuxing26jiayou/article/details/51887665" rel="nofollow">https://blog.csdn.net/wuxing26jiayou/article/details/51887665</a>&nbsp; //PHP SplQueue 队列简介 <a href="https://www.php.net/manual/zh/class.splqueue.php" rel="nofollow">https://www.php.net/manual/zh/class.splqueue.php</a>&nbsp; //The SplQueue class &nbsp; 2.简介 SplQueue 类通过使用一个双向链表来提供队列的主要功能。 &nbsp; 3.实践 -- 如何使用？ Code： &lt;?php class Test { &nbsp; &nbsp; public static function foo() { &nbsp; &nbsp; &nbsp; &nbsp; echo 'Test::foo() called'.'&lt;br/&gt;'; &nbsp; &nbsp; } &nbsp; &nbsp; public static function bar() { &nbsp; &nbsp; &nbsp; &nbsp; echo 'Test::bar() called'.'&lt;br/&gt;'; &nbsp; &nbsp; } &nbsp; &nbsp; public static function msg($msg) { &nbsp; &nbsp; &nbsp; &nbsp; echo "$msg".'&lt;br/&gt;'; &nbsp; &nbsp; } } &nbsp; $queue = new SplQueue(); $queue-&gt;setIteratorMode(SplQueue::IT_MODE_DELETE); $queue-&gt;enqueue(array("Test", "foo")); $queue-&gt;enqueue(array("Test", "bar")); $queue-&gt;enqueue(array("Test", "msg", "Hi there!")); var_dump($queue); &nbsp; foreach ($queue as $task) { &nbsp; &nbsp; if (count($task) &gt; 2) { &nbsp; &nbsp; &nbsp; &nbsp; list($class, $method, $args) = $task; &nbsp; &nbsp; &nbsp; &nbsp; $class::$method($args); &nbsp; &nbsp; } else { &nbsp; &nbsp; &nbsp; &nbsp; list($class, $method) = $task; &nbsp; &nbsp; &nbsp; &nbsp; $class::$method(); &nbsp; &nbsp; } } &nbsp; 输出： object(SplQueue)#1 (2) { ["flags":"SplDoublyLinkedList":private]=&gt; int(5) ["dllist":"SplDoublyLinkedList":private]=&gt; array(3) { [0]=&gt; array(2) { [0]=&gt; string(4) "Test" [1]=&gt; string(3) "foo" } [1]=&gt; array(2) { [0]=&gt; string(4) "Test" [1]=&gt; string(3) "bar" } [2]=&gt; array(3) { [0]=&gt; string(4) "Test" [1]=&gt; string(3) "msg" [2]=&gt; string(9) "Hi there!" } } } Test::foo() called Test::bar() called Hi there! &nbsp; 4.解答算法面试题 <a href="https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/php-bfsjie-fa-by-lyyw/" rel="nofollow">https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/php-bfsjie-fa-by-lyyw/</a>&nbsp; &nbsp;//自行写PHP code &nbsp; 尚未解决 
 <table> 
 <tbody> 
 <tr> 
 <td> &lt;?php //&nbsp;104.&nbsp;二叉树的最大深度 //&nbsp;给定一个二叉树，找出其最大深度。 &nbsp; //&nbsp;二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 &nbsp; //&nbsp;说明:&nbsp;叶子节点是指没有子节点的节点。 &nbsp; //&nbsp;示例： //&nbsp;给定二叉树&nbsp;[3,9,20,null,null,15,7]， &nbsp; //&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3 //&nbsp;&nbsp;&nbsp;&nbsp;/&nbsp;\ //&nbsp;&nbsp;&nbsp;9&nbsp;&nbsp;20 //&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/&nbsp;&nbsp;\ //&nbsp;&nbsp;&nbsp;&nbsp;15&nbsp;&nbsp;&nbsp;7 //&nbsp;返回它的最大深度&nbsp;3&nbsp;。 &nbsp; /** &nbsp;*&nbsp;Definition&nbsp;for&nbsp;a&nbsp;binary&nbsp;tree&nbsp;node.&nbsp;&nbsp;使用PHP如何实现二叉树结构？&nbsp;TBD&nbsp;//20201014 &nbsp;*&nbsp;class&nbsp;TreeNode&nbsp;{ &nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;$val&nbsp;=&nbsp;null; &nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;$left&nbsp;=&nbsp;null; &nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;$right&nbsp;=&nbsp;null; &nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;function&nbsp;__construct($value)&nbsp;{&nbsp;$this-&gt;val&nbsp;=&nbsp;$value;&nbsp;} &nbsp;*&nbsp;} &nbsp;*/ &nbsp; class&nbsp;Solution&nbsp;{ &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;TreeNode&nbsp;$root &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@return&nbsp;Integer &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;function&nbsp;maxDepth($root)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if($root&nbsp;==&nbsp;null){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$queue&nbsp;=&nbsp;new&nbsp;SplQueue(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$queue-&gt;enqueue($root); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$ans&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(!$queue-&gt;isEmpty()){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(int)&nbsp;$size&nbsp;=&nbsp;$queue-&gt;count(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while($size&nbsp;&gt;&nbsp;0){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$node&nbsp;=&nbsp;$queue-&gt;dequeue(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if($node-&gt;left&nbsp;!=&nbsp;null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$queue-&gt;enqueue($node-&gt;left); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if($node-&gt;right&nbsp;!=&nbsp;null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$queue-&gt;enqueue($node-&gt;right); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$size--; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$ans++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;$ans; &nbsp;&nbsp;&nbsp;&nbsp;} } &nbsp; $root&nbsp;=&nbsp;[3,9,20,null,null,15,7]; $solution&nbsp;=&nbsp;new&nbsp;Solution(); $ret&nbsp;=&nbsp;$solution-&gt;maxDepth($root); var_dump($ret);&nbsp;//&nbsp;int(1)&nbsp;应该是3 &nbsp; //即执行失败~&nbsp;&nbsp;解决问题的关键在于如何使用PHP定义实现二叉树结构&nbsp;？ 参见： <a href="https://blog.csdn.net/william_n/article/details/109106814" rel="nofollow">https://blog.csdn.net/william_n/article/details/109106814</a> &nbsp; 补充： 完整代码 TreeNode.php &lt;?php &nbsp; // 二叉树结点类 class&nbsp;TreeNode{ &nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;$val; //var是public的别名 &nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;$left&nbsp;=&nbsp;NULL; &nbsp;&nbsp;&nbsp;&nbsp;var&nbsp;$right&nbsp;=&nbsp;NULL; &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;function&nbsp;__construct($val){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$this-&gt;val&nbsp;=&nbsp;$val; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;//构造二叉树 &nbsp;&nbsp;&nbsp;&nbsp;function&nbsp;createBinaryTree(TreeNode&nbsp;$lchird&nbsp;=&nbsp;NULL,&nbsp;TreeNode&nbsp;$rchird&nbsp;=&nbsp;NULL){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!is_null($lchird)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$this-&gt;left&nbsp;=&nbsp;$lchird; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(!is_null($rchird)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$this-&gt;right&nbsp;=&nbsp;$rchird; &nbsp;&nbsp;&nbsp;&nbsp;} } &nbsp; ?&gt; &nbsp; getTreeMaxDepth.php &lt;?php require_once&nbsp;'./TreeNode.php'; &nbsp; class&nbsp;Solution&nbsp;{ &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;TreeNode&nbsp;$root &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@return&nbsp;Integer &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;function&nbsp;maxDepth($root)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if($root&nbsp;==&nbsp;null){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$queue&nbsp;=&nbsp;new&nbsp;SplQueue(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$queue-&gt;enqueue($root); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$ans&nbsp;=&nbsp;0; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(!$queue-&gt;isEmpty()){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(int)&nbsp;$size&nbsp;=&nbsp;$queue-&gt;count(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while($size&nbsp;&gt;&nbsp;0){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$node&nbsp;=&nbsp;$queue-&gt;dequeue(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if($node-&gt;left&nbsp;!=&nbsp;null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$queue-&gt;enqueue($node-&gt;left); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if($node-&gt;right&nbsp;!=&nbsp;null) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$queue-&gt;enqueue($node-&gt;right); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$size--; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$ans++; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;$ans; &nbsp;&nbsp;&nbsp;&nbsp;} } &nbsp; $a&nbsp;=&nbsp;new&nbsp;TreeNode(3); $b&nbsp;=&nbsp;new&nbsp;TreeNode(9); $c&nbsp;=&nbsp;new&nbsp;TreeNode(20); $d&nbsp;=&nbsp;new&nbsp;TreeNode(15); $e&nbsp;=&nbsp;new&nbsp;TreeNode(7); &nbsp; $a-&gt;createBinaryTree($b,&nbsp;$c); $b-&gt;createBinaryTree(NULL,&nbsp;NULL); $c-&gt;createBinaryTree($d,&nbsp;$e); &nbsp; $solution&nbsp;=&nbsp;new&nbsp;Solution(); $ret&nbsp;=&nbsp;$solution-&gt;maxDepth($a); var_dump($ret); &nbsp; ?&gt; &nbsp; 输出结果： &nbsp; <img alt="" height="143" src="https://img-blog.csdnimg.cn/20201015230118635.png" width="460"> 正常解决~ </td> 
 </tr> 
 </tbody> 
 </table>&nbsp; &nbsp; 后续补充 ... </td> 
 </tr> 
 </tbody> 
</table>

3.问题/补充

4.参考

<table> 
 <tbody> 
 <tr> 
 <td> <a href="https://blog.csdn.net/wuxing26jiayou/article/details/51887665" rel="nofollow">https://blog.csdn.net/wuxing26jiayou/article/details/51887665</a>&nbsp; //PHP SplQueue 队列简介 <a href="https://www.php.net/manual/zh/class.splqueue.php" rel="nofollow">https://www.php.net/manual/zh/class.splqueue.php</a>&nbsp; //The SplQueue class </td> 
 </tr> 
 </tbody> 
</table>

后续补充

...