JavaScript による一番簡単なスタックとキューの実装方法

JavaScript の Array オブジェクトには配列の先頭要素の取り出し (shift)、最後尾要素への追加 (push)、 最後尾要素の取り出し (pop) 等の操作が実装されています。

Array の持つメソッドだけを使って、スタック及びキューを実装してみましょう。

スタックの実装

スタックは LIFO (Last In First Out) のデータ構造です。つまり、１，２，３ の順番で、 スタックにデータをプッシュすると、取り出すデータは３，２，１ の順番で出てきます。

慣例的に、スタックにデータを入れる操作を push, データを取り出す操作を pop といいます。 JavaScript の Array オブジェクトには既に push, pop が実装されていますから、それをそのまま使いましょう。

クラスの定義方法に不慣れな人は、当サイトの JavaScript によるオブジェクト指向プログラミング を見てください。

//
// Stack (LIFO)
//

function Stack() {
	this.__a = new Array();
}

Stack.prototype.push = function(o) {
	this.__a.push(o);
}

Stack.prototype.pop = function() {
	if( this.__a.length > 0 ) {
		return this.__a.pop();
	}
	return null;
}

Stack.prototype.size = function() {
	return this.__a.length;
}

Stack.prototype.toString = function() {
	return '[' + this.__a.join(',') + ']';
}

定義は以上です。内部変数として Array オブジェクトを持ちます。 push, pop メソッドはデータの出し入れ、size メソッドは現在のデータ数、 そして toString メソッドはデータ構造中のデータを JSON 形式でダンプします。

テストコードは次のようになります。

//
// Stack の動作確認
//

var i;
var s = new Stack();
s.push(1);
s.push(2);
s.push(3);
alert( s.toString() );

while( i = s.pop() ) {
	alert( i );
}

キューの実装

キューは FIFO のデータ構造です。ところてん方式に、先に入れたのが取り出せます。 １，２，３ の順番でデータを格納すれば、取り出すのも１，２，３ の順番です。

慣例的にキューにデータを入れる操作を、push とか enqueue、データを取り出す操作を get とか dequeue といいます。Array オブジェクトのメソッドで言えば、前者は push、 後者は shift メソッドに対応します。

//
// Queue (FIFO)
//

function Queue() {
	this.__a = new Array();
}

Queue.prototype.enqueue = function(o) {
	this.__a.push(o);
}

Queue.prototype.dequeue = function() {
	if( this.__a.length > 0 ) {
		return this.__a.shift();
	}
	return null;
}

Queue.prototype.size = function() {
	return this.__a.length;
} 

Queue.prototype.toString = function() {
	return '[' + this.__a.join(',') + ']';
}

以上が定義です。テストコードは以下の通りです。

//
// Queue の動作確認
//

var i;
var q = new Queue();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
alert( q.toString() );

while( i = q.dequeue() ) {
	alert( i );
}