SplStackとSplQueueで配列のpush/popをやめる

Bynori

SplStackとSplQueueは、配列のarray_push/array_popやarray_shift/array_unshiftの代わりに、スタックとキューを明示的な型として扱うためのSPLクラスです。

スタックもキューも、配列があれば一応作れてしまいます。だから業務コードでもほとんどの人は配列で済ませていると思います。ただ、意図が配列という汎用の箱に埋もれてしまうのが気になっていて、最近はSplStackとSplQueueを使う場面が増えました。今日はその使い分けと、地味にハマったところを書いておきます。

SplStackとSplQueueは何が違うのか

どちらもSplDoublyLinkedList(二重リンクリスト)を継承したクラスです。違いは反復(foreach)したときの向きだけで、要素の出し入れ自体は同じ土台の上に乗っています。SplStackは後入れ先出し(LIFO)、SplQueueは先入れ先出し(FIFO)でイテレーションされるように、コンストラクタが内部のイテレータモードを固定しています。

$stack = new SplStack();
$stack->push('a');
$stack->push('b');
$stack->push('c');

foreach ($stack as $v) {
    echo $v; // cba (後から積んだものが先に出る)
}

$queue = new SplQueue();
$queue->push('a');
$queue->push('b');
$queue->push('c');

foreach ($queue as $v) {
    echo $v; // abc (積んだ順のまま出る)
}

push()で積んでいる点はどちらも同じで、foreachしたときの順番だけが変わっているのがポイントです。配列だと「取り出す側のコード」が向きを決めていましたが、SplStackとSplQueueでは「箱の種類」が向きを決めます。読む側はクラス名を見るだけで意図がわかる、というのがこの2つを使う一番の理由だと思っています。

キューらしく書くならenqueue/dequeue

SplQueueにはpush()やpop()もそのまま継承されていて呼べてしまいますが、これを使うとスタックのように振る舞ってしまいます。キューとして使うつもりなら、専用のエイリアスメソッドを使ったほうが事故が減ります。

$queue = new SplQueue();
$queue->enqueue('first');
$queue->enqueue('second');
$queue->enqueue('third');

echo $queue->dequeue(); // first
echo $queue->dequeue(); // second

enqueue()はSplDoublyLinkedList::push()の、dequeue()はSplDoublyLinkedList::shift()のエイリアスです。中身は同じ処理ですが、名前が意図と一致しているので、あとでコードを読み返したときに「これはキューとして使っている」とすぐわかります。push()/pop()の組み合わせで書いてしまうと、うっかりキューのつもりがスタック動作になっていた、という取り違えが起きるので注意が必要です。

なぜ配列のarray_shiftではダメなのか

配列でキューを作ると、array_shift()で先頭を取り出すたびに残りの要素のインデックスが全部詰め直されます。要素数が多いキューを大量に出し入れする処理では、この詰め直しコストが積み重なって無視できなくなることがあります。SplQueueは二重リンクリストなので、先頭・末尾の追加削除がインデックスの再構築を伴わず、計算量の面で有利です。

逆に言うと、要素数が少ない・出し入れの回数が少ないなら配列で十分で、無理にSplQueueへ置き換える必要はありません。パフォーマンスよりも「型で意図を表す」ことのほうが自分にとっては動機として大きいです。

isEmpty()での終了判定を忘れない

SplStackとSplQueueはArrayAccessやCountableも実装しているので、count()や添字アクセスもできます。ただ、キューを空になるまで処理するようなループでは、isEmpty()を使うのが素直です。

$queue = new SplQueue();
$queue->enqueue('task1');
$queue->enqueue('task2');

while (!$queue->isEmpty()) {
    $task = $queue->dequeue();
    echo $task . "\n";
}

空のSplStack/SplQueueに対してpop()やdequeue()、あるいはtop()やbottom()を呼ぶとRuntimeExceptionが投げられます。配列なら空でもarray_shift()は静かにnullを返すだけなので、この違いを知らずに移行すると、思わぬところで例外が飛んで戸惑うことになります。ループの終了条件はisEmpty()で書いておくのが安全です。

まとめ

SplStackとSplQueueは、内部的にはどちらも同じ二重リンクリストで、違いはイテレーションの向きとメソッド名のエイリアスだけです。それでも、配列でスタックやキューを表現するより、クラス名とメソッド名が意図をそのまま語ってくれるぶん、あとから読むときの負担が減ります。空チェックの挙動が配列と違って例外を投げてくる点だけ覚えておけば、置き換える価値は十分にあると思います。

よくある質問

Q. SplStackとSplQueueはどちらも配列より遅いのでは?
A. 要素数や操作の頻度によります。先頭からの追加削除を多用するキューの用途では、配列のインデックス再構築が発生しない分、SplQueueのほうが有利になる場面があります。少量データでは体感差はほとんどありません。

Q. SplQueueでpush()を使うと何が起きますか?
A. push()はSplDoublyLinkedList由来のメソッドで末尾に追加するだけなので、それ自体はenqueue()と同じ動作です。ただしpop()を組み合わせると末尾から取り出すことになり、キューではなくスタックとして動いてしまいます。

Q. 空のSplQueueをdequeue()するとどうなりますか?
A. RuntimeExceptionが投げられます。配列のarray_shift()のようにnullが返るわけではないので、ループの終了条件はisEmpty()で判定するようにします。

類似投稿

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です