详解php中的队列

阿雪小哥_4563

阿雪小哥_4563

2021-07-23

6415人浏览

转载

今天,我们就来学习另外一个也是非常经典的逻辑结构类型:队列。相信不少同学已经使用过 redis 、 rabbitmq 之类的缓存队列工具。其实,数据库、程序代码,这些都可以实现队列的操作,就和栈一样,队列也是有其特定的规则,只要符合这个规则,它就叫做队列。

什么是队列?

相对于栈来说,队列是一种先进先出(FIFO)的顺序逻辑结构。什么叫先进先出呢?就和我们的排队一样,当我们去银行或者医院的时候,总是要在门口取一个号,这个号是按顺序叫的。先来的人就可以先办业务或者看病,这就是一个典型的队列。同理,日常的排队就是一个标准的队列模式。

如果有插队的,在有正当理由的情况下,我们可以认为它的优先级更高,这是队列中元素的一种特殊形式。就像我们会在等地铁或者公交的时候让孕妇优先,在排队买火车票的时候也有军人的优先窗口。不过,这个并不在我们这次的讨论范围之内。

在公交站排队时,排第一个的当然可以第一个上车,然后依次。这时,你来到了公交站,那么你只能排到最后一位。这个就是队列的具体表现形式。

同样,和栈一样,也有一些名词我们需要了解。当你来到公交站并排到最后一位时,这个操作叫作“入队”。当公交车进站后,第一位乘客上车,这个操作叫做“出队”。第一位乘客所处的位置叫做“队头”,你做为当前队列的最后一位乘客,你的位置就叫做“队尾”。回到代码逻辑上面来看,也就是说队列是从“队尾”“入队”,从“队头”“出队”。

顺序队列

OK,我们还是直接从来代码来看,首先看到的依然是顺序队的实现。

class SqQueue{
    public $data;
    public $front;
    public $rear;
}

既然是顺序队,我们依然还是用一个数组 data 来表示队内的元素。然后定义两个指针 front 和 rear 来表示队头和队尾。因为是顺序队,所以这里的指针其实也就是保存的是数组的下标。接下来的操作其实就非常的简单了,“入队”时 rear++ ,“出队”时 front++ 。

function InitSqQueue(){
    $queue = new SqQueue();
    $queue->data = [];
    $queue->front = 0;
    $queue->rear = 0;
    return $queue;
}

function EnSqQueue(SqQueue &$queue, $e){
    $queue->data[$queue->rear] = $e;
    $queue->rear ++;
}

function DeSqQueue(SqQueue &$queue){
    // 队列为空
    if($queue->front == $queue->rear){
        return false;
    }
    $e = $queue->data[$queue->front];
    $queue->front++;
    return $e;
}

$q = InitSqQueue();
EnSqQueue($q, 'A');
EnSqQueue($q, 'B');
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//         )

//     [front] => 0
//     [rear] => 2
// )

是不是感觉学过了栈之后,队列也很好理解了。初始化队列时,就是让队头和队尾指针都是 0 下标的记录就可以了。入队的时候让队尾增加,在这段代码中,我们入队了两个元素,打印出来的顺序队列内容就如注释所示。

EnSqQueue($q, 'C');
EnSqQueue($q, 'D');
EnSqQueue($q, 'E');
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C
//             [3] => D
//             [4] => E
//         )

//     [front] => 0
//     [rear] => 5
// )

echo DeSqQueue($q), PHP_EOL; // A
echo DeSqQueue($q), PHP_EOL; // B
echo DeSqQueue($q), PHP_EOL; // C
echo DeSqQueue($q), PHP_EOL; // D
echo DeSqQueue($q), PHP_EOL; // E

echo DeSqQueue($q), PHP_EOL; // 

print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C
//             [3] => D
//             [4] => E 
//         )

//     [front] => 5
//     [rear] => 5
// )

