投稿者: Hong Chen

キューとスタックは、古典的なデータ構造として広く知られているものですが、 実装上はリストの一種と考えることができます。

キュー

キュー (Queue) は「先入れ先出し (First-In First-Out, FIFO)」を表すデータ構造です。 データを取り出す際、先に格納したものから順に取り出します。

• 銀行や病院やたい焼き屋の待ち行列 (先に並んだ人からサービスを受ける)
• コンピューターでプリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。

データを追加する操作をエンキュー(enqueue)。
データを取り出す操作をデキュー(dequeue)という。

スタック

スタック(Stack)は、 「あと入れ先出し (Last-In First-Out, LIFO)」あるいは「先入れあと出し(First-In Last-Out, FILO)」を表すデータ構造です。 データを取り出す際、最も後に格納したものから順に取り出します。

• 積ん読 (本を重ねて積んでいくと上からしか取れない)
• コンピューターで割込みやサブルーチンを支援するために極めて有用である

スタックにデータを入れる操作をプッシュ(push)という。
スタックからデータを取り出す操作をポップ(pop)という。

キューとスタックの実装

オブジェクトの後入れ先出し（LIFO）スタックを表すStackクラスは、JDK 1.0から導入されていました。これに対して、オブジェクトの先入れ先出し（FIFO）を表す待ち行列（キュー）は、特に用意されていませんでしたが、JDK 5.0からQueueインターフェイスが新たに導入されました。

一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。

import java.util.*;

String[] item = {"Apple", "Banana", "Cocoa"};
Queue q = new LinkedList();
Stack s = new Stack();
for(String i: item) {
  q.offer(i); // enqueue
  s.push(i);  // push
}
while(q.size() > 0) {
  println("QUEUE:" + q.poll());
}
while(s.size() > 0) {
  println("STACK:" + s.pop());
}

キューがスタックに近い形で利用可能になっているのが、実感できます。

参考：

• http://www.atmarkit.co.jp/fjava/javatips/182java064.html　ーーGenericsを用いたスタックとキューのサンプルプログラム

サーチ（Search）とは，複数のデータの中から特定のデータを見つけ出す作業のことです。日本語では探索や検索と呼びます。

サーチのアルゴリズムには，ランダムなデータを取り扱えるものと，ソート済みのデータを取り扱うものとがあります。

リストサーチ（list search）

データのリスト構造とはA, B, C, ……のように，データが次々と連続している構造のことを言います。代表例は配列です。

そのようなリスト構造を持つデータの集合を探索するためのアルゴリズムを，ここではリストサーチと呼びます。

探索のアルゴリズム

• 線形探索
• 二分探索
• ハッシュ法

線形探索

線形探索という言葉は英語のLinear Searchの直訳です。線形探索はリストの先頭から終端に向かって目的の要素を探し出すアルゴリズムです。

目的の要素であるという判定は比較によって行います。

アルゴリズム分析

1. リストの先頭から要素を取り出す
2. 取り出した要素の値と探したい要素の値を比較する
   • 一致すれば探索完了
   • 一致しなければ 1. へ戻り次の要素を取り出す

かなりシンプルで理解し易いアルゴリズムです。

サンプルコード

線形探索のアルゴリズムを実装したsketchは次のとおりです。

// 線形探索   Linear Search
// 番兵無し   No Sentinel

final int    NUMBER_OF_RANDOM_DATA = 500;
final String DATA_FILE_NAME        = "RandomData.txt";
final int    DIAMITER              = 5;
final int    SEARCHING_VALUE       = 37;

ArrayList<Integer> nums = new ArrayList<Integer>();
int i = 0; // サーチ回数。drawする度にカウントアップ

void setup(){
  //ランダムなデータの読み込み
  loadData();
  //ディスプレイウインドウの設定
  size(NUMBER_OF_RANDOM_DATA,NUMBER_OF_RANDOM_DATA);
  background(0,0,0);
  frameRate(60);
  stroke(255,0,0);
}

void loadData(){
  String lines[] = loadStrings(DATA_FILE_NAME);
  for(String val : lines){
    nums.add(int(val));
  }
}


void linearSearch(){
  if (SEARCHING_VALUE == nums.get(i)) {
    println("Hit!");
    ellipse(i,nums.get(i),DIAMITER*2,DIAMITER*2);
    exit();
  } 
}

void draw(){
  println("Searching value is " + SEARCHING_VALUE);
  if (i < NUMBER_OF_RANDOM_DATA){
    //サーチ１パス
    linearSearch();
    //結果をプロット
    println("Count " + i);
    clear(); 
    for (int k=0; k < nums.size(); k++) {
      if ( k == i ) {
        ellipse(k,nums.get(k),DIAMITER*2,DIAMITER*2);
      } else {
        ellipse(k,nums.get(k),DIAMITER,DIAMITER);
      }
    }
    ++i;
  }
}

