집 >백엔드 개발 >PHP 문제 >PHP의 대기열에 대한 자세한 설명

PHP의 대기열에 대한 자세한 설명

醉折花枝作酒筹앞으로: 2021-07-23 17:37:546007검색

오늘은 또 다른 매우 고전적인 논리 구조 유형인 대기열을 배워보겠습니다. 나는 많은 학생들이 이미 redis나 Rabbitmq와 같은 캐시 큐 도구를 사용해 본 적이 있다고 생각합니다. 실제로 데이터베이스와 프로그램 코드는 모두 큐 작업을 구현할 수 있습니다. 스택과 마찬가지로 큐에도 이러한 규칙을 준수하는 한 고유한 규칙이 있습니다.

PHP의 대기열에 대한 자세한 설명

큐란 무엇인가요?

스택에 비해 큐는 FIFO(선입선출) 순차 논리 구조입니다. 선입선출이란 무엇입니까? 우리 줄처럼 은행이나 병원에 갈 때 항상 문앞에서 번호표를 뽑아야 하는데, 이 번호가 순서대로 호출됩니다. 먼저 오는 사람이 먼저 사업을 하거나 의사를 만날 수 있는 전형적인 대기열입니다. 마찬가지로 일일 대기열은 표준 대기열 모드입니다.

큐를 뛰어넘는 사람이 있는 경우 정당한 이유가 있는 경우 이를 더 높은 우선순위로 간주할 수 있습니다. 이는 큐에 있는 요소의 특별한 형태입니다. 지하철이나 버스를 기다릴 때 임산부에게 우선권을 주는 것처럼, 기차표를 사기 위해 줄을 설 때도 군인을 위한 우선창구가 있습니다. 그러나 이는 이번 논의 범위를 벗어납니다.

버스 정류장에서 줄을 서는 경우, 물론 먼저 줄을 선 사람이 먼저 버스에 탈 수 있습니다. 이때 버스 정류장에 오면 가장 마지막 줄에만 올 수 있습니다. 이것이 대기열의 구체적인 표현입니다.

마찬가지로 스택처럼 우리가 이해해야 할 명사가 있습니다. 버스 정류장에 도착했을 때 줄의 마지막 사람이 되었을 때 이 작업을 "줄에 합류"라고 합니다. 버스가 역에 진입하여 첫 번째 승객이 버스에 탑승하는 것을 '나가기'라고 합니다. 첫 번째 승객의 위치를 "대기열의 선두"라고 합니다. 현재 대기열의 마지막 승객인 귀하의 위치를 "대기열의 꼬리"라고 합니다. 코드 논리로 돌아가면, 즉 대기열은 "끝"에서 "입력"되고 "헤드"에서 "종료"됩니다.

순차 대기열

자, 코드를 직접 살펴보겠습니다. 우리가 가장 먼저 보는 것은 여전히 순차 대기열의 구현입니다.

