PHPはキュー機能を実装しています：2つのスタックでキュー操作を最適化する効率的な方法

gitbox 2025-07-23

導入

キューは、ファーストインファーストアウト（FIFO）の原則に従う広く使用されているデータ構造です。 PHPの配列はキューイング機能を実装できますが、配列の直接操作により効率が低下する場合があります。この記事では、2つのスタック構造を使用して効率的なキュー操作を実現し、プログラムのパフォーマンスを向上させる方法について説明します。

スタックの基本概念

Stackは、最後のファーストアウト（LIFO）を備えたデータ構造であり、その主な操作にはプッシュとポップが含まれます。要素をスタックの上部に押し込み、外出中に要素をスタックの上部に削除します。

2つのスタックのキューを実装するためのアイデア

キューは2つのスタックを介して実装されます。1つは入力スタックとして要素エンキューの責任を負い、もう1つは出力スタックとして要素デキューの責任を負います。出力スタックが空になると、入力スタックの要素が1つずつ飛び出して出力スタックに押し込まれ、それにより、ファーストでファーストアウトキューの動作が実現されます。

キュー操作に参加してください

エントリ操作は比較的単純です。要素を入力スタックに押し込むだけです。

 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;
}

サンプルコード

次の例は、2つのスタックを使用してキューの基本操作を実装する方法を示しています。

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

要約します

2つのスタックを使用してキューを実装すると、頻繁なアレイの動きによって引き起こされるパフォーマンスの問題を効果的に回避できます。チームへの参加の操作はシンプルで効率的であり、ファーストインファーストアウト機能は、出発時に要素転送を通じて保証されます。追加のスタックスペースが必要ですが、キュー操作の全体的な実行効率が改善され、大量のデータを処理する際のキュー操作に特に適しています。