参考：

• http://www.codereading.com/algo_and_ds/algo/linear_search.html

データ構造とは

データ構造（データこうぞう、英: data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。
ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。

配列

配列（はいれつ）は同じ型の変数を複数取り扱うために考案された仕組みです。配列は変数名にカッコ付きの整数を添えることで順番を決め，要素を区別します。配列によってまとめられた，一つひとつの変数を要素（ようそ）と呼びます。要素を区別するために添えた数字を添字（そえじ）と呼びます。

配列は大変シンプルで，コレクションクラスに比較すると必要とするメモリ量が少なく，アクセスが高速なことがメリットです。データを単純に格納して，順番に参照する程度の用途であれば，コレクションクラスに比較して配列のほうが有利です。

最も基本的な配列の使用例を次に示します。配列の要素数を含めて宣言し，配列の添字を明記して要素に値を代入し，添字を指定して要素の値を呼び出します。

String names[] = {“Tim Bray”,        // 0番目の要素
“Brian Kernighan”, // 1番目の要素
“Jon Bentley”,     // 2番目の要素
“Karl Fogel”};     // 3番目の要素

for(int i = 0; i < names.length; ++i){
println(names[i]);
}

ランダムな整数データを500個もつデータファイルRandomData.txtを作成

int NUMBER_OF_RANDOM_DATA = 500;
int MIN_SIZE_OF_RANDOM_DATA = 1;
int MAX_SIZE_OF_RANDOM_DATA = 500;
String DATA_FILE_NAME = “RandomData.txt”;
int DIAMETER = 5;

void setup(){
//ランダムなデータの作成
ArrayList<Integer> nums = new ArrayList<Integer>();
for(int i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
nums.add((int)random(MIN_SIZE_OF_RANDOM_DATA,MAX_SIZE_OF_RANDOM_DATA));
}
//画面に出力してみる
size(500,500);
background(0,0,0);
stroke(255,0,0);
for(int i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
ellipse(i,nums.get(i),DIAMETER,DIAMETER);
}
//ファイルに出力
String[] data = new String[NUMBER_OF_RANDOM_DATA];
for(Integer i = 0; i < NUMBER_OF_RANDOM_DATA; ++i){
data[i] = nums.get(i).toString();
}
saveStrings(DATA_FILE_NAME,data);
}

このコードで作成したデータファイルRandomData.txtはスケッチフォルダGenerateRandomData内にあります。他のsketchで利用する場合は，そのsketchのスケッチフォルダにコピーしてください。

コレクション

配列は変数に添字と呼ばれる番号を振ることで要素を区別しています。場合によっては添字が不要であったり余計であったりします。

コレクション（collection）（時には，コンテナー（container）と呼ばれます）は，効率的なアクセスのために有用な方法で，オブジェクトを保持してまとめる入れ物です。

まとめ

• 配列はシンプルで高速なアクセスが可能です。要素数が少なく，ごく単純な操作しか必要ない場合に活用すると良いでしょう。
• コレクションは柔軟な取り扱いができるよう工夫された仕組みです。特に意味がなければ，配列ではなくコレクションを用いましょう。

• http://www.tohoho-web.com/java/collection.htm
• http://java-reference.sakuraweb.com/java_collection_compare.html
• https://rat.cis.k.hosei.ac.jp/article/java/index.html

アルゴリズムとは

アルゴリズム（英: algorithm）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。「算法（さんぽう）」と訳されることもある。

基本的なアルゴリズム

• 順次
• 条件判定と分岐 (if, switch)
• 繰り返し (while, for)

順次

順次実行構造は，上に書かれた命令が先に実行され，下に書かれた命令が後に実行される構造のことです。なるべくこのようなシンプルで自然な構造になるようコードを書くべきです。

典型的な順次実行の例として，GSWPよりサンプルコードを引用します。

// Example 03-13 from "Getting Started with Processing" 
// by Reas & Fry. O'Reilly / Make 2010

size(480, 120);
smooth();
strokeWeight(12);
strokeJoin(ROUND);      // Round the stroke corners
rect(40, 25, 70, 70);
strokeJoin(BEVEL);      // Bevel the stroke corners
rect(140, 25, 70, 70);
strokeCap(SQUARE);      // Square the line endings
line(270, 25, 340, 95);
strokeCap(ROUND);       // Round the line endings
line(350, 25, 420, 95);

画面の設定から描画まで，上から下へ順に実行されます。

条件判定と分岐 (if, switch)