class SqQueue{
    public $data;
    public $front;
    public $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, &#39;A&#39;);
EnSqQueue($q, &#39;B&#39;);
print_r($q);
// SqQueue Object
// (
//     [data] => Array
//         (
//             [0] => A
//             [1] => B
//         )

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

스택을 배우고 나면 큐도 이해하기 쉽다고 느끼시나요? 큐를 초기화할 때 헤드 및 테일 포인터를 아래 첨자가 0인 레코드로 설정하면 됩니다. 큐에 합류할 때 큐의 꼬리를 늘리십시오. 이 코드에서는 두 요소를 큐에 결합하고 인쇄된 순차 큐 내용은 주석에 표시된 것과 같습니다.

EnSqQueue($q, &#39;C&#39;);
EnSqQueue($q, &#39;D&#39;);
EnSqQueue($q, &#39;E&#39;);
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
// )

팀 탈퇴시 프론트에서 1을 추가하는 작업을 수행하도록 합니다. 그러나 대기열에서 제거할 때 배열의 모든 요소가 대기열에서 제거되었는지 여부는 여전히 확인해야 합니다. 여기서는 대기열이 비어 있는지 확인하기 위해 매우 간단한 판단 조건, 즉 앞과 뒤가 같은지 여부만 사용합니다. 코드 이해를 돕기 위해 그림을 사용할 수 있습니다.

PHP의 대기열에 대한 자세한 설명

원형 대기열

많은 학생들이 눈치채셨을 거라 믿습니다. 큐 작업은 큐 헤드와 큐 테일의 포인터 레코드만 수정하지만 배열이 계속 증가하면 배열이 메모리를 가득 채울 것입니다. 이는 확실히 좋은 큐 구현이 아닙니다. 실제로 C 언어에서는 배열의 길이가 고정되어 있습니다. PHP의 배열은 해시 구조에 가깝기 때문에 무한히 커질 수 있으며 처음에 특정 배열 길이를 정의할 필요가 없습니다.

이것도 PHP의 편리함인데, 메모리 공간을 낭비하고 싶지 않다면 어떻게 해야 할까요? C 언어와 마찬가지로 PHP에서도 배열의 길이를 지정하고 매우 고전적인 "순환 대기열"을 사용하여 대기열 배열의 저장 문제를 해결합니다. 아래 그림과 같이:

PHP의 대기열에 대한 자세한 설명

실제로 제한된 배열 공간 내에서 배열의 최대값에 도달하면 새 데이터가 이전 첨자 위치에 다시 저장된다는 의미입니다. 예를 들어 그림에는 6개의 요소가 있고 현재 팀의 책임자는 아래 첨자 2에 있고 팀의 꼬리는 아래 첨자 5에 있습니다. 요소를 대기열에 넣으면 대기열의 끝이 인덱스 6으로 이동합니다. 다른 요소를 추가하면 대기열 꼬리는 0 첨자로 다시 이동합니다. 계속 추가하면 대기열 꼬리 첨자가 대기열 헤드 첨자에서 1을 뺀 값과 같을 때 대기열이 가득 차서 더 이상 요소가 없는 것으로 간주합니다. 추가될 수 있습니다.

마찬가지로, dequeue할 때 team head 요소도 주기적으로 작동합니다. team head 요소가 6의 첨자에 도달하면 계속해서 dequeue하면 0의 첨자 위치로 돌아가서 계속해서 dequeue됩니다. 큐의 선두와 꼬리의 값이 동일할 경우, 현재 큐는 빈 큐로 판별될 수도 있습니다.

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

define(&#39;MAX_QUEUE_LENGTH&#39;, 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, &#39;A&#39;);
EnSqQueueLoop($q, &#39;B&#39;);
EnSqQueueLoop($q, &#39;C&#39;);
EnSqQueueLoop($q, &#39;D&#39;);
EnSqQueueLoop($q, &#39;E&#39;);

EnSqQueueLoop($q, &#39;F&#39;);

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, &#39;F&#39;);
EnSqQueueLoop($q, &#39;G&#39;);

EnSqQueueLoop($q, &#39;H&#39;);
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, &#39;A&#39;);
EnLinkQueue($q, &#39;B&#39;);
EnLinkQueue($q, &#39;C&#39;);
EnLinkQueue($q, &#39;D&#39;);
EnLinkQueue($q, &#39;E&#39;);

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, &#39;F&#39;);
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 为我们提供的数组队列操作

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

$sqQueueList = [];

array_push($sqQueueList, &#39;a&#39;);
array_push($sqQueueList, &#39;b&#39;);
array_push($sqQueueList, &#39;c&#39;);

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 rabbitmq 循环指针数据结构栈对象算法 redis 数据库

성명：

이 기사는 segmentfault.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제

이전 기사：PHP의 연결리스트에 대한 자세한 설명다음 기사：PHP의 연결리스트에 대한 자세한 설명