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