在逻辑结构中，我们学习了一个非常经典的结构类型：栈。今天，我们来学习另一种非常经典的逻辑结构类型：队列。相信很多同学都已经使用过redis、rabbitmq等缓存队列工具。事实上，数据库和程序代码都可以实现队列操作。就像栈一样，队列也有特定的规则。只要满足这些规则，就称为队列。什么是队列？与栈相比，队列是一种先进先出（FIFO）的顺序逻辑结构。什么是先进先出？就像我们排队一样，去银行或者医院，总要在门口取号，这个号是按顺序叫的??。先来者可先做生意或先看病。这是一个典型的队列。同理，每日排队是一种标准的排队模式。如果存在队列跳线，我们可以认为它具有更高的优先级，如果有正当理由，这是队列中元素的一种特殊形式。就像我们在等地铁、公交车时优先考虑孕妇一样，在排队买火车票时也有军人优先窗口。不过，这不在我们这次的讨论范围之内。在公交车站排队时，排在第一位的人当然可以先上车，然后再按顺序。这时，你来到了汽车站，所以你只能排在最后一个。这就是队列的具体表现。同样，和堆栈一样，有一些名词我们需要了解。当你来到公交车站，你是最后一个排队的人时，这种操作叫做“排队”。公交车进站后，第一位乘客上车。此操作称为“出队”。第一个乘客的位置被称为“队首”。作为当前队列中的最后一位乘客，您的位置称为“队列尾部”。回到代码逻辑，也就是说，队列从“尾”“入”，从“头”“出”。顺序队列是可以的。我们直接看代码。我们首先看到的是顺序队列的实现。类SqQueue{公共$data;公共$前线；public$rear;}既然是顺序队列，我们??还是用一个数组数据来表示队列中的元素。然后定义两个指针front和rear分别代表队列的头部和尾部。因为是顺序队列，这里的指针其实保存的是数组的下标。接下来的操作其实很简单，“入队”的时候是rear++，“出队”的时候是front++。函数InitSqQueue(){$queue=newSqQueue();$队列->数据=[]；$queue->front=0;$queue->rear=0;返回$queue;}functionEnSqQueue(SqQueue&$queue,$e){$queue->data[$queue->rear]=$e;$queue->rear++;}functionDeSqQueue(SqQueue&$queue){//队列为空if($queue->front==$queue->rear){returnfalse;$e=$queue->data[$queue->front];$队列->前面++；return$e;}$q=InitSqQueue();EnSqQueue($q,'A');EnSqQueue($q,'B');print_r($q);//SqQueue对象//(//[数据]=>Array//(//[0]=>A//[1]=>B//)//[front]=>0//[rear]=>2//)学了之后是不是觉得栈，队列也很好理解。初始化队列时，只要让队头和队尾指针都为0下标记录即可。入队时，让队尾增加。在这段代码中，我们向队列中添加了两个元素，打印出的顺序队列内容如注释所示。EnSqQueue($q,'C');EnSqQueue($q,'D');EnSqQueue($q,'E');print_r($q);//SqQueue对象//(//[数据]=>数组//(//[0]=>A//[1]=>B//[2]=>C//[3]=>D//[4]=>E//)//[front]=>0//[rear]=>5//)echoDeSqQueue($q),PHP_EOL;//AechoDeSqQueue($q),PHP_EOL;//BechoDeSqQueue($q),PHP_EOL;//CechoDeSqQueue($q),PHP_EOL;//DechoDeSqQueue($q),PHP_EOL;//EechoDeSqQueue($q),PHP_EOL;//打印_r($q);//SqQueue对象//(//[数据]=>数组//(//[0]=>A//[1]=>B//[2]=>C//[3]=>D//[4]=>E//)//[front]=>5//[rear]=>5//)出队时，让前面加1。但是出队时，需要判断数组中的所有元素是否已经出队。这里，我们只用一个很简单的判断条件，即前后是否相等来判断队列是否为空。您可以使用图表来帮助理解代码。循环队列相信很多同学都已经看过了。队列操作只是修改队列头部和尾部的指针记录，但是数组会一直增加，所以如果一直增加，就会导致这个数组占满内存，这绝对不是一个好的队列实现。其实在C语言中，数组就是要给定长度的。PHP中的数组更像是一个Hash结构，所以它可以无限增长，我们不需要一开始就定义一个具体的数组长度。这也是PHP的方便之处，但是不想浪费内存空间怎么办呢？就像在C语言中一样，我们在PHP中也为数组指定了一个长度，并使用了一个非常经典的“循环队列”来解决队列数组的存储问题。如下图所示：其实就是说在有限的数组空间内，当我们到达数组的最大值时，新的数据会被存回到之前的下标位置。比如我们图中有6个元素，当前队头在2个下标，队尾在5个下标。如果我们入队一个元素，则队列尾部移动到索引6。如果添加另一个元素，队列尾部将移回下标0。如果我们继续添加，当队列尾部的下标为等于头部的下标减1，我们认为队列已满，不能再添加元素。同样，在dequeue操作的时候，我们也是循环操作teamhead元素。当队头元素到达6下标时，如果继续出队，则回到0下标位置继续出队。当队列头和队列尾相等时，也可以判断当前队列为空队列。由此可见，循环队列比普通线性队列多了一个满状态。下面就来看看如何直接从代码中判断队伍的满员情况吧。define('MAX_QUEUE_LENGTH',6);functionEnSqQueueLoop(SqQueue&$queue,$e){//判断队列是否满if(($queue->rear+1)%MAX_QUEUE_LENGTH==$queue->front){返回假；}$queue->data[$queue->rear]=$e;$queue->rear=($queue->rear+1)%MAX_QUEUE_LENGTH;//更改为循环下标}functionDeSqQueueLoop(SqQueue&$queue){//队列为空if($queue->front==$queue->rear){returnfalse;$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对象//(//[data]=>Array//(//[0]=>A//[1]=>B//[2]=>C//[3]=>D//[4]=>E//[5]=>//结尾//)//[front]=>0//[rear]=>5//)echoDeSqQueueLoop($q),PHP_EOL;echoDeSqQueueLoop($q),PHP_EOL;print_r($q);//SqQueue对象//(//[数据]=>数组//(//[0]=>A//[1]=>B//[2]=>C//头//[3]=>D//[4]=>E//[5]=>//尾//)//[前]=>2//[后]=>5//)EnSqQueueLoop($q,'F');EnSqQueueLoop($q,'G');EnSqQueueLoop($q,'H');print_r($q);//SqQueue对象//(//[data]=>Array//(//[0]=>G//[1]=>B//尾//[2]=>C//头//[3]=>D//[4]=>E//[5]=>F//)//[front]=>2//[rear]=>1//)出队和入队的下标移动和队列满度的判断都是以(queue->rear+1)的形式进行的)%MAX_QUEUE_LENGTH根据队列对长度取模得到当前循环下标是不是很巧妙。不得不感慨先人的智慧！当然这也是基本的数学原理，所以要学习数据结构，还是需要复习一下数学相关的知识！链式队列的顺序队列是不是混淆了？没关系，队列的链式结构其实比顺序结构要简单，因为它真的只需要操作队头和队尾的指针，其他的真的不需要考虑。而这个指针实际上是一个指向特定对象的指针。类LinkQueueNode{public$data;public$next;}classLinkQueue{public$first;//队列头指针public$rear;//queuetailpointer}这里我们需要两个基本的物理结构。一个是节点Node，一个是队列对象。节点对象就是一个普通的链表结构，没什么特别的。队列对象就更简单了，一个属性是队列头指针，另一个属性是队列尾指针。函数InitLinkQueue(){$node=newLinkQueueNode();$node->next=NULL;$queue=newLinkQueue();$queue->first=$node;$queue->rear=$node;返回$queue;}functionEnLinkQueue(LinkQueue&$queue,$e){$node=newLinkQueueNode();$node->data=$e;$node->next=NULL;$queue->rear->next=$node;$queue->rear=$node;}functionDeLinkQueue(LinkQueue&$queue){if($queue->front==$queue->rear){返回false;}$node=$queue->first->next;$v=$节点->数据；$queue->first->next=$node->next;if($queue->rear==$node){$queue->rear=$queue->first;}返回$v;}$q=InitLinkQueue();EnLinkQueue($q,'A');EnLinkQueue($q,'B');EnLinkQueue($q,'C');EnLinkQueue($q,'D');EnLinkQueue($q,'E');print_r($q);//LinkQueue对象//(//[first]=>LinkQueueNode对象//(//[data]=>//[next]=>LinkQueueNode对象//(//[data]=>A//[next]=>LinkQueueNode对象//(//[data]=>B//[next]=>LinkQueueNode对象//(//[data]=>C//[next]=>LinkQueueNode对象//(//[data]=>D//[next]=>LinkQueueNode对象//(//[data]=>E//[下一步]=>//)//)//)//)//)//)//[rear]=>LinkQueueNode对象//(//[data]=>E//[next]=>//)//)echoDeLinkQueue($q),PHP_EOL;//AechoDeLinkQueue($q),PHP_EOL;//BEnLinkQueue($q,'F');print_r($q);//LinkQueue对象//(//[first]=>LinkQueueNode对象//(//[data]=>//[next]=>LinkQueueNode对象//(//[数据]=>C//[下一个]=>LinkQueueNode对象//(//[数据]=>D//[下一个]=>LinkQueueNode对象//(//[数据]=>E//[next]=>LinkQueueNodeObject//(//[data]=>F//[next]=>//)//)//)//)//)//[rear]=>LinkQueueNode对象//(//[data]=>F//[next]=>//)//)出入队列的代码功能和测试代码一并给出。是不是很简单？初始队头元素仍然是一个空节点作为起始节点。然后在入队时，让rear等于新创建的节点，在链表中建立链式关系。出队时也一样，让first成为当前first的下一跳节点，即first->next。判断队列是否为空的条件很简单，就是队头和队尾指针是否相等。和sequentialteam相比，chainteam其实简单一点，但是同样的东西，接下来的东西很容易让人头晕，死记硬背就行了。还是可以从图中了解到：PHP为我们提供了一个数组队列操作最后，和栈一样，PHP代码也为我们提供了一个可以进行队列操作的函数。$sqQueueList=[];array_push($sqQueueList,'a');array_push($sqQueueList,'b');array_push($sqQueueList,'c');print_r($sqQueueList);//数组//(//[0]=>a//[1]=>b//[2]=>c//)array_shift($sqQueueList);print_r($sqQueueList);//数组//(//[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。Stacksandqueues/source/3.2queues.php相关的逻辑操作参考资料：《数据结构》第二版，闫伟民《数据结构》第二版，陈越《数据结构高分笔记》2020版，天琴考研各自媒体平台可以搜索【硬核】专案经理]
