@blog.justoneplanet.info

JavaScript、PHP、MySQLを使ったり

JavaScript Arrays as Stacks and Queues（スタック・待ち行列）

■スタック

スタックとは

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

実際のコード

以下のようにpush()メソッドを使用すると、引数を配列の要素として追加する。また、pop()メソッドを使用すると、配列の最終要素を削除し戻り値として返します。

var ary = [];
ary.push('John', 'Jack');
alert(ary);//John,Jack
var name = ary.pop();
alert(ary);//John
alert(name);//Jack

応用

Stackを固定長とする時、以下の様なコードが良いかもしれない。

var undefined;
function Stack(n){
    this._ary = new Array();
    this._length = n;
}
Stack.prototype = {
    "isEmpty" : function(){
        if(this._ary.length === 0){
            return true;
        }
        else{
            return false;
        }
    },
    "isFull" : function(){
        if(this._ary.length === this._length){
            return true;
        }
        else{
            return false;
        }
    },
    "push" : function(elm){
        if(this.isFull()){
            throw new Error('Stack is full : Stack.push(' + elm + ')');
        }
        else{
            this._ary.push(elm);
        }
    },
    "pop" : function(){
        var obj;
        if(this.isEmpty()){
            throw new Error('Stack is empty : Stack.pop');
        }
        else{
            obj = this._ary.pop();
            return obj;
        }
    },
    "size" : function(){
        return this._ary.length;
    },
    "length" : function(){
        return this._length;
    },
    "top" : function(){
        if(this.isEmpty()){
            throw new Error('Stack.top');
        }
        else{
            return this._ary[this._ary.length - 1];
        }
    },
    "toString" : function(){
	    return '[' + this._ary.join + ']';
    }
}
var tmp = new Stack(3);
tmp.push(1);
tmp.push(2);
tmp.push(3);
//tmp.push(4);//full
alert('top : ' + tmp.top());//3
alert('size : ' + tmp.size());//3
alert(tmp.pop());//3
alert(tmp.pop());//2
alert(tmp.pop());//1
alert('size : ' + tmp.size());//0
//alert(tmp.pop());//empty
//tmp.sort();//error

当然ながら実装されていないメソッドは使えない。

コンストラクタはfunctionで、その他メンバはprototypeで書くのが綺麗な気がする。

■キュー（待ち行列）

待ち行列とは

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

実際のコード

以下のように、shift()メソッドを使うと配列の最初の要素を削除できる。また、unshift()メソッドを使うと引数を要素として挿入することができる。

var ary = ['John', 'Ken', 'Mike'];
name = ary.shift();
alert(ary);//Ken,Mike
alert(name);//John
ary.unshift('Nick', 'Emily');
alert(ary);//Nick,Emily,Ken,Mike

shiftとunshiftを使うとスタックと変わらない。従ってキューの実装には以下のようにshiftとpushを用いる。

応用

var undefined;
function Queue(n){
    this._ary = new Array();
    this._length = n;
}
Queue.prototype = {
    "isEmpty" : function(){
        if(this._ary.length === 0){
            return true;
        }
        else{
            return false;
        }
    },
    "isFull" : function(){
        if(this._ary.length === this._length){
            return true;
        }
        else{
            return false;
        }
    },
    "enqueue" : function(elm){
        if(this.isFull()){
            throw new Error('Queue is full : Queue.enqueue(' + elm + ')');
        }
        else{
            this._ary.push(elm);
        }
    },
    "dequeue" : function(){
        if(this.isEmpty()){
            throw new Error('Queue is empty : Queue.dequeue');
        }
        else{
            return this._ary.shift();
        }
    },
    "size" : function(){
        return this._ary.length;
    },
    "length" : function(){
        return this._length;
    },
    "top" : function(){
        if(this.isEmpty()){
            return new Error();
        }
        else{
            return this._ary[this._ary.length - 1];
        }
    },
    "toString" : function(){
	    return '[' + this._ary.join + ']';
    }
}
var tmp = new Queue(3);
tmp.enqueue(3);
tmp.enqueue(2);
tmp.enqueue(1);
//tmp.enqueue(0);//full
alert('top : ' + tmp.top());//3
alert('size : ' + tmp.size());//3
alert(tmp.dequeue());//3
alert(tmp.dequeue());//2
alert(tmp.dequeue());//1
alert('size : ' + tmp.size());//0
//alert(tmp.dequeue());//empty

JavaScript Array Basic（配列の基本）

配列とは値を順序づけしたもので、個々の値を要素、各要素に割り当てる番号をインデックスと呼ぶ。但し、内部的にJavaScriptにおける配列とはオブジェクトを拡張したものである。

var tmpAry = new Array();
alert(typeof tmpAry);//object

■配列の生成

配列リテラルを使用

var ary = ['John', 'Jack', 'Nick'];

Arrayコンストラクタを使用

var ary = new Array('John', 'Jack', 'Nick');

但し、以下のように1個の数字を引数に指定した場合は、引数で指定した個数の未定義値の値の要素を持つ配列が生成される。

var ary = new Array(5);

■要素へのアクセス

var ary = ['John', 'Jack', 'Nick'];
ary[3] = 'Mike';
ary['3'] = 'Emily';
alert(ary);//John,Jack,Nick,Emily

■要素の追加

以下のようにして要素を追加することができる。インデックスは連続した値である必要はなく、メモリ上に使用していないインデックスが確保される事もない。

var ary = ['John', 'Jack', 'Nick'];
ary[101] = 'Pochi';
for(var i = 0; i< ary.length; i++){
    alert(ary[i]);
}
//102 times alerts

但し、lengthは最後のインデックス+1が格納され、上述のようなコードではループが最後のインデックスまで1ずつ実行される。

■要素の削除

以下のようにdelete演算子を使うこともできるが、undefinedが入り要素自体は削除されない。

var undefined;//for browsers not implementing the type 'undefined'
var ary = ['John', 'Jack', 'Nick'];
delete ary[1];
alert(ary);//John,,Nick
alert(ary.length);//3
for(var i = 0; i < ary.length; i++){
    if(typeof ary[i] === undefined){
        alert('undefined');
    }
    else{
        alert(ary[i]);
    }
}
/*
John,undefined,Nick
*/

■lengthプロパティ

以下のように配列の長さより小さな値を代入し配列を切り詰めることができる。

var ary = ['John', 'Jack', 'Nick'];
ary.length = 2;
alert(ary);//John,Jack

以下のように配列の長さより大きな値を代入し配列を拡張することができる。

var ary = ['John', 'Jack', 'Nick'];
ary.length = 4;
alert(ary);//John,Jack,Nick,

代入することが出来るのは基本的には数値のみである。

var ary = ['John', 'Jack', 'Nick'];
ary.length = {};
//syntax error