什么是队列
队列是另外一种遵循先进先出原则的线性数据结构. 队列有两端可供操作, 一端出队, 一端入队. 这个特点和栈不同, 栈只有一端可以用来操作. 入队总是在后端, 出队在前端.
常见操作
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;
- }
- }
- }
里面涉及到了之前的链表实现, 不了解细节的同学可以去这里 https://github.com/xx19941215/webBlog 看看.
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 \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;
- }
- }
里面涉及到了之前的链表实现, 不了解细节的同学可以去这里 https://github.com/xx19941215/webBlog 看看.
总结
栈和队列是我们最常用的数据结构, 我们会在其他的复杂数据结构中看到这两种抽象数据类型的应用. 在下一章, 我们继续学习 PHP 数据结构之递归, 这是一种将复杂问题简单化的常用思路.
专题系列
PHP 基础数据结构专题系列目录地址: https://github.com/xx19941215/webBlog 主要使用 PHP 语法总结基础的数据结构和算法. 还有我们日常 PHP 开发中容易忽略的基础知识和现代 PHP 开发中关于规范, 部署, 优化的一些实战性建议, 同时还有对 Javascript 语言特点的深入研究.
来源: https://juejin.im/post/5b24c512e51d4558b80b1300