php 양방향 큐 클래스

deque(double-ended queue)는 큐와 스택의 성질을 가진 데이터 구조다.양방향 큐의 요소는 양쪽 끝에서 꺼낼 수 있으며, 삽입 및 삭제 작업은 표의 양쪽 끝에서 이루어진다.



실제 사용 시, 출력 제한적인 양방향 큐와 입력 제한적인 양방향 큐를 사용할 수 있습니다. 즉, 다른 쪽 끝점은 삽입 및 삭제 허용하고, 다른 쪽 끝점은 삽입 및 삭제 허용하도록 하는 입력 제한 양방향 큐(즉, 다른 쪽 끝점은 삽입 및 삭제 허용)도 있습니다.삭제된 양방향 큐).만약 양방향 큐가 어떤 끝점에서만 삽입되는 요소를 제거하도록 제한한다면, 양방향 큐는 두 개의 스택 아래에 인접한 스택으로 바뀝니다.

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('a'); // 선두가 열로 들어가다
$obj->rearAdd('b');  // 백엔드가 열로 입력됨
$obj->frontAdd('c'); // 선두가 열로 들어가다
$obj->rearAdd('d');  // 백엔드가 열로 입력됨
 
// 배열은 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('a');
$insert[] = $obj->rearAdd('b');
$insert[] = $obj->frontAdd('c'); // 프론트 엔드는 출력만 가능하므로 여기서는 false가 반환됩니다
$insert[] = $obj->rearAdd('d');
$insert[] = $obj->rearAdd('e');
$insert[] = $obj->rearAdd('f');
$insert[] = $obj->rearAdd('g'); // 길이 초과, 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();  // 출력이 입력에 의존하기 때문에 이것은 NULL을 반환합니다
$result[] = $obj->frontRemove();
$result[] = $obj->frontRemove();
$result[] = $obj->frontRemove();
 
var_dump($result);
 
?>