實戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之隊列

cnio 發(fā)布于2019-07-01 10:09 / 2044人閱讀

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

什么是隊列

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

常見操作

enqueue -> 入隊

dequeue -> 出隊

peek -> 返回隊列前端元素

isEmpty -> 是否為空

PHP實現(xiàn)

首先我們定義一個QueueInterface。

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

來看基于數(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強大的array結(jié)構(gòu)，我們輕而易舉的寫出來了隊列的基本操作方法。果然世界上最好的語言名不虛傳。

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

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

Spl中的隊列

強大的PHP已經(jīng)內(nèi)置了隊列實現(xiàn)，可以使用的方法和上面我們自己實現(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)先隊列

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

順序序列

優(yōu)先隊列可以分為有序優(yōu)先隊列和無序優(yōu)先隊列。有序優(yōu)先隊列又有兩種情況，倒序或者順序。在順序序列中，我們可以迅速的找出最大或者最小優(yōu)先級別的節(jié)點，復(fù)雜度是O(1)。但是插入的話會花費掉更多的時間，因為我們要檢查每一個節(jié)點的優(yōu)先級別然后插入到合適的位置。

無序序列

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

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)形隊列

為充分利用向量空間，克服"假溢出"現(xiàn)象的方法是：將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量。存儲在其中的隊列稱為循環(huán)隊列。環(huán)形隊列也是一種數(shù)組，只是它在邏輯上把數(shù)組的頭和尾相連，形成循環(huán)隊列，當(dāng)數(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;

    }
}

雙端隊列

截止目前我們所實現(xiàn)的隊列都是在隊尾(rear)入隊，隊首(front) 出隊的結(jié)構(gòu)。在特殊的情況下，我們希望不論是隊首還是隊尾都可以入隊或者出隊，這種結(jié)構(gòu)就叫做雙端隊列。基于我們之前實現(xiàn)的鏈表結(jié)構(gòu)，我們可以輕而易舉的實現(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;
    }
}

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

總結(jié)

棧和隊列是我們最常用的數(shù)據(jù)結(jié)構(gòu)，我們會在其他的復(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ǔ)知識和現(xiàn)代PHP開發(fā)中關(guān)于規(guī)范、部署、優(yōu)化的一些實戰(zhàn)性建議，同時還有對Javascript語言特點的深入研究。