出队的时候,就让 front 进行加 1 操作。不过,在出队的时候还需要判断数组中的元素是否全部出队了,在这里,我们只用了一个非常简单的判断条件,那就是 front 和 rear 是否相等来判断队列是否空了。大家可以通过一个图示来辅助对代码的理解。

bVcTDKy.webp.jpg

循环队列

相信已经有不少同学看出来了。队列操作只是修改队头和队尾的指针记录,但是数组会一直增加,这样如果一直增加的话,就会导致这一个数组占满内存,这肯定不是一个好的队列实现。其实,在 C 语言中,数组就是要给一个固定的长度的。而 PHP 中的数组更像是一个 Hash 结构,所以它是可以无限增长的,并不需要我们在一开始定义一个具体的数组长度。

这也是 PHP 的方便之处,不过如果我们不想浪费内存空间的话,应该怎么办呢?就像在 C 语言中一样,我们在 PHP 中也为数组指定一个长度,并且使用非常经典的“循环队列”来解决队列数组的存储问题。就像下图所示:

bVcTDKz.webp.jpg

其实意思就是,在有限的数组空间范围内,当我们达到数组的最大值时,将新的数据保存回之前的下标位置。比如图中我们有 6 个元素,当前队头在 2 下标,队尾在 5 下标。如果我们入队一个元素,队尾移动到 6 下标。再添加一个元素的话,队尾移动回 0 下标,如果继续添加的话,当队尾下标等于队头下标减 1 的时候,我们就认为这个队列已经满了,不能再增加元素了。

btpanel phpsite 宝塔面板PHP网站
btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理:站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

同理,出队操作的时候我们也是循环地操作队头元素,当队头元素到 6 的下标后,继续出队的话,也会回到 0 下标的位置继续出队。当队头和队尾相等时,当前的队列也可以判定为空队列了。

由此,我们可以看出,循环队列相比普通的线性队列来说,多了一个队满的状态。我们还是直接从代码中来看看这个队满的条件是如何判断的。

define('MAX_QUEUE_LENGTH', 6);

function EnSqQueueLoop(SqQueue &$queue, $e){
    // 判断队列是否满了
    if(($queue->rear + 1) % MAX_QUEUE_LENGTH == $queue->front){
        return false;
    }
    $queue->data[$queue->rear] = $e;
    $queue->rear = ($queue->rear + 1) % MAX_QUEUE_LENGTH; // 改成循环下标
}

function DeSqQueueLoop(SqQueue &$queue){
    // 队列为空
    if($queue->front == $queue->rear){
        return false;
    }
    $e = $queue->data[$queue->front];
    $queue->front = ($queue->front + 1) % MAX_QUEUE_LENGTH; // 改成循环下标
    return $e;
}

$q = InitSqQueue();
EnSqQueueLoop($q, 'A');
EnSqQueueLoop($q, 'B');
EnSqQueueLoop($q, 'C');
EnSqQueueLoop($q, 'D');
EnSqQueueLoop($q, 'E');

EnSqQueueLoop($q, 'F');

print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C
//             [3] => D
//             [4] => E
//             [5] =>   // 尾
//         )

//     [front] => 0
//     [rear] => 5
// )

echo DeSqQueueLoop($q), PHP_EOL;
echo DeSqQueueLoop($q), PHP_EOL;
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//             [2] => C // 头
//             [3] => D
//             [4] => E
//             [5] =>   // 尾
//         )

//     [front] => 2
//     [rear] => 5
// )

EnSqQueueLoop($q, 'F');
EnSqQueueLoop($q, 'G');

EnSqQueueLoop($q, 'H');
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => G
//             [1] => B // 尾
//             [2] => C // 头
//             [3] => D
//             [4] => E
//             [5] => F
//         )

//     [front] => 2
//     [rear] => 1
// )

出、入队的下标移动以及队满的判断,都是以 (queue->rear + 1) % MAX_QUEUE_LENGTH 这个形式进行的。根据队列长度的取模来获取当前的循环下标,是不是非常地巧妙。不得不感慨先人的智慧呀!当然,这也是基本的数学原理哦,所以,学习数据结构还是要复习一下数学相关的知识哦!

