ホームページ >バックエンド開発 >PHPチュートリアル >PHP双方向キュークラスの説明

PHP双方向キュークラスの説明

jacklove
jackloveオリジナル
2018-06-09 13:58:491487ブラウズ

(deque、フルネーム double-ended queue) は、キューとスタックのプロパティを持つデータ構造です。双方向キュー内の要素は両端からポップでき、挿入および削除操作はテーブルの両端に限定されます。

実際の使用では、出力が制限された双方向キュー (つまり、一方のエンドポイントは挿入と削除を許可し、もう一方のエンドポイントは挿入のみを許可します) や入力が制限されたキューも存在する可能性があります。双方向キュー (つまり、一方のエンドポイントでは挿入と削除が許可され、もう一方のエンドポイントでは削除のみが許可される双方向キュー)。また、双方向キューの特定のエンドポイントから挿入された要素が、そのエンドポイントからのみ削除されるように制限されている場合、双方向キューは下部の 2 つの隣接するスタックに変換されます。

#DEQue.class.php

<?php
/** php 双向队列。支持限定队列长度,输入受限,输出受限,及输出必须与输入同端几种设置
*   Date:   2014-04-30
*   Author: fdipzone
*   Ver:    1.0
*
*   Func:
*   public  frontAdd     前端入列
*   public  frontRemove  前端出列
*   public  rearAdd      后端入列
*   pulbic  rearRemove   后端出列
*   public  clear        清空对列
*   public  isFull       判断对列是否已满
*   private getLength    获取对列长度
*   private setAddNum    记录入列,输出依赖输入时调用
*   private setRemoveNum 记录出列,输出依赖输入时调用
*   private checkRemove  检查是否输出依赖输入
*/
class DEQue{ // class start
    private $_queue = array(); // 对列
    private $_maxLength = 0;   // 对列最大长度,0表示不限
    private $_type = 0;        // 对列类型
    private $_frontNum = 0;    // 前端插入的数量
    private $_rearNum = 0;     // 后端插入的数量
    /** 初始化
    * @param $type       对列类型
    *                    1:两端均可输入输出
    *                    2:前端只能输入,后端可输入输出
    *                    3:前端只能输出,后端可输入输出
    *                    4:后端只能输入,前端可输入输出
    *                    5:后端只能输出,前端可输入输出
    *                    6:两端均可输入输出,在哪端输入只能从哪端输出
    * @param $maxlength  对列最大长度
    */
    public function __construct($type=1, $maxlength=0){
        $this->_type = in_array($type, array(1,2,3,4,5,6))? $type : 1;
        $this->_maxLength = intval($maxlength);
    }
    /** 前端入列
    * @param  Mixed   $data 数据
    * @return boolean
    */
    public function frontAdd($data=null){
        if($this->_type==3){ // 前端输入限制
            return false;
        }
        if(isset($data) && !$this->isFull()){
            array_unshift($this->_queue, $data);
            $this->setAddNum(1);
            return true;
        }
        return false;
    }
    /** 前端出列
    * @return Array
    */
    public function frontRemove(){
        if($this->_type==2){ // 前端输出限制
            return null;
        }
        if(!$this->checkRemove(1)){ // 检查是否依赖输入
            return null;
        }
        $data = null;
        if($this->getLength()>0){
            $data = array_shift($this->_queue);
            $this->setRemoveNum(1);
        }
        return $data;
    }
    /** 后端入列
    * @param  Mixed   $data 数据
    * @return boolean
    */
    public function rearAdd($data=null){
        if($this->_type==5){ // 后端输入限制
            return false;
        }
        if(isset($data) && !$this->isFull()){
            array_push($this->_queue, $data);
            $this->setAddNum(2);
            return true;
        }
        return false;
    }
    /** 后端出列
    * @return Array
    */
    public function rearRemove(){
        if($this->_type==4){ // 后端输出限制
            return null;
        }
        if(!$this->checkRemove(2)){ // 检查是否依赖输入
            return null;
        }
        $data = null;
        if($this->getLength()>0){
            $data = array_pop($this->_queue);
            $this->setRemoveNum(2);
        }
        return $data;
    }
    /** 清空对列
    * @return boolean
    */
    public function clear(){
        $this->_queue = array();
        $this->_frontNum = 0;
        $this->_rearNum = 0;
        return true;
    }
    /** 判断对列是否已满
    * @return boolean
    */
    public function isFull(){
        $bIsFull = false;
        if($this->_maxLength!=0 && $this->_maxLength==$this->getLength()){
            $bIsFull = true;
        }
        return $bIsFull;
    }
    /** 获取当前对列长度
    * @return int
    */
    private function getLength(){
        return count($this->_queue);
    }
    /** 记录入列,输出依赖输入时调用
    * @param int $endpoint 端点 1:front 2:rear
    */
    private function setAddNum($endpoint){
        if($this->_type==6){
            if($endpoint==1){
                $this->_frontNum ++;
            }else{
                $this->_rearNum ++;
            }
        }
    }
    /** 记录出列,输出依赖输入时调用
    * @param int $endpoint 端点 1:front 2:rear
    */
    private function setRemoveNum($endpoint){
        if($this->_type==6){
            if($endpoint==1){
                $this->_frontNum --;
            }else{
                $this->_rearNum --;
            }
        }
    }
    /** 检查是否输出依赖输入
    * @param int $endpoint 端点 1:front 2:rear
    */
    private function checkRemove($endpoint){
        if($this->_type==6){
            if($endpoint==1){
                return $this->_frontNum>0;
            }else{
                return $this->_rearNum>0;
            }
        }
        return true;
    }
} // class end
?>