条件に従って実行するコードブロックを切り替える仕組みは大変便利です。図5.3はif文の流れ図です。論理式が成り立つ場合，つまり「真」ならば直下のコードブロックを実行し，論理式が成り立たなければ，つまり「偽」ならば流れは右へ分岐し，右側のコードブロックが実行されます。

基本的に，条件分岐の流れ図では，論理式が成り立つ（すなわち真の）とき真下へ向かう流れ線をたどり，論理式が成り立たない（すなわち偽の）とき横へ向かう流れ線をたどります。流れ線に真や偽，TやFといった値が記されていない場合はそのように理解してください。

昼には太陽、夜には月が動くようなアニメーション

これを実現するためは、たとえば以下のようなプログラムを書く

 int scene;
 int x;
 float theta;
 void setup(){
  scene = 0;
  theta = 3.1;
  size(600,300);
 }
 void draw(){
  theta += 0.01;
  if(scene==0){
    background(100,100,200);
    noStroke();
    fill(250,250,250);
    ellipse(300*cos(theta)+300,300*sin(theta)+400,100,100);
    if(theta > 6.3){scene=1; theta=3.1;}
  }
  else {
    background(0);
    noStroke();
   fill(250,250,50);
   ellipse(300*cos(theta)+300,300*sin(theta)+400,100,100);
   if(theta > 6.3){scene=0; theta=3.1;}
 }
 }

ここでは、ふたつの場面のどちらであるかを表すために scene という変数を用意して、scene が0なら昼の場面、それ以外なら夜の場面を描くようにしている。実際にはscene は0か1である。

繰り返し (while, for)

同じような仕事を繰り返すことがあります。コンピュータは，繰り返しの仕事が得意です。人間なら早晩飽きて放り出してしまうことも，コンピュータは決して飽きません。

図5.4は繰り返しの基本形，while文の流れ図です。

while文による繰り返し構造の流れ図は次のように読みます。

1. 論理式（条件式とも呼びます）が成り立てば，すぐ下のコードブロックへ実行が移ります。
2. コードブロックの実行が終わると，論理式の直前に実行が戻ります。
3. 論理式が成り立つ限り，コードブロックを繰り返し実行します。
4. 論理式が成り立たない場合，実行は右側へ移り，コードブロックを実行せずwhile文の構造を終了します。

命令 for を使うと、同じ内容は以下のように書ける。

 int i;
 for(i=0; i<=90; i += 10){
  line(0,i,99,i);
 }

参考：

• いろいろなソートアルゴリズム http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/
• Interactive Data Structure Visualizations http://student.seas.gwu.edu/~idsv/idsv.html

Javaのインストール

MacBookでのJavaのインストール方法

http://java.com/ja/download/help/mac_install.xml

MacにJavaをインストールするには、次の手順に従います。
jre-7u6-macosx-x64.dmgファイルをダウンロードします。ファイルをダウンロードする前に、使用許諾契約の内容を確認し、同意します。
.dmgファイルをダブルクリックして起動します
パッケージ・アイコンをダブルクリックし、インストール・ウィザードを起動します

結果確認

chen-no-MacBook-Air:~ chen$ java -version
java version “1.8.0_11”
Java(TM) SE Runtime Environment (build 1.8.0_11-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.11-b03, mixed mode)

Windows７でのJavaのインストール方法

http://java.com/ja/download/help/windows_manual_download.xml

手動ダウンロード・ページに移動します
「Windows Online」をクリックします
ダウンロードするファイルを実行するか保存するかを尋ねる「ファイルのダウンロード」ダイアログ・ボックスが表示されます
インストーラを実行するには、「実行」をクリックします。
ファイルを保存して後でインストールするには、「保存」をクリックします。
保存先として、ローカル・システムのフォルダを選択します。
ヒント: デスクトップなどのように、コンピュータ上のわかりやすい場所にファイルを保存してください。
保存したファイルをダブル・クリックし、インストールを開始します。
インストールが始まります。「Install (インストール)」ボタンをクリックして使用許諾契約の条項に同意し、インストールを続行します。

Javaアプリケーションのサンプル（HelloWorld）

Java の　Hello World

class Hello {
  public static void main(String[] args) {
    System.out.println("Hello World!");
  }
}

chen-no-MacBook-Air:Workshop chen$ vi Hello.java
chen-no-MacBook-Air:Workshop chen$ javac Hello.java
chen-no-MacBook-Air:Workshop chen$ java Hello
Hello World!
chen-no-MacBook-Air:Workshop chen$

ブラウザで実行できるサービス

例えばちょっと○○言語触ってみたいなーと思ったとき、
環境を作る手間を考えて辞めてしまうことは割と多い。

