■スタック
スタックとは
順列において、最初に挿入されたデータが最後に取り出される。最後に挿入したデータが最初に取り出されるデータ構造。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