實戰PHP數據結構基礎之隊列

cnio 發布于2019-07-01 10:09 / 2054人閱讀

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

什么是隊列

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

常見操作

enqueue -> 入隊

dequeue -> 出隊

peek -> 返回隊列前端元素

isEmpty -> 是否為空

PHP實現

首先我們定義一個QueueInterface。

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

來看基于數組的隊列實現

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結構，我們輕而易舉的寫出來了隊列的基本操作方法。果然世界上最好的語言名不虛傳。

可能機智的同學已經猜到了，我之前已經定義了一個隊列接口，那隊列的實現肯定不止只有上面一種哈。來看基于鏈表的實現。

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;
        }
    }
}

里面涉及到了之前的鏈表實現，不了解細節的同學可以去這里看看。

Spl中的隊列

強大的PHP已經內置了隊列實現，可以使用的方法和上面我們自己實現的類似。

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();
    }
}

優先隊列

優先隊列是一種特殊的隊列，入隊或者出隊的順序都是基于每個節點的權重。

順序序列

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

無序序列

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

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;
    }
}

環形隊列

為充分利用向量空間，克服"假溢出"現象的方法是：將向量空間想象為一個首尾相接的圓環，并稱這種向量為循環向量。存儲在其中的隊列稱為循環隊列。環形隊列也是一種數組，只是它在邏輯上把數組的頭和尾相連，形成循環隊列，當數組尾滿的時候，要判斷數組頭是否為空，不為空繼續存放數據。

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;

    }
}

雙端隊列

截止目前我們所實現的隊列都是在隊尾(rear)入隊，隊首(front) 出隊的結構。在特殊的情況下，我們希望不論是隊首還是隊尾都可以入隊或者出隊，這種結構就叫做雙端隊列。基于我們之前實現的鏈表結構，我們可以輕而易舉的實現這樣的結構。

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;
    }
}

里面涉及到了之前的鏈表實現，不了解細節的同學可以去這里看看。

總結

棧和隊列是我們最常用的數據結構，我們會在其他的復雜數據結構中看到這兩種抽象數據類型的應用。在下一章，我們繼續學習PHP數據結構之遞歸，這是一種將復雜問題簡單化的常用思路。

專題系列

PHP基礎數據結構專題系列目錄地址：地址主要使用PHP語法總結基礎的數據結構和算法。還有我們日常PHP開發中容易忽略的基礎知識和現代PHP開發中關于規范、部署、優化的一些實戰性建議，同時還有對Javascript語言特點的深入研究。

云服務器 GPU云服務器之基礎篇黑客基礎之DOS 零基礎課程之c語言零基礎實戰機器學習

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/28865.html

實戰PHP數據結構基礎之棧

摘要：棧和隊列棧和隊列和之前講到的實戰數據結構基礎之雙鏈表一樣都是線性結構。來看基于數組的棧實現得益于強大的結構，我們輕而易舉的寫出來了棧的基本操作方法。專題系列基礎數據結構專題系列目錄地址主要使用語法總結基礎的數據結構和算法。棧和隊列棧和隊列和之前講到的實戰PHP數據結構基礎之雙鏈表一樣都是線性結構。棧有什么特點棧遵循后進先出的原則(LIFO)。這意味著棧只有一個出口用來壓入元素...

banana_pi 2019-07-01 10:08 評論0 收藏0
PHP基礎

摘要：分別為適配器模式，裝飾器模式，代理模式，外觀模式，橋接模式，組合模式，享元模式。設計模式五適配器模式適配器模式將某個對象的接生成器和協程的實現在這篇文章中，作者針對那些比較難以理解的概念，以一個更為通俗的方式去講明白。。 PHP 源碼注解 PHP 的詳細源碼注解 PHP 字符串操作整理一些有關字符串的常用操作。 Redis 常見七種使用場景 (PHP 實戰) 這篇文章主要介紹利用 R...

HtmlCssJs 2019-06-28 14:29 評論0 收藏0
PHPer書單

摘要：想提升自己，還得多看書多看書多看書下面是我收集到的一些程序員應該看得書單及在線教程，自己也沒有全部看完。共勉吧當然，如果你有好的書想分享給大家的或者覺得書單不合理，可以去通過進行提交。講師溫銘，軟件基金會主席，最佳實踐作者。想提升自己，還得多看書！多看書！多看書！下面是我收集到的一些PHP程序員應該看得書單及在線教程，自己也沒有全部看完。共勉吧！當然，如果你有好的書想分享給大家的或者...

jimhs 2019-07-01 12:35 評論0 收藏0
PHP小知識點

摘要：那些瑣碎的知識點作者記錄的的很奇特很難記的知識點。易錯知識點整理注意和的區別中和都是輸出的作用，但是兩者之間還是有細微的差別。今天手頭不忙，總結一下，分享過程中掌握的知識點。深入理解 PHP 之：Nginx 與 FPM 的工作機制這篇文章從 Nginx 與 FPM 的工作機制出發，探討配置背后的原理，讓我們真正理解 Nginx 與 PHP 是如何協同工作的。 PHP 那些瑣碎的知識...

hover_lew 2019-06-28 14:35 評論0 收藏0
實戰PHP數據結構基礎之雙鏈表

摘要：什么是雙鏈表上一篇實戰數據結構基礎之單鏈表說到單鏈表由一個一個的作為節點的對象構成的，每一個節點都有指向下一個節點的指針，最后一個節點的指針域指向空。什么是雙鏈表？上一篇實戰PHP數據結構基礎之單鏈表說到單鏈表由一個一個的作為節點的對象構成的，每一個節點都有指向下一個節點的指針，最后一個節點的指針域指向空。每個節點可以存儲任何數據類型。而雙鏈表每個節點有兩個指針域，分別指向前驅...

Michael_Lin 2019-07-01 10:07 評論0 收藏0