統合開発環境(IDE)みたいにインストールするだけで使えます！とかならまだしも、
手動で環境変数を設定したり設定ファイル編集したりしなければならないとなると･･･

そんなときに使えるのがこのIdeone。
http://ideone.com/

ユーザ登録をしなくても使うことができる。
しかしユーザ登録をした方が間違いなく便利なのでオススメ。

ユーザ名とパスワード、メールアドレスだけで登録できる。
「I have read and agree to the Ideone Terms of use.」にチェックをいれること。

Processingのインストール

ProcessingはJava言語の機能をより簡単に使えるよう工夫されており，また開発環境から実行環境までがワンセットになっています。初心者が学習する言語として最適です。作成したプログラムは単独で動く実行ファイルに簡単に変換できます。これも大変魅力的です。

ダウンロード

Processing の公式サイト（http://processing.org/）を開き，メニューから DOWNLOAD をクリックします．Linux ，Mac OSX，Windows，Windows (without Java) というメニューがありますので、自分のPCに合わせてダウンロードしてください。

Windows版であれば，ダウンロードしたファイルを展開するだけです。展開したフォルダに入っているProcessingのアイコンをダブルクリックすれば開発環境が立ち上がります。展開したフォルダをMy Documentsなどのお好みの場所へ置いてください。USB へのセットアップすれば、自分の Windows PC 以外でも USB メモリを挿せば Processing プログラミング環境が利用できます。

Mac OS X 版はさらに簡単です。ダウンロードしたファイルをダブルクリックすれば開発環境が立ち上がります。ダウンロードしたファイルはアプリケーションフォルダにドラッグ＆ドロップしておきましょう。

Processing のサンプル（HelloWorld）

プログラミング学習の第一歩は，Hello World という文字列を画面に表示するのが一般的ですが，Processing は視覚的な表現が得意，具体的には図形（グラフィック）描画が得意なので，最初の一歩も図形を描画することをしてみます．

では，入力エリアに次の文字列を入力してください．

line( 0, 0, 100, 100 );

入力が終わったら，入力エリアの上にあるボタンのうち，一番左にある音楽再生ボタンのような絵柄のボタンをクリックしてください．小さなウィンドウが表示され，直線が描かれていると思います．ここでは，このウィンドウを 実行ウィンドウ と呼ぶことにます．

ブラウザで実行できるサービス

• OpenProcessing（英語）http://www.openprocessing.org
  • 編集ページ → http://www.openprocessing.org/sketch/create
  • 解説ページ → OpenProcessing の新機能 create new sketch を試してみた
• アプリケーションをインストールしていなくても、ブラウザさえ立ち上げれば気楽に試すことができる。
• OpenProcessing に公開すれば、他のユーザーの評価を受けたり、ブログパーツとして利用することもできる。

練習問題

  1. 画面に適当な大きさの正方形を描くプログラムを作れ
  2. 画面に「田の字」を描くプログラムを作れ

作ったプログラムはProcessing のメニューの File ⇒ save で保存する。プログラムの名前を変更するときは save asを使う。保存先のフォルダが上で作ったものになっているのを確認すること。

参考サイト

• http://www.tohoho-web.com/java/about.htm
• http://gihyo.jp/dev/serial/01/practical-programming-with-processing

• 「明解 Javaによるアルゴリズムとデータ構造」  柴田 望洋 (著)ソフトバンククリエイティブ (2007/11/7)
• 「明解Java　入門編」  柴田 望洋 (著)ソフトバンククリエイティブ(2007/8/8)
  • http://bohyoh.com/Java/
• 「Javaによるはじめてのアルゴリズム入門」（河西朝雄著、技術評論社、2001年）
• 「標準Javaプログラミングブック」（河西朝雄著、技術評論社、2001年）
• とほほのJava入門 (http://www.tohoho-web.com/java/index.htm )

【参考文献（英語）】

• http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/ — Algorithms and Data Structures Research & Reference Material
• https://www.cs.auckland.ac.nz/software/AlgAnim/ppt/ — Data Structures and Algorithms, PowerPoint slides
• https://www.cs.auckland.ac.nz/software/AlgAnim/ds_ToC.html — Data Structures and Algorithms, Table of Contents
• https://www.cs.auckland.ac.nz/software/AlgAnim/ppt/ — Data Structures and Algorithms , PowerPoint Slides, 1998 Lectures
• http://xlinux.nist.gov/dads/ — Dictionary of Algorithms and Data Structures ( http://hissa.ncsl.nist.gov/~black/)
• http://student.seas.gwu.edu/~idsv/idsv.html — Interactive visualisations グラフなどのデータ構造を視覚化して表示（Mozilla Firefoxでは動作しない）