PHPで競技プログラミングをする時などにQueueやStackを使う場合があると思います。PHPのStackとQueueについて紹介していきます。
Stack
arrayを使って実装
PHPのarrayは高機能で、array_push
, array_pop
メソッドを使ってStackを実装することができます。
<?php class Stack { private $array = []; public function push($v) { array_push($this->array, $v); } public function pop() { return array_pop($this->array); } } $s = new Stack(); $s->push(1); $s->push(2); var_dump($s->pop()); // => int(2) var_dump($s->pop()); // => int(1) var_dump($s->pop()); // => NULL
SplStackを使う
SplStackというものもあります。
$s = new SplStack(); $s->push(1); $s->push(2); var_dump($s->pop()); // => int(2) var_dump($s->pop()); // => int(1) var_dump($s->pop()); // => PHP Fatal error: Uncaught exception 'RuntimeException' with message 'Can't pop from an empty datastructure'
Queue
arrayを使って実装
array_push
と array_shift
を使って実装できます。
class Queue { private $array = []; public function enqueue($v) { array_push($this->array, $v); } public function dequeue() { return array_shift($this->array); } } $q = new Queue(); $q->enqueue(1); $q->enqueue(2); var_dump($q->dequeue()); // => int(1) var_dump($q->dequeue()); // => int(2) var_dump($q->dequeue()); // => NULL
SplQueue を利用
$q = new SplQueue(); $q->enqueue(1); $q->enqueue(2); var_dump($q->dequeue()); // => int(1) var_dump($q->dequeue()); // => int(2) var_dump($q->dequeue()); // => Uncaught exception 'RuntimeException' with message 'Can't shift from an empty datastructure'