链式队列

顺序队列有没有看懵?没关系,队列的链式结构其实相比顺序结构还要简单一些,因为它真的只需要操作队头和队尾的指针而已,别的真的就不太需要考虑了。而且这个指针就是真的指向具体对象的指针了。

class LinkQueueNode{
    public $data;
    public $next;
}

class LinkQueue{
    public $first; // 队头指针
    public $rear; // 队尾指针
}

这里我们需要两个基本的物理结构。一个是节点 Node ,一个是队列对象,节点对象就是一个正常的链表结构,没啥特别的。而队列对象里面就更简单了,一个属性是队头指针,一个属性是队尾指针。

function InitLinkQueue(){
    $node = new LinkQueueNode();
    $node->next = NULL;
    $queue = new LinkQueue();
    $queue->first = $node;
    $queue->rear = $node;
    return $queue;
}

function EnLinkQueue(LinkQueue &$queue, $e){
    $node = new LinkQueueNode();
    $node->data = $e;
    $node->next = NULL;

    $queue->rear->next = $node;
    $queue->rear = $node;
}

function DeLinkQueue(LinkQueue &$queue){
    if($queue->front == $queue->rear){
        return false;
    }

    $node = $queue->first->next;
    $v = $node->data;

    $queue->first->next = $node->next;
    if($queue->rear == $node){
        $queue->rear = $queue->first;
    }

    return $v;
}

$q = InitLinkQueue();
EnLinkQueue($q, 'A');
EnLinkQueue($q, 'B');
EnLinkQueue($q, 'C');
EnLinkQueue($q, 'D');
EnLinkQueue($q, 'E');

print_r($q);
// LinkQueue Object
// (
//     [first] => LinkQueueNode Object
//         (
//             [data] => 
//             [next] => LinkQueueNode Object
//                 (
//                     [data] => A
//                     [next] => LinkQueueNode Object
//                         (
//                             [data] => B
//                             [next] => LinkQueueNode Object
//                                 (
//                                     [data] => C
//                                     [next] => LinkQueueNode Object
//                                         (
//                                             [data] => D
//                                             [next] => LinkQueueNode Object
//                                                 (
//                                                     [data] => E
//                                                     [next] => 
//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

//     [rear] => LinkQueueNode Object
//         (
//             [data] => E
//             [next] => 
//         )

// )

echo DeLinkQueue($q), PHP_EOL; // A
echo DeLinkQueue($q), PHP_EOL; // B

EnLinkQueue($q, 'F');
print_r($q);
// LinkQueue Object
// (
//     [first] => LinkQueueNode Object
//         (
//             [data] => 
//             [next] => LinkQueueNode Object
//                 (
//                     [data] => C
//                     [next] => LinkQueueNode Object
//                         (
//                             [data] => D
//                             [next] => LinkQueueNode Object
//                                 (
//                                     [data] => E
//                                     [next] => LinkQueueNode Object
//                                         (
//                                             [data] => F
//                                             [next] => 
//                                         )

//                                 )

//                         )

//                 )

//         )

//     [rear] => LinkQueueNode Object
//         (
//             [data] => F
//             [next] => 
//         )

// )

出、入队的代码函数和测试代码就一并给出了,是不是非常的简单。初始的队头元素依然是一个空节点做为起始节点。然后入队的时候,让 rear 等于新创建的这个节点,并在链表中建立链式关系。出队的时候也是同样的让 first 变成当前这个 first 的下一跳节点,也就是 first->next 就可以了。判断队空的条件也是简单的变成了队头和队尾指针是否相等就可以了。链队相比顺序队其实是简单了一些,不过同样的,next 这个东西容易让人头晕,硬记下来就可以了。大家还是可以结合图示来学习:

view.webp.jpg

PHP 为我们提供的数组队列操作

