本文實(shí)例講述了php實(shí)現(xiàn)的雙向隊(duì)列類及其用法，對(duì)于php數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)有不錯(cuò)的參考價(jià)值。分享給大家供大家參考。具體分析如下：

（deque，全名double-ended queue）是一種具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。雙向隊(duì)列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進(jìn)行。

在實(shí)際使用中，還可以有輸出受限的雙向隊(duì)列（即一個(gè)端點(diǎn)允許插入和刪除，另一個(gè)端點(diǎn)只允許插入的雙向隊(duì)列）和輸入受限的雙向隊(duì)列（即一個(gè)端點(diǎn)允許插入和刪除，另一個(gè)端點(diǎn)只允許刪除的雙向隊(duì)列）。而如果限定雙向隊(duì)列從某個(gè)端點(diǎn)插入的元素只能從該端點(diǎn)刪除，則該雙向隊(duì)列就蛻變?yōu)閮蓚€(gè)棧底相鄰的棧了。

DEQue.class.php類文件如下：

<?php /** php 雙向隊(duì)列。支持限定隊(duì)列長(zhǎng)度，輸入受限，輸出受限，及輸出必須與輸入同端幾種設(shè)置 *  Date:  2014-04-30 *  Author: fdipzone *  Ver:  1.0 * *  Func: *  public frontAdd   前端入列 *  public frontRemove 前端出列 *  public rearAdd   后端入列 *  pulbic rearRemove  后端出列 *  public clear    清空對(duì)列 *  public isFull    判斷對(duì)列是否已滿 *  private getLength  獲取對(duì)列長(zhǎng)度 *  private setAddNum  記錄入列,輸出依賴輸入時(shí)調(diào)用 *  private setRemoveNum 記錄出列,輸出依賴輸入時(shí)調(diào)用 *  private checkRemove 檢查是否輸出依賴輸入 */  class DEQue{ // class start    private $_queue = array(); // 對(duì)列   private $_maxLength = 0;  // 對(duì)列最大長(zhǎng)度，0表示不限   private $_type = 0;    // 對(duì)列類型   private $_frontNum = 0;  // 前端插入的數(shù)量   private $_rearNum = 0;   // 后端插入的數(shù)量     /** 初始化   * @param $type    對(duì)列類型   *          1:兩端均可輸入輸出   *          2:前端只能輸入，后端可輸入輸出   *          3:前端只能輸出，后端可輸入輸出   *          4:后端只能輸入，前端可輸入輸出   *          5:后端只能輸出，前端可輸入輸出   *          6:兩端均可輸入輸出，在哪端輸入只能從哪端輸出   * @param $maxlength 對(duì)列最大長(zhǎng)度   */   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 數(shù)據(jù)   * @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 數(shù)據(jù)   * @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;   }    /** 清空對(duì)列   * @return boolean   */   public function clear(){     $this->_queue = array();     $this->_frontNum = 0;     $this->_rearNum = 0;     return true;   }    /** 判斷對(duì)列是否已滿   * @return boolean   */   public function isFull(){     $bIsFull = false;     if($this->_maxLength!=0 && $this->_maxLength==$this->getLength()){       $bIsFull = true;     }     return $bIsFull;   }    /** 獲取當(dāng)前對(duì)列長(zhǎng)度   * @return int   */   private function getLength(){     return count($this->_queue);   }    /** 記錄入列,輸出依賴輸入時(shí)調(diào)用   * @param int $endpoint 端點(diǎn) 1:front 2:rear   */   private function setAddNum($endpoint){     if($this->_type==6){       if($endpoint==1){         $this->_frontNum ++;       }else{         $this->_rearNum ++;       }     }   }    /** 記錄出列,輸出依賴輸入時(shí)調(diào)用   * @param int $endpoint 端點(diǎn) 1:front 2:rear   */   private function setRemoveNum($endpoint){     if($this->_type==6){       if($endpoint==1){         $this->_frontNum --;       }else{         $this->_rearNum --;       }     }   }    /** 檢查是否輸出依賴輸入   * @param int $endpoint 端點(diǎn) 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(); // 前后端都可以輸入，無(wú)限長(zhǎng)度  $obj->frontAdd('a'); // 前端入列 $obj->rearAdd('b'); // 后端入列 $obj->frontAdd('c'); // 前端入列 $obj->rearAdd('d'); // 后端入列  // 入列后數(shù)組應(yīng)為 cabd  $result = array();  $result[] = $obj->rearRemove(); // 后端出列 $result[] = $obj->rearRemove(); // 后端出列 $result[] = $obj->frontRemove(); // 前端出列 $result[] = $obj->frontRemove(); // 前端出列  print_r($result); // 出列順序應(yīng)為 dbca  // 例子2 $obj = new DEQue(3, 5); // 前端只能輸出，后端可輸入輸出，最大長(zhǎng)度5  $insert = array(); $insert[] = $obj->rearAdd('a'); $insert[] = $obj->rearAdd('b'); $insert[] = $obj->frontAdd('c'); // 因前端只能輸出，因此這里會(huì)返回false $insert[] = $obj->rearAdd('d'); $insert[] = $obj->rearAdd('e'); $insert[] = $obj->rearAdd('f'); $insert[] = $obj->rearAdd('g'); // 超過(guò)長(zhǎng)度，返回false  var_dump($insert);  // 例子3 $obj = new DEQue(6); // 輸出依賴輸入  $obj->frontAdd('a'); $obj->frontAdd('b'); $obj->frontAdd('c'); $obj->rearAdd('d');  $result = array(); $result[] = $obj->rearRemove(); $result[] = $obj->rearRemove(); // 因?yàn)檩敵鲆蕾囕斎耄@個(gè)會(huì)返回NULL $result[] = $obj->frontRemove(); $result[] = $obj->frontRemove(); $result[] = $obj->frontRemove();  var_dump($result);  ?> 

完整實(shí)例代碼點(diǎn)擊此處本站下載。

希望本文所述對(duì)大家php程序算法設(shè)計(jì)的學(xué)習(xí)有所幫助。

php技術(shù)：php實(shí)現(xiàn)的雙向隊(duì)列類實(shí)例，轉(zhuǎn)載需保留來(lái)源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。