摘要：環(huán)形隊(duì)列為充分利用向量空間，克服假溢出現(xiàn)象的方法是將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。雙端隊(duì)列截止目前我們所實(shí)現(xiàn)的隊(duì)列都是在隊(duì)尾入隊(duì)，隊(duì)首出隊(duì)的結(jié)構(gòu)。

隊(duì)列是另外一種遵循先進(jìn)先出原則的線性數(shù)據(jù)結(jié)構(gòu)。隊(duì)列有兩端可供操作，一端出隊(duì)，一端入隊(duì)。這個(gè)特點(diǎn)和棧不同，棧只有一端可以用來(lái)操作。入隊(duì)總是在后端，出隊(duì)在前端。

enqueue -> 入隊(duì)

dequeue -> 出隊(duì)

peek -> 返回隊(duì)列前端元素

isEmpty -> 是否為空

首先我們定義一個(gè)QueueInterface。

interface QueueInterface
{
    public function enqueue(string $item);
    public function dequeue();
    public function isEmpty();
    public function peek();
}

來(lái)看基于數(shù)組的隊(duì)列實(shí)現(xiàn)

class ArrQueue implements QueueInterface
{
    private $queue;
    private $limit;

    public function __construct(int $limit = 0)
    {
       $this->limit = $limit;
       $this->queue = [];
    }

    public function isEmpty()
    {
        return empty($this->queue);
    }

    public function dequeue()
    {
        if ($this->isEmpty()) {
            throw new UnderflowException("queue is empty");
        } else {
            array_shift($this->queue);
        }
    }

    public function enqueue(string $item)
    {
        if (count($this->queue) >= $this->limit) {
            throw new OverflowException("queue is full");
        } else {
            array_unshift($this->queue, $item);
        }
    }

    public function peek()
    {
        return current($this->queue);
    }
}

得益于PHP強(qiáng)大的array結(jié)構(gòu)，我們輕而易舉的寫(xiě)出來(lái)了隊(duì)列的基本操作方法。果然世界上最好的語(yǔ)言名不虛傳。

可能機(jī)智的同學(xué)已經(jīng)猜到了，我之前已經(jīng)定義了一個(gè)隊(duì)列接口，那隊(duì)列的實(shí)現(xiàn)肯定不止只有上面一種哈。來(lái)看基于鏈表的實(shí)現(xiàn)。

class LinkedListQueue implements QueueInterface
{
    private $limit;
    private $queue;

    public function __construct(int $limit = 0)
    {
        $this->limit = $limit;
        $this->queue = new LinkedList();
    }

    public function isEmpty()
    {
        return $this->queue->getSize() == 0;
    }

    public function peek()
    {
        return $this->queue->getNthNode(0)->data;
    }

    public function enqueue(string $item)
    {
        if ($this->queue->getSize() < $this->limit) {
            $this->queue->insert($item);
        } else {
            throw new OverflowException("queue is full");
        }
    }

    public function dequeue()
    {
        if ($this->isEmpty()) {
            throw new UnderflowException("queue is empty");
        } else {
            $lastItem = $this->peek();
            $this->queue->deleteFirst();

            return $lastItem;
        }
    }
}

里面涉及到了之前的鏈表實(shí)現(xiàn)，不了解細(xì)節(jié)的同學(xué)可以去這里看看。

強(qiáng)大的PHP已經(jīng)內(nèi)置了隊(duì)列實(shí)現(xiàn)，可以使用的方法和上面我們自己實(shí)現(xiàn)的類似。

class SqlQueue
{
    private $splQueue;

    public function __construct()
    {
        $this->splQueue = new SplQueue();
    }

    public function enqueue(string $data = null)
    {
        $this->splQueue->enqueue($data);
    }

    public function dequeue()
    {
        return $this->splQueue->dequeue();
    }
}

優(yōu)先隊(duì)列是一種特殊的隊(duì)列，入隊(duì)或者出隊(duì)的順序都是基于每個(gè)節(jié)點(diǎn)的權(quán)重。

順序序列

優(yōu)先隊(duì)列可以分為有序優(yōu)先隊(duì)列和無(wú)序優(yōu)先隊(duì)列。有序優(yōu)先隊(duì)列又有兩種情況，倒序或者順序。在順序序列中，我們可以迅速的找出最大或者最小優(yōu)先級(jí)別的節(jié)點(diǎn)，復(fù)雜度是O(1)。但是插入的話會(huì)花費(fèi)掉更多的時(shí)間，因?yàn)槲覀円獧z查每一個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)別然后插入到合適的位置。

無(wú)序序列

在無(wú)序序列中，在插入新節(jié)點(diǎn)的時(shí)候我們不需要根據(jù)他們的優(yōu)先級(jí)確定位置。入隊(duì)的時(shí)候像普通隊(duì)列一樣，插入到隊(duì)列的末尾。但是當(dāng)我們想移除優(yōu)先級(jí)最高的元素的時(shí)候，我們要掃描每一個(gè)節(jié)點(diǎn)來(lái)確定移除優(yōu)先級(jí)最高的那一個(gè)。接下來(lái)我們還是基于鏈表實(shí)現(xiàn)一個(gè)順序的優(yōu)先隊(duì)列。

class LinkedListPriorityQueue
{
    private $limit;
    private $queue;


    public function __construct(int $limit = 0)
    {
        $this->limit = $limit;
        $this->queue = new LinkedList();
    }

    public function enqueue(string $data = null, int $priority)
    {
        if ($this->queue->getSize() > $this->limit) {
            throw new OverflowException("Queue is full");
        } else {
            $this->queue->insert($data, $priority);
        }
    }

    public function dequeue(): string
    {
        if ($this->isEmpty()) {
            throw new UnderflowException("Queue is empty");
        } else {
            $item = $this->peek();
            $this->queue->deleteFirst();

            return $item->data;
        }
    }

    public function peek()
    {
        return $this->queue->getNthNode(0);
    }

    public function isEmpty()
    {
        return $this->queue->getSize() === 0;
    }
}

為充分利用向量空間，克服"假溢出"現(xiàn)象的方法是：將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列。環(huán)形隊(duì)列也是一種數(shù)組，只是它在邏輯上把數(shù)組的頭和尾相連，形成循環(huán)隊(duì)列，當(dāng)數(shù)組尾滿的時(shí)候，要判斷數(shù)組頭是否為空，不為空繼續(xù)存放數(shù)據(jù)。

class CircularQueue implements QueueInterface
{
    private $queue;
    private $limit;
    private $front = 0;
    private $rear = 0;

    public function __construct(int $limit = 0)
    {
        $this->limit = $limit;
        $this->queue = [];
    }

    public function isEmpty()
    {
        return $this->front === $this->rear;
    }

    public function isFull()
    {
        $diff = $this->rear - $this->front;

        if ($diff == -1 || $diff == ($this->limit - 1)) {
            return true;
        }

        return false;
    }

    public function peek()
    {
        return $this->queue[$this->front];
    }

    public function dequeue()
    {
        if ($this->isEmpty()) {
            throw new UnderflowException("Queue is empty");
        }

        $item = $this->queue[$this->front];
        $this->queue[$this->front] = null;
        $this->front = ($this->front + 1) % $this->limit;

        return $item;
    }

    public function enqueue(string $item)
    {
        if ($this->isFull()) {
            throw new OverflowException("Queue is full");
        }

        $this->queue[$this->rear] = $item;
        $this->rear = ($this->rear + 1) % $this->limit;

    }
}

截止目前我們所實(shí)現(xiàn)的隊(duì)列都是在隊(duì)尾(rear)入隊(duì)，隊(duì)首(front) 出隊(duì)的結(jié)構(gòu)。在特殊的情況下，我們希望不論是隊(duì)首還是隊(duì)尾都可以入隊(duì)或者出隊(duì)，這種結(jié)構(gòu)就叫做雙端隊(duì)列?；谖覀冎皩?shí)現(xiàn)的鏈表結(jié)構(gòu)，我們可以輕而易舉的實(shí)現(xiàn)這樣的結(jié)構(gòu)。

class LinkedListDeQueue
{
    private $limit = 0;
    private $queue;

    public function __construct(int $limit = 0)
    {
        $this->limit = $limit;
        $this->queue = new DataStructureLinkedListLinkedList();
    }

    public function dequeueFromFront(): string 
    {
        if ($this->isEmpty()) {
            throw new UnderflowException("Queue is empty");
        }

        $item = $this->queue->getNthNode(0);
        $this->queue->deleteFirst();

        return $item->data;
    }

    public function dequeueFromBack(): string 
    {
        if ($this->isEmpty()) {
            throw new UnderflowException("Queue is empty");
        }

        $item = $this->queue->getNthNode($this->queue->getSize() - 1);
        $this->queue->deleteLast();

        return $item->data;
    }

    public function isFull()
    {
        return $this->queue->getSize() >= $this->limit;
    }

    public function enqueueAtBack(string $data = null)
    {
        if ($this->isFull()) {
            throw new OverflowException("queue is full");
        }

        $this->queue->insert($data);
    }

    public function enqueueAtFront(string $data = null)
    {
        if ($this->isFull()) {
            throw new OverflowException("queue is full");
        }

        $this->queue->insertAtFirst($data);
    }

    public function isEmpty()
    {
        return $this->queue->getSize() === 0;
    }

    public function peekFront()
    {
        return $this->queue->getNthNode(0)->data;
    }

    public function peekBack()
    {
        return $this->queue->getNthNode($this->queue->getSize() - 1)->data;
    }
}

里面涉及到了之前的鏈表實(shí)現(xiàn)，不了解細(xì)節(jié)的同學(xué)可以去這里看看。

棧和隊(duì)列是我們最常用的數(shù)據(jù)結(jié)構(gòu)，我們會(huì)在其他的復(fù)雜數(shù)據(jù)結(jié)構(gòu)中看到這兩種抽象數(shù)據(jù)類型的應(yīng)用。在下一章，我們繼續(xù)學(xué)習(xí)PHP數(shù)據(jù)結(jié)構(gòu)之遞歸，這是一種將復(fù)雜問(wèn)題簡(jiǎn)單化的常用思路。

PHP基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址：地址 主要使用PHP語(yǔ)法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。還有我們?nèi)粘HP開(kāi)發(fā)中容易忽略的基礎(chǔ)知識(shí)和現(xiàn)代PHP開(kāi)發(fā)中關(guān)于規(guī)范、部署、優(yōu)化的一些實(shí)戰(zhàn)性建議，同時(shí)還有對(duì)Javascript語(yǔ)言特點(diǎn)的深入研究。