In logical structures, we have studied a very classic type of structure: the stack. Today, we’re going to look at another very classic type of logical structure: queues. Many of you have already used redis, RabbitMQ and other cache queue tools. In fact, the database, program code, these can implement the operation of the queue, just like the stack, the queue also has its specific rules, as long as it conforms to this rule, it is called queue.

What is a queue?

A queue is a first-in, first-out (FIFO) sequential logical structure compared to a stack. What is fifO? Just like our queue, when we go to the bank or hospital, we always have to take a number at the door, which is called in order. Those who come first can get a business or doctor’s appointment first, which is a typical queue. By the same token, everyday queuing is a standard queue pattern. If there is a queue-jumper, we can consider it to have a higher priority for a valid reason, which is a special form of an element in the queue. Just like we give priority to pregnant women when waiting for the subway or bus, there are also priority Windows for soldiers when waiting for train tickets. That, however, is beyond the scope of our discussion.

When you’re in line at a bus stop, the first person in line gets on first, of course, and then in turn. At this point, you arrive at the bus stop, and you are at the back of the line. So this is exactly what a queue looks like.

Also, as with stacks, there are some nouns we need to know. When you get to the end of the bus stop, this operation is called “queueing”. When the bus pulls into the station, the first passenger gets on. This operation is called “queuing up”. 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 “back of the queue”. Going back to the logic of the code, the queue starts at the end of the queue and ends at the head of the queue.

The order queue

OK, let’s go straight to the code, and the first thing we see is the implementation of the sequential queue.

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

Since this is a sequential queue, we still use an array data to represent the elements in the queue. And then we define two Pointers front and rear to indicate the head and the back of the queue. Because it’s a sequential queue, the pointer here is really just holding the index of the array. The next operation is actually very simple, “in the queue” when rear++, “out of the queue” when the 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 ++; 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 // )

Now that you’ve learned about stacks, queues are easy to understand. When initializing a queue, it is necessary to set the pointer at the head and the pointer at the tail of the queue to 0. In this code, we queued two elements, and the printed sequence queue content is shown in the comment.

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 you leave the queue, let the front add one. But, when you’re going out of the queue, you’re going to have to determine whether all of the elements in the array are out of the queue, and in this case, we’re just using a very simple criterion, which is whether front and rear are equal to each other to determine whether the queue is empty. You can use a diagram to help you understand the code.

Circular queue

I believe many of you have seen it. Queue operations just change the pointer records at the head and the end of the queue, but the array keeps growing, so if it keeps growing, the array will fill up memory, which is definitely not a good queue implementation. In fact, in C, you give an array a fixed length. An array in PHP is more like a Hash structure, so it can grow indefinitely, and we don’t need to define a specific array length to begin with. This is also handy for PHP, but what if we don’t want to waste memory? Just as in C, we specify a length for arrays in PHP, and use the classic “circular queue” to solve the storage problem of queue arrays. As you can see below:

What that means is, in the limited array space, when we reach the maximum value of the array, we save the new data back to the previous subscript. For example, we have six elements in the picture, and the current team leader is at index 2 and the end of the team is at index 5. If we add an element to the queue, the end of the queue moves to 6 subscript. If we add one more element, the end of the queue moves back to zero index, and if we add more, when the end of the queue is equal to the head of the queue minus one, we think the queue is full and can’t add any more elements.

Similarly, when exiting the team, we also operate the team head element in a loop. When the team head element reaches the subscript 6, if we continue exiting the team, it will return to the position of subscript 0 and continue exiting the team. When the head and tail of the queue are equal, the current queue can also be judged to be empty.

From this, we can see that a circular queue has one more full queue state than a normal linear queue. Let’s look directly at the code to see how the full condition is determined.

define('MAX_QUEUE_LENGTH', 6); function EnSqQueueLoop(SqQueue &$queue, If (($queue->rear + 1) % MAX_QUEUE_LENGTH == $queue->front){return false; } $queue->data[$queue->rear] = $e; $queue->rear = ($queue->rear + 1) % MAX_QUEUE_LENGTH; If ($queue->front == $queue->rear){return false;} function DeSqQueueLoop($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] => // Tail / / / / / 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 end = > 2 / / [rear] = > / / 5) EnSqQueueLoop ($q, 'F'); EnSqQueueLoop($q, 'G'); EnSqQueueLoop($q, 'H'); print_r($q); / / SqQueue Object / / / / [data] = > Array / /, / / / / [0] = > G [1] = > / / stern/B/C [2] = > / / / / [3] = > D / / / / [4] = > E [5] => F // ) // [front] => 2 // [rear] => 1 // )

(queue->rear + 1) % MAX_QUEUE_LENGTH (queue->rear + 1) % MAX_QUEUE_LENGTH) It is not very clever to get the current loop index based on the modulus of the queue length. Can’t help feeling the wisdom of ancestors! Of course, it’s also basic math, so it’s important to review your math before learning about data structures.

Chain queue

Any confusion about sequential queues? It doesn’t matter, the chain structure of the queue is actually simpler than the sequential structure, because it really only needs to operate on the Pointers at the head and the end of the queue, and there really isn’t much else to worry about. And that pointer is actually a pointer to a concrete object.

class LinkQueueNode{ public $data; public $next; } class LinkQueue{ public $first; Public $rear; // End pointer}

Here we need two basic physical structures. One is the Node, the other is the queue object, the Node object is just a normal list structure, nothing special. In the queue object, it’s even simpler, one property is a pointer to the head of the queue and one property is a pointer to the tail of the queue.

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

The code function and test code are given together, is not very simple. The initial team header element is still an empty node as the starting node. And then when you join the queue, you set rear equal to this newly created node, and you set up a chain in the list. First ->next = first->next = first->next The condition to determine whether the team is empty is as simple as whether the lead and tail Pointers are equal. The chain queue is actually a little easier than the sequential queue, but again, the next thing is easy to get dizzy, just memorize it. You can still use the diagrams to learn:

PHP provides us with array queue operations

Finally, just like the stack, the PHP code provides a function that we can use for queue operations.

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

The array_shift() function pops the first element in the array. Note that the indices of the elements are also changed. If we unset() the elements of the array with index 0, the indices of b and C will still be 1 and 2. Array_shift (), on the other hand, rearranges the array so that its indices are still in order.

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

conclusion

We are done with stack queues in two articles. But only say not practice false handle, next, we come to a bit of real dry goods, use stack and queue to do bai, learn the algorithm to brush the problem, a day does not brush such as every three years!!

Test code:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/3. Stack and queue /source/3.2 queue related logical operations

References:

Data Structures, 2nd Ed., Weimin Yan

Data Structures, 2nd Ed., Yue Chen

“Data structure high score notes” 2020 edition, day attendance entrance examination

[Core Project Manager] can be searched on each media platform.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

[PHP data structure] Logical operations related to queues

What is a queue?

The order queue

Circular queue

Chain queue

PHP provides us with array queue operations

conclusion

“Data structure high score notes” 2020 edition, day attendance entrance examination

[PHP data structure] Logical operations related to queues

What is a queue?

The order queue

Circular queue

Chain queue

PHP provides us with array queue operations

conclusion

“Data structure high score notes” 2020 edition, day attendance entrance examination

Related Posts

Development and production of dating website, the second

[Doctrine Migrations] Database migration components in depth analysis 2: custom integration

My Composer Package for “Nail Custom Robots”