@blog.justoneplanet.info

■スタック

スタックとは

順列において、最初に挿入されたデータが最後に取り出される。最後に挿入したデータが最初に取り出されるデータ構造。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';
?>

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()を用いる。

■集合と配列の比較

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

和集合

集合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)
}
*/
?>