最后,就和栈一样,PHP 代码中也为我们提供了一个可以用于队列操作的函数。

$sqQueueList = [];

array_push($sqQueueList, 'a');
array_push($sqQueueList, 'b');
array_push($sqQueueList, 'c');

print_r($sqQueueList);
// Array
// (
//     [0] => a
//     [1] => b
//     [2] => c
// )

array_shift($sqQueueList);
print_r($sqQueueList);
// Array
// (
//     [0] => b
//     [1] => c
// )

array_shift() 函数就是弹出数组中最前面的那个元素。请注意,这里元素的下标也跟着变动了,如果我们是 unset() 掉数组的 0 下标元素的话,b 和 c 的下标依然还会是 1 和 2 。而 array_shift() 则会重新整理数组,让其下标依然有序。

unset($sqQueueList[0]);
print_r($sqQueueList);
// Array
// (
//     [1] => c
// )

总结

关于栈的队列的内容我们就通过两篇文章介绍完了。不过光说不练假把式,接下来,我们来一点真实的干货,使用栈和队列来做做题呗,学算法就得刷题,一日不刷如隔三秋呀!!!

测试代码:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3.栈和队列/source/3.2队列的相关逻辑操作.php

推荐学习:php视频教程

php免费学习视频:立即使用
踏上前端学习之旅,开启通往精通之路!从前端基础到项目实战,循序渐进,一步一个脚印,迈向巅峰!

相关文章

PHP速学教程(入门到精通)
PHP速学教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

php

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
rabbitmq和kafka有什么区别
rabbitmq和kafka有什么区别

rabbitmq和kafka的区别:1、语言与平台;2、消息传递模型;3、可靠性;4、性能与吞吐量;5、集群与负载均衡;6、消费模型;7、用途与场景;8、社区与生态系统;9、监控与管理;10、其他特性。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.02.23

704

5

Java 消息队列与异步架构实战
Java 消息队列与异步架构实战

本专题系统讲解 Java 在消息队列与异步系统架构中的核心应用,涵盖消息队列基本原理、Kafka 与 RabbitMQ 的使用场景对比、生产者与消费者模型、消息可靠性与顺序性保障、重复消费与幂等处理,以及在高并发系统中的异步解耦设计。通过实战案例,帮助学习者掌握 使用 Java 构建高吞吐、高可靠异步消息系统的完整思路。

2026.01.28

1228

20

RabbitMQ使用教程合集
RabbitMQ使用教程合集

RabbitMQ使用教程合集整理 RabbitMQ 基础教程、消息队列开发案例、生产者消费者、交换机与队列实战内容。

2026.05.20

224

15

RabbitMQ集群部署指南
RabbitMQ集群部署指南

RabbitMQ集群部署指南聚合 RabbitMQ 集群部署、高可用架构、镜像队列、故障恢复、监控与运维优化内容。

2026.05.20

137

12

RabbitMQ Docker实战指南
RabbitMQ Docker实战指南

RabbitMQ Docker实战指南提供 RabbitMQ Docker 镜像部署、Docker Compose、Kubernetes Operator 与云原生实践教程。

2026.05.20

162

10

C++ 智能指针与现代内存管理
C++ 智能指针与现代内存管理

深入讲解 C++ 现代内存管理的核心工具——智能指针,涵盖 unique_ptr 独占所有权语义、shared_ptr 引用计数机制与循环引用问题、weak_ptr 弱引用的应用场景、make_unique/make_shared 工厂函数的性能优势、自定义删除器的编写、RAII 资源管理思想的实践,以及从裸指针迁移到智能指针的重构策略,帮助开发者编写安全无泄漏的现代 C++ 代码。

2026.04.23

399

31

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2961

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
墨刀帮助中心
墨刀帮助中心

共0课时 | 0人学习

MyEclipse学习中心
MyEclipse学习中心

共0课时 | 0人学习

Apache Subversion 官方手册
Apache Subversion 官方手册

共0课时 | 0人学习