@blog.justoneplanet.info

日々勉強

PHP Arrays as Stacks, Queues and Set(スタック・待ち行列・和集合)

■スタック

スタックとは

順列において、最初に挿入されたデータが最後に取り出される。最後に挿入したデータが最初に取り出されるデータ構造。LIFO(last in first out)と呼ばれる。

実際のコード

以下のようにarray_push関数を使用すると、第一引数の配列の最後尾に第二引数以降の値を、配列の要素として追加する。また、array_pop関数を使用すると、配列の最終要素を削除し戻り値として返します。

<?php
$stack = array();
array_push($stack, 'John', 'Jack');
var_dump($stack);
/*
array(2) {
  [0]=>
  string(4) "John"
  [1]=>
  string(4) "Jack"
}
*/
$value = array_pop($stack);
var_dump($value);
var_dump($stack);
/*
string(4) "Jack"
array(1) {
  [0]=>
  string(4) "John"
}
*/
?>

但し、array_pushについては以下のようなコードでも同じようなことができる。そして、関数をコールするオーバーヘッドが発生しない分だけわずかに高速である。

<?php
$stack = array();
$stack[] = 'John';
$stack[] = 'Jack';
?>
各関数について
int array_push(array &$ary, mixed $var[, mixed $var, …])
$aryの最後に、第二引数以降の値を配列の要素として追加する。
mixed array_pop(array &$ary)
配列の最後から要素を取り除き、その値を返す。

ちなみにJavaScriptで以下のように書いてしまうと、シンタックスエラーとなる。

var tmpAry[] = 'test';
//syntax error!!

■キュー(待ち行列)

待ち行列とは

データが順列に挿入された順序で、削除(処理)されていくようなデータ構造。FIFO(first in first out)と呼ばれる。

実際のコード

以下のように、array_shift関数を使うと第一引数で指定した配列の最初の要素を削除できる。また、array_unshift関数を使うと第一引数で指定した配列に、第二引数以降の要素を代入することができる。

<?php
$queue = array('John', 'Ken', 'Mike');
$value = array_shift($queue);
var_dump($value);//John
var_dump($queue);
/*
array(2) {
  [0]=>
  string(3) "Ken"
  [1]=>
  string(4) "Mike"
}
*/
array_unshift($queue, 'Nick', 'Emily');
var_dump($queue);
/*
array(4) {
  [0]=>
  string(4) "Nick"
  [1]=>
  string(5) "Emily"
  [2]=>
  string(3) "Ken"
  [3]=>
  string(4) "Mike"
}
*/
?>

shiftとunshiftを使うとスタックと変わらない。従ってキューの実装にはarray_shift()とarray_push()を用いる。

各関数について
mixed array_shift(array &$ary)
配列の先頭から要素を一つ取り出し、その値を返す。
int array_unshift(array &$ary, mixed $var[, mixed $var])
第一引数の配列に、第二引数以降の値を配列の要素として加える。

■集合と配列の比較

集合とは、いくつかの要素の集まったデータ構造。配列を使用すると、集合論の基本となる和集合や積集合、対象差といった演算を実装できる。

和集合

集合Aと集合Bを結合し、重複を取り除いた集合。

<?php
$a = array(1, 5, 3, 9);
$b = array(2, 5, 9, 7);
$tmpAry = array_merge($a, $b);
$set = array_unique($tmpAry);
var_dump($set);
/*
array(6) {
  [0]=>
  int(1)
  [1]=>
  int(5)
  [2]=>
  int(3)
  [3]=>
  int(9)
  [4]=>
  int(2)
  [7]=>
  int(7)
}
*/
?>

配列(集合)の差分

array_diff関数を使うと配列の差を計算することができる。以下のような場合、第一引数の配列の要素で、第二引数以降の配列に含まれて居ない要素を配列として返す。

<?php
$a = array(1, 3, 9, 27);
$b = array(1, 9, 2, 7);
var_dump(array_diff($a, $b));
/*
array(2) {
  [1]=>
  int(3)
  [3]=>
  int(27)
}
*/
?>

また、配列の比較においてキーまで含める場合は以下のように、array_diff_assoc関数を使用する。

<?php
$a = array(1, 3, 9, 27);
$b = array(1, 9, 2, 7);
var_dump(array_diff_assoc($a, $b));
/*
array(3) {
  [1]=>
  int(3)
  [2]=>
  int(9)
  [3]=>
  int(27)
}
*/
?>

配列(集合)の共通項

array_intersect関数は以下のように、配列の共通項のリストを返す。

<?php
$a = array(1, 3, 9, 27);
$b = array(1, 9, 2, 7);
var_dump(array_intersect($a, $b));
/*
array(2) {
  [0]=>
  int(1)
  [2]=>
  int(9)
}
*/
?>

各関数について

array array_merge(array $ary[, array $ary2])
複数の配列をマージし結果を返す。但し、連想配列の文字列が重複している場合は値が上書きされる。
array array_unique(array $ary[, int $sort_flags=SORT_REGULAR])
配列から重複を取り除いた配列を返す。
array array_diff(array $ary1, array $ary2)
$ary1の要素のうち$ary2に含まれないものを配列として返す。
array array_intersect(array $ary1, array $ary2)
配列の共通項を配列として返す。

コメントはまだありません»

No comments yet.

RSS feed for comments on this post.TrackBack URL

Leave a comment