#demo.php

<?php
require "DEQue.class.php";
// 例子1
$obj = new DEQue(); // 前后端都可以输入,无限长度
$obj->frontAdd(&#39;a&#39;); // 前端入列
$obj->rearAdd(&#39;b&#39;);  // 后端入列
$obj->frontAdd(&#39;c&#39;); // 前端入列
$obj->rearAdd(&#39;d&#39;);  // 后端入列
// 入列后数组应为 cabd
$result = array();
$result[] = $obj->rearRemove(); // 后端出列
$result[] = $obj->rearRemove(); // 后端出列
$result[] = $obj->frontRemove(); // 前端出列
$result[] = $obj->frontRemove(); // 前端出列
print_r($result); // 出列顺序应为 dbca
// 例子2
$obj = new DEQue(3, 5); // 前端只能输出,后端可输入输出,最大长度5
$insert = array();
$insert[] = $obj->rearAdd(&#39;a&#39;);
$insert[] = $obj->rearAdd(&#39;b&#39;);
$insert[] = $obj->frontAdd(&#39;c&#39;); // 因前端只能输出,因此这里会返回false
$insert[] = $obj->rearAdd(&#39;d&#39;);
$insert[] = $obj->rearAdd(&#39;e&#39;);
$insert[] = $obj->rearAdd(&#39;f&#39;);
$insert[] = $obj->rearAdd(&#39;g&#39;); // 超过长度,返回false
var_dump($insert);
// 例子3
$obj = new DEQue(6); // 输出依赖输入
$obj->frontAdd(&#39;a&#39;);
$obj->frontAdd(&#39;b&#39;);
$obj->frontAdd(&#39;c&#39;);
$obj->rearAdd(&#39;d&#39;);
$result = array();
$result[] = $obj->rearRemove();
$result[] = $obj->rearRemove();  // 因为输出依赖输入,这个会返回NULL
$result[] = $obj->frontRemove();
$result[] = $obj->frontRemove();
$result[] = $obj->frontRemove();
var_dump($result);
?>
この記事では、PHP 双方向キュー クラスについて説明します。関連コンテンツの詳細については、PHP 中国語 Web サイトを参照してください。

関連する推奨事項:

php heredoc と nowdoc の違いと特徴

HTML5 localStorage と sessionStorage の違いについて


#php zip ファイルの内容比較クラスの説明


以上がPHP双方向キュークラスの説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。