キューもスタックもデータ型の一種で、先に入れた値が先に出てくるのがキュー、後で入れた値が先に出てくるのがスタックです。
キューが底のない筒で、スタックがコップのように底のあるものと考えるとわかりやすいでしょう。
PHPにとってはどちらも配列の一種で、array_push()、array_pop()あたりを使えば簡単に実装できます。
queue.class.php
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
//キュー
class Queue implements Iterator{
//配列置き
protected $arr=array();
//イテレータ
protected $loop=0;
//コンストラクタ
function __Construct(){}
//エンキュー
function enqueue($val){
array_push($this->arr,$val);
}
//デキュー
function dequeue(){
return array_shift($this->arr);
}
//イテレータ
function current(){
return $this->arr[$this->loop];
}
function next(){
$this->loop++;
}
function key(){
return $this->loop;
}
function rewind(){
$this->loop=0;
}
function valid(){
if(isset($this->arr[$this->loop])){
return true;
}else{
return false;
}
}
#↓クラスのおわり
}
//スタック
class Stack extends Queue{
//push
function push($val){
array_unshift($this->arr,$val);
}
//pop
function pop(){
return array_shift($this->arr);
}
#↓クラスのおわり
}
|
例によってエラー処理は作ってません。
キューを作ってしまえばスタックはほぼ同じなのでスタックもついでに作成しました。
入れる順番変えるだけですし。
ただこういう書き方をした場合、スタックからでもキューのメソッドを使えてしまえるのであまりよくありません。
共通のメソッドを集めた基底クラスを作ってそこからextendsしたほうがいいでしょう。
むしろどちらとしても使えるクラスが一個あれば十分という気もしないでもないですが。
使用時は普通にpush、pop、enqueue、decueするだけです。簡単。
queue.php
1
2
3
4
5
6
7
8
9
10
11
12
|
require_once('queue.class.php');
$stack=new Stack();
$stack->push(5);
$stack->push(4);
$stack->push(3);
$stack->pop();
foreach($stack as $key=>$val){
var_dump($val);
}
|
さて、PHP5.3でキュー、スタッククラスが実装されました。
http://jp.php.net/manual/ja/class.splstack.php
http://jp.php.net/manual/ja/class.splqueue.php
どう見てもSplQueue extends SplStackとしか思えない。
あと、PHPの配列って元々キューなのであまり意味がない気もしないでもない。
PR
トラックバック
トラックバックURL:
