データ構造の選択次第で天国と地獄の差：コーディングに役立つ！アルゴリズムの基本（2）（1/3 ページ）

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

» 2008年09月01日 00時00分公開

[山下寛人，オイシックス株式会社]

　第1回「いまさらアルゴリズムを学ぶ意味」では、アルゴリズムを学ぶ意味を解説しました。今後紹介していくアルゴリズムは、データの集合を処理していくものが多数あります。そこで、先にデータ構造についておさらいしていきたいと思います。なぜならば、同じ処理を行う場合でもデータ構造をどうするかによってプログラムの難易度やパフォーマンスに大きな違いが出てくるからです。

　解説のための言語は、引き続きJavaScriptを使います。JavaScriptを学ぶことが目的でないため、なるべくJavaScriptに依存しない、ほかの言語でも同じように記述できるようなコードを提示しますが、試しに実行する場合はWebブラウザでJavaScriptとして実行するとよいでしょう。あくまで概要を理解するのが目的のため、エラーチェックなどは省略しています。

基本中の基本、配列

　配列は簡単にいうと、変数に番号（インデックス）を付けて扱えるようにするものです。

var hairetsu = new Array();
hairetsu[0] = 1;
hairetsu[1] = 2;
hairetsu[2] = 3;
document.write("0番目のhairetsuは" + hairetsu[0] + "<br/>");

　インデックスに変数を使うこともできます。

var num = 1;
document.write(num + "番目のhairetsuは" + hairetsu[num] + "<br/>");

　同じ種類の変数が多数あるときに、単一の変数しかないと取り扱いが大変になります。例えば3つの数値を合計する場合、以下のようなプログラムになるでしょう。

var a1 = 1;
var a2 = 2;
var a3 = 3;
document.write(a1 + a2 + a3);

　このサンプルのように変数が3つ程度ならまだいいですが、100個、1000個となると合計する部分のプログラムがどんどん長くなります。

　配列を利用するとデータをまとめて取り扱うことができます。

var hairetsu = new Array();
hairetsu[0] = 1;
hairetsu[1] = 2;
hairetsu[2] = 3;
var sum = 0;
for (i in hairetsu) {
  sum += hairetsu[i];
}
document.write(sum);

　配列の中に配列を持たせることもできます。二重になっているものを二次元配列、三重になっているものを三次元配列と呼びます。二次元以上の配列を多次元配列といいます。

var tajigen = new Array();
tajigen[0] = new Array();
tajigen[0][0] = 0;
tajigen[0][1] = 1;
tajigen[1] = new Array();
tajigen[1][0] = 10;
tajigen[1][1] = 11;
document.write(tajigen.join("/"));

後入れ先出し、スタック

　スタックは、あるデータの集合にデータを1つ追加し、その後1つ取り出すと、最後に追加したものが取得できるという性質のものです。スタックへのデータの追加はプッシュ（push）、データの取り出しはポップ（pop）と呼ばれます。図にすると以下のようになります。

図1　プッシュとポップ

　スタックのような動作はLIFO（Last In First Out）と呼ばれます。ライフォやリーフォと読むことが多いようです。日本語では後入れ先出しといいます。プログラムで表現すると以下のようになります。

<html>
<body> 
<script type="text/javascript">
  function Stack() {
    this.elements = new Array();
    this.length = 0;
  }
  Stack.prototype.push = function(value) {
    this.elements[this.length] = value;
    this.length++;
  }
  Stack.prototype.pop = function() {
    var popvalue = this.elements[this.length - 1];
    delete this.elements[this.length - 1];
    this.length--;
    return popvalue;
  }
 
  var stack = new Stack();
  stack.push(3);
  stack.push(8);
  stack.push(7);
  stack.push(5);
  document.write("1回目のpop = " + stack.pop() + "<br/>");
  document.write("2回目のpop = " + stack.pop() + "<br/>");
</script>
</body>
</html>

sample2-1.html

4～7行目：

クラスStackとコンストラクタを定義しています。内部では配列を使ってデータを管理します。変数lengthはStackの長さと同時に末尾の要素のインデックスを指定するのにも使います。

8～11行目：

pushメソッドを定義しています。配列elementsの末尾にデータを追加します。

12～17行目：

末尾からデータを取り出し、末尾の要素を削除しています。末尾の要素を削除してもthis.elements.lengthの値は変わりません。そのため別途length変数を使っています。

JavaScriptのクラスとprototypeについて

　スタックを表現したコード中に2カ所、prototypeという部分があります。これはJavaScript（その基礎となるECMAScript）に固有の記述です。ここでは詳細な解説は割愛しますが、JavaScriptでクラスのメソッドを定義する場合にはこのように記述するものと理解していただければと思います。Javaで同様のコードを記述すると次のようになります。

public class Stack {
 
  private int[] elements;
  private int length;
 
  public Stack(int capacity) {
    this.elements = new int[capacity];
    this.length = 0;
  }
 
  public void push(int value) {
    this.elements[this.length] = value;
    this.length++;
  }
 
  public int pop() {
    int popvalue = this.elements[this.length - 1];
    this.elements[this.length - 1] = 0;
    this.length--;
    return popvalue;
  }
}

先入れ先出し、キュー

　　　　　　 1|2|3 次のページへ

SpecialPR