지역 사회 배우다 도구 라이브러리 여가
찾다
한국어
집 > 백엔드 개발 > PHP 문제 > 본문

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

醉折花枝作酒筹
풀어 주다： 2023-03-11 19:22:01
앞으로
5975명이 탐색했습니다.

오늘은 또 다른 매우 고전적인 논리 구조 유형인 대기열을 배워보겠습니다. 나는 많은 학생들이 이미 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, '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
// )
로그인 후 복사

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

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

원형 대기열

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

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

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

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

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

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

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 为我们提供的数组队列操作

最后，就和栈一样，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
원천：segmentfault.com
이전 기사：PHP의 연결리스트에 대한 자세한 설명 다음 기사：PHP의 스택에 대한 자세한 설명
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
URL 매개변수에서 얻은 PHP 배열이 예상대로 작동하지 않습니다. 카테고리 ID가 포함된 URL 매개변수가 있고 이를 다음과 같은 배열로 처리하려고 합니다. http://example.com?cat[]=3,9,13 PHP에서는 ...
에서 2024-04-06 22:09:02
0
1
1428
Apache에서 CustomLog 지시문을 어디에 배치해야 합니까? 저는 php:7.2-apachedocker를 사용하고 있습니다. 상태 확인 URL 로그인 액세스 로그를 비활성화해야 합니다. 이 링크를 기반으로 Customlog...
에서 2024-04-06 22:03:59
0
1
990
반환 값의 변수 형식은 무엇입니까? 저는 PHP를 처음 배우는 사람입니다. 코드 조각을 찾았습니다: if($x<time()){return[false,'error'];} 논리나 변수는 중요하지 ...
에서 2024-04-06 21:55:20
0
1
778
opentbs를 사용하여 odt 파일을 생성할 때 발생하는 문제: 동일한 키의 값이 별도의 열이 아닌 동일한 행에 표시됩니다. PHP를 사용하여 odt를 만들기 위해 OpenTbs라는 라이브러리를 사용하고 있는데, 열과 행이 동적으로 생성되기 때문에 사용하고 있습니다. 행과 열을 만드는 ...
에서 2024-04-06 20:18:18
0
1
483
루프 오버를 위해 ID별로 MySQL 결과 그룹화 mysql에 비행 데이터가 포함된 테이블이 있습니다. codeigniter3 travel_idair_idFlightDurationout_or_inflightdur...
에서 2024-04-06 17:27:56
0
1
406
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