:数据结构线性表之队列

✏一.队列的定义

和栈相反，队列是一种先进先出(FIFO)的线性表。只允许在表的一端进行插入，在另一端进行删除。就像我们日常排队一样。在队列中，允许插入的一端叫队头，删除的一端叫队尾。

✏二.队列的顺序表示

队列也可以用顺序结构和链式结构来表示，用顺序结构实现的叫做顺序队列，常用的数组表示队列。链式结构实现的叫链式队列，比如链表。下面我用PHP实现了简单的顺序队列。

class Queue1{
    private $size;
    private $head=0;
    private $back=0;
    private $data=[];
    public function __construct($size=5)
{
        $this->size=$size;
    }

    /**
     * 入队
     * @param $val
     * @return bool
     */
    public function goqueue($val)
{
        if($this->back==$this->size){  //队列满了
            return false;
        }
        array_push($this->data,$val);
        ++$this->back;
        return true;
    }

    /**
     * 出队
     * @param $val
     * @return bool
     */
    public function outqueue()
{
        if($this->head==$this->back){
            return false;
        }
        array_shift($this->data);
        ++$this->head;
        return true;
    }

    public function queueValue()
{
        return $this->data;
    }

}

//$queue=new Queue1(5);
//$queue->goqueue(2);
//$queue->goqueue(8);
//$queue->goqueue(3);
//$queue->goqueue(1);
//$queue->outqueue();
//$queue->outqueue();
//$queue->goqueue(20);
//$queue->outqueue();
//var_dump($queue->queueValue());
//echo '
';
//var_dump($queue);exit;

如上所示，定义了一个数组来存储队列，定义了当前队列的大小，以及两个指针分别指向队头和队尾。队列为空时队头指向队尾，当我们向队列推数据时，队尾加1，当我们从队列移出数据时，队头+1。你会发现，随着不断的入队出队，队头和队尾指针也不断的向右移动，当队尾指针到达移动到我们定义队列长度的最右端时，此时数据不能再入队，即使当前队列还有空闲的空间。

这个时候我们需要进行数据搬迁，我们不需要在出队的时候进行数据搬迁而是在数据入队的时候进行搬迁。那搬迁的依据是什么呢？还是上面那张图，首先判断条件就是当前队尾是否已经等于队列的长度了，如果是说明此时已经不能再插入数据了，但是我们并不知道是否真的队列满了，在判断队头是否等于0，如果队头等于0的话说明队列是真的满了，否则就像上图所示，0和1这两个位置是空闲的空间，我们可以把front到rear的数组搬移到0到rear-front的位置。然后再重新设置头指针是0，尾指针是rear-front.下面是我把之前入队的代码做了一些整改。这是一段伪代码

 if($this->back==$this->size){
            if($this->head==0){
                return false;
            }
            for($i=$this->head;$i<$this->back;$i++){
                $this->data[$i-$this->head]=$this->data[$i];
            }
            $this->back -=$this->head;
            $this->head=0;

        }
        $this->data[$this->back]=$val;
        ++$this->back;

✏三.队列的链式表示

链式队列也分别用头指针和尾指针来表示头结点和尾结点。当入队时，只要把当前尾结点当next指针指向插入的新结点，然后把当前尾结点的next结点赋值给当前尾结点。出队列的时候，只要把头指针的next结点指向它的->next->next结点即可。下面是简单的用PHP实现。

class queueList{
    public $data;
    public $next;
    public function __construct($data)
{
        $this->data=$data;
        $this->next=null;
    }

}

class showList{
    private $head;
    private $tail;
    public function __construct($head)
{
        $this->head=new queueList($head);
        $this->tail=$this->head;
    }

    /**
     * @param $val
     */
    public function goList($val)
{

        $newList=new queueList($val);
        $this->tail->next=$newList;
        $this->tail=$this->tail->next;
     }

    /**
     * @return queueList
     */
    public function outList()
    {
        if(empty($this->head->next)){
            $this->head=$this->tail;
        }
        $this->head->next=$this->head->next->next;
        return true;
    }
    
    public function head()
{
        return $this->head;
    }
}

$show=new showList('head');
$show->goList(3);
$show->goList(4);
$show->goList(7);
$show->goList(9);
$show->goList(10);
$show->outList();

$show->outList();
$show->outList();
$show->goList(50);
echo "
";
var_dump($show->head());

✏四.循环队列

之前我们使用顺序队列存储数据的时候，会出现数据搬迁，这样队列的入队操作就会受影响，这时候循环队列就出现了。之前的数组实现的队列是有头尾的一条直线，但是循环队列是一个环。

此时队空的判断依然是front=rear，但是我们浪费一个位置不存储数据当(rear+1)%MAXQSIZE ==front,代表着队满的状态。

转载链接：https://leetcode.cn/