什么是隊(duì)列

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

常見操作

• enqueue -> 入隊(duì)
• dequeue -> 出隊(duì)
• peek -> 返回隊(duì)列前端元素
• isEmpty -> 是否為空

PHP實(shí)現(xiàn)

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

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

來看基于數(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)，我們輕而易舉的寫出來了隊(duì)列的基本操作方法五督。果然世界上最好的語言名不虛傳藏否。

可能機(jī)智的同學(xué)已經(jīng)猜到了，我之前已經(jīng)定義了一個(gè)隊(duì)列接口充包，那隊(duì)列的實(shí)現(xiàn)肯定不止只有上面一種哈。來看基于鏈表的實(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é)可以去這里看看。

Spl中的隊(duì)列

強(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ì)列

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

順序序列

優(yōu)先隊(duì)列可以分為有序優(yōu)先隊(duì)列和無序優(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í)別然后插入到合適的位置珍手。

無序序列

在無序序列中，在插入新節(jié)點(diǎn)的時(shí)候我們不需要根據(jù)他們的優(yōu)先級(jí)確定位置辞做。入隊(duì)的時(shí)候像普通隊(duì)列一樣琳要，插入到隊(duì)列的末尾。但是當(dāng)我們想移除優(yōu)先級(jí)最高的元素的時(shí)候秤茅，我們要掃描每一個(gè)節(jié)點(diǎn)來確定移除優(yōu)先級(jí)最高的那一個(gè)稚补。接下來我們還是基于鏈表實(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;
    }
}

環(huán)形隊(duì)列

為充分利用向量空間框喳，克服"假溢出"現(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;

    }
}

雙端隊(duì)列

截止目前我們所實(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 \DataStructure\LinkedList\LinkedList();
    }

    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é)可以去這里看看巡李。

總結(jié)

棧和隊(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ù)雜問題簡單化的常用思路辐宾。

專題系列

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