定义

队列，和栈类似，也是一种操作受限的线性表数据结构。与栈结构不同的是，可以对队列 2 端操作，要求数据从一端进（入队），从另一端出（出队）。队列遵循 "先进先出" 的原则，即最先进队列的数据元素，同样要最先出队列。

实现

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

#数组队列
class Queue
{
    private $_head;
    private $_tail;
    private $_queue;
    private $_queueSize;
    public function __construct($size){

        $this->_queue = [];
        $this->_queueSize = $size;
        $this->_head = 0;
        $this->_tail = 0;
    }
    #入队
  public function enQueue( $elem ){
        if (!$this->isFull()) {
            $this->_queue[$this->_tail] = $elem;
            $this->_tail++;  
            return true;
        }
        return false;
    }
    #出队
    public function deQueue(){
        if( !$this->isEmpty() ) {
            $elem = $this->_queue[$this->_head];
            $this->_head ++;
            return $elem;
        }
        return false;
    }
    #队列是否为空
    public function isEmpty() {
        return ( $this->_head == $this->_tail  ? true : false );
        // return   $this->_head == $this->_tail ;
    }
    #队列是否已满
    public function isFull(){
        return ( $this->_tail === $this->_queueSize ? true : false );
    }
}

如上，当不停地入队和出队时，head 和 tail 都会后移。当到达数组最后面时，即使数组前面仍空余，也无法入队操作了。此时，就需要我们对数组进行迁移(只需要到达数组最后面时迁移，不需要每次出队都进行迁移，以此提高效率)。

循环队列

你可能已经发现，如上所示还是需要做迁移的，如果数组很大，迁移消耗也很大的。这种情况下，我们可以从头再开始，也就是头尾相接的循环。我们把队列这种头尾相接的顺序存储节后称为循环队列。

public class CircularQueue { 
    private $items = [] ;  
    private $n = 0;  
    private $head = 0;  
    private $tail = 0;   
    public __construct($size) {   
        $n = $size; 
    } 
    public function  enqueue($item) {    
        if (($tail + 1) % $n == $head) 
            return false;    
        $items[$tail] = $item;   
        $tail = ($tail + 1) % $n;    
        return true;  
    }  
     public function  dequeue() {     
         if ($head == $tail) 
             return false;   
        $ret = $items[$head];    
        $head = ($head + 1) % $n;    
        return $ret;  
    }
}

应用

资源有限的场景都可以队列，例如买车票、秒杀、分布式应用的消息队列。

本作品采用《CC 协议》，转载必须注明作者和本文链接