php的双向队列类

（deque，全名double-ended queue）是一种具有队列和栈的性质的数据结构。双向队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

在实际使用中，还可以有输出受限的双向队列（即一个端点允许插入和删除，另一个端点只允许插入的双向队列）和输入受限的双向队列（即一个端点允许插入和删除，另一个端点只允许删除的双向队列）。而如果限定双向队列从某个端点插入的元素只能从该端点删除，则该双向队列就蜕变为两个栈底相邻的栈了。

DEQue.class.php

查看本栏目更多精彩内容：http://www.bianceng.cn/webkf/PHP/
    *                    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