JavaScriptでデータ構造を実装したい！ (スタック・キュー・ヒープ実装編)

JavaScript

前回の記事「JavaScriptでデータ構造を実装したい！ (基本編)」ではJavaScriptでデータ構造を実装するために必要な知識をまとめたので、今回は実際にJavaScriptでスタック・キュー・ヒープを実装してみます。

まずはスタック・キューの実装ですがJavaScriptの配列には先頭や末尾の要素を出し入れするメソッドがあるのでスタック・キューは実装する必要がありません。しかし普段C++を使ってプログラミングコンテストに参加している感覚と同じようにスタック・キューを使うを使うためにメソッド名を同じにして使いやすくしてみましょう。
スタック

Stack.prototype.push = function (val) {
    this.data.push(val);
    return val;
}
Stack.prototype.pop = function () {
    return this.data.pop();
}
Stack.prototype.top = function () {
    return this.data[this.data.length - 1];
}
Stack.prototype.size = function () {
    return this.data.length;
}
Stack.prototype.empty = function () {
    return this.data.length == 0;
}

// 例
var st = new Stack();
st.push(1); // [] => [1]
st.push(2); // [1] => [1, 2]
st.push(3); // [1, 2] => [1, 2, 3]
st.empty(); // false
st.pop(); // [1, 2, 3] => [1, 2]
st.size(); // 2

キュー

function Queue() {
    this.data = [];
}
Queue.prototype.push = function (val) {
    this.data.push(val);
    return val;
}
Queue.prototype.pop = function () {
    return this.data.shift();
}
Queue.prototype.front = function () {
    return this.data[0];
}
Queue.prototype.size = function () {
    return this.data.length;
}
Queue.prototype.empty = function () {
    return this.data.length == 0;
}

// 例
var q = new Queue();
q.push(1); // [] => [1]
q.push(2); // [1] => [1, 2]
q.front(); // 1 
q.push(3); // [1, 2] => [1, 2, 3]
q.pop(); // [1, 2, 3] => [2, 3]
q.pop(); // [2, 3] => [3]
q.size(); // 1
q.pop(); // [3] => []

メソッド名が同じなのでほとんどC++と同じようにプログラミングコンテストで使うことができそうです。(ただし、空の時にpopしようとしたときなどC++とJavaScriptで動作が異なる操作は存在する)

最後にヒープを実装してみましょう。ヒープ(二分ヒープ)は優先度付きキューの実装によく使われており、最小値(最大値)を効率よく取り出すことができるデータ構造です。ヒープの実装は二分木でなく実際には配列で実装するのが一般的のようです。ヒープの実装はプログラミングコンテストチャレンジブックp.71を参考にしてつくりました。
ヒープ

function Heap () {
    this.heap = new Array();
    this.size = 0;
}
Heap.prototype.push = function (val) {
    var k = this.size++;

    while( 0 < k ) {
        var p = Math.floor( (k - 1) / 2 );
        
        if( this.heap[p] <= val ) break;
        
        this.heap[k] = this.heap[p];
        k = p;
    }
    this.heap[k] = val;
}
Heap.prototype.pop = function () {
    var ret = this.heap[0];
    var x = this.heap[--this.size];
	
    var k = 0;
    while( k * 2 + 1 < this.size ) {
        var a = k * 2 + 1;
        var b = k * 2 + 2;
        if( b < this.size && this.heap[b] < this.heap[a] ) a = b;
		
        if( x <= this.heap[a] ) break;

        this.heap[k] = this.heap[a];
        k = a;
    }
    this.heap[k] = x;
    return ret;
}
Heap.prototype.top = function () {
    return this.heap[0];
}
Heap.prototype.size = function () {
    return this.size;
}

// 例
q.push(3);
q.push(7);
q.push(6);
q.push(-7);
q.push(2);
q.push(8);
q.pop(); // => -7 (最小値が出てくる)
q.pop(); // => 2
q.pop(); // => 3
q.pop(); // => 6

JavaScriptでスタック・キュー・ヒープが実装できたので解ける問題が増えると思います。次回は「JavaScriptでデータ構造を実装したい！ (連想配列編)」です。(準備中)