PHP는 대기열 기능을 구현합니다 : 두 개의 스택으로 대기열 작업을 최적화하는 효율적인 방법

소개

대기열은 FIFO (First-In-First-Out)의 원리를 따르는 널리 사용되는 데이터 구조입니다. PHP의 배열은 대기열 기능을 구현할 수 있지만 어레이를 직접 조작하면 효율이 감소 될 수 있습니다. 이 기사에서는 두 개의 스택 구조를 사용하여 효율적인 큐 작업을 달성하고 프로그램 성능을 향상시키는 방법을 설명합니다.

스택의 기본 개념

스택은 최후의 첫 번째 출력 (LIFO)이있는 데이터 구조이며 주요 작업에는 푸시 및 팝핑이 포함됩니다. 스택 상단에 요소를 밀고 스택 상단에 요소를 제거하면 요소를 제거하십시오.

두 스택에 대한 대기열 구현 아이디어

큐는 두 개의 스택을 통해 구현되며, 하나는 입력 스택으로 요소 eNqueue를 담당하고 다른 하나는 출력 스택으로 요소 dequeue를 담당합니다. 출력 스택이 비어 있으면 입력 스택의 요소가 하나씩 튀어 나와 출력 스택으로 밀려서 첫 번째 최초의 큐 동작을 달성합니다.

대기열 작업에 가입하십시오

입력 작업은 비교적 간단합니다. 요소를 입력 스택으로 밀어 넣으십시오.

 class Queue {
    private $inputStack = [];
    private $outputStack = [];

    public function enqueue($item) {
        array_push($this->inputStack, $item);
    }
}

출발 작전

큐 작업은 먼저 출력 스택이 비어 있는지 여부를 결정합니다. 비어 있으면 입력 스택의 모든 요소를 팝업하여 출력 스택으로 밀고 출력 스택에서 요소를 팝업하십시오. 비어 있지 않으면 출력 스택에서 요소를 직접 팝업하십시오.

 public function dequeue() {
    if (empty($this->outputStack)) {
        while (!empty($this->inputStack)) {
            array_push($this->outputStack, array_pop($this->inputStack));
        }
    }
    if (!empty($this->outputStack)) {
        return array_pop($this->outputStack);
    }
    return null;
}

샘플 코드

다음 예제는 두 개의 스택을 사용하여 큐의 기본 작동을 구현하는 방법을 보여줍니다.

 $queue = new Queue();
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
echo $queue->dequeue(); // 산출1
echo $queue->dequeue(); // 산출2
echo $queue->dequeue(); // 산출3

요약

두 개의 스택을 사용하여 대기열을 구현하면 자주 배열 이동으로 인한 성능 문제를 효과적으로 피할 수 있습니다. 팀에 합류하는 운영은 간단하고 효율적이며 출발시 요소 전송을 통해 첫 번째 최초의 기능이 보장됩니다. 추가 스택 공간이 필요하지만 대기열 작업의 전체 실행 효율이 향상되며 많은 양의 데이터를 처리 할 때 큐 작업에 특히 적합합니다.