Detailed explanation of queues in php

Today, we will learn another very classic logical structure type: queue. I believe many students have already used cache queue tools such as redis and rabbitmq. In fact, databases and program codes can all implement queue operations. Just like stacks, queues also have their own specific rules. As long as they comply with these rules, it is called a queue.

What is a queue?

Compared to the stack, the queue is a first-in-first-out (FIFO) sequential logical structure. What is first in first out? Just like our queue, when we go to the bank or hospital, we always have to take a number at the door, and this number is called in order. The person who comes first can do business or see a doctor first. This is a typical queue. In the same way, daily queuing is a standard queue mode.

If there is someone who jumps the queue, we can consider it to have a higher priority if there is a legitimate reason. This is a special form of elements in the queue. Just like we give priority to pregnant women when waiting for the subway or bus, there is also a priority window for military personnel when queuing up to buy train tickets. However, this is outside the scope of our discussion this time.

When queuing up at a bus stop, of course the first person in line can get on the bus first, and then follow the other order. At this time, you come to the bus stop, then you can only be the last one in line. This is the specific manifestation of the queue.

Similarly, like stacks, there are some nouns we need to understand. When you come to a bus stop and are the last person in line, this operation is called "joining the queue." When the bus enters the station and the first passenger gets on the bus, this operation is called "exiting". The position of the first passenger is called the "head of the queue". As the last passenger in the current queue, your position is called the "tail of the queue". Going back to the code logic, that is to say, the queue is "entered" from the "end" and "exited" from the "head".

Sequential Queue

OK, let’s look directly at the code. The first thing we see is still the implementation of the sequential queue.

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

Since it is a sequential team, we still use an array data to represent the elements in the team. Then define two pointers front and rear to represent the head and tail of the team. Because it is a sequential queue, the pointer here actually stores the subscript of the array. The next operation is actually very simple, rear when "entering the queue", and front when "leaving the queue".

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
// )

Do you feel that after learning the stack, the queue is also easy to understand. When initializing the queue, just set the head and tail pointers to records with 0 subscripts. When joining the queue, let the tail of the queue increase. In this code, we join two elements into the queue, and the printed sequential queue content is as shown in the comments.

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
// )

When leaving the team, let front perform the operation of adding 1. However, when dequeuing, you still need to determine whether all elements in the array have been dequeued. Here, we only use a very simple judgment condition, that is, whether front and rear are equal to determine whether the queue is empty. You can use an illustration to assist in understanding the code.

Circular Queue

I believe many students have noticed it. The queue operation only modifies the pointer records of the queue head and queue tail, but the array will keep increasing. If it keeps increasing, the array will fill up the memory. This is definitely not a good queue implementation. In fact, in C language, arrays are given a fixed length. The array in PHP is more like a Hash structure, so it can grow infinitely, and we do not need to define a specific array length at the beginning.

This is also the convenience of PHP, but what should we do if we don’t want to waste memory space? Just like in C language, we also specify a length for the array in PHP, and use a very classic "circular queue" to solve the storage problem of the queue array. As shown in the figure below:

In fact, it means that within the limited array space, when we reach the maximum value of the array, the new data will be saved back to the previous one. subscript position. For example, in the picture we have 6 elements, the current head of the team is at subscript 2, and the tail of the team is at subscript 5. If we enqueue an element, the end of the queue moves to index 6. If you add another element, the queue tail will move back to the 0 subscript. If you continue to add, when the queue tail subscript is equal to the queue head subscript minus 1, we will think that the queue is full and no more elements can be added.

Similarly, when dequeuing, we also operate the team head element cyclically. When the team head element reaches the subscript of 6, if we continue to dequeue, it will return to the position of 0 subscript and continue to dequeue. . When the head of the queue and the tail of the queue are equal, the current queue can also be determined to be an empty queue.

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

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 这个东西容易让人头晕，硬记下来就可以了。大家还是可以结合图示来学习：

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视频教程

The above is the detailed content of Detailed explanation of queues in php. For more information, please follow other related articles on the PHP Chinese website!