实战PHP数据结构基础之队列

cnio 发布于2019-07-01 10:09 / 1953人阅读

摘要：环形队列为充分利用向量空间，克服假溢出现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。双端队列截止目前我们所实现的队列都是在队尾入队，队首出队的结构。

什么是队列

队列是另外一种遵循先进先出原则的线性数据结构。队列有两端可供操作，一端出队，一端入队。这个特点和栈不同，栈只有一端可以用来操作。入队总是在后端，出队在前端。

常见操作

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语言特点的深入研究。

私有云超融合服务器之基础篇黑客基础之DOS 零基础课程之c语言零基础实战机器学习

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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