@blog.justoneplanet.info

日々勉強

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

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

No comments yet.

RSS feed for comments on this post.TrackBack URL

Leave a comment