工房のweb（okアカウントが必要）
さて、奥出研内での勉強会「工房」で、今週金曜3限（13:00-14:30）からアルゴリズムとデータ構造の筋トレ的なプログラミングをやります。
先月までは「地獄開発環境」と銘打って、俺の使っている開発環境（Flash, AVR, Apache, Perl, PHP, MySQL, Proce55ing, Wiring, Arduino, C#）なんかを延々インストールしたりFlickrやはてなブックマークを使うような事をやってましたが、今月から激しくJavaでアルゴリズム体操。
（ぶっちゃけ配列とか関数とか何？って状態からでも大丈夫だと思います）
というわけで俺も久しぶりにJava開発環境をインストールして、「Stack」というデータ構造を作ってみた。
参考：JavaのStackクラス
左：Stack設計図 右：TreeやMap、ソートの概念
あー、左の写真の下の図、Stackじゃなくてdequeになってる（リンクが双方向になってる）これは間違い
スタックは、一つ隣への参照を持っている「ノード」が、無限に連なる事で要素を無限に保持する事が出来る。配列より柔軟。
■なんでアルゴリズムとデータ構造をやるのか
Stackとか○○Mapとか○○Setとか○○Hashとか○○Listとか伝統的な名前があって、それによって使い所が違う。そういうのを知っていると良いことがいっぱいある。
・他人のコードを読む時に便利。名前を見れば何をするプログラムか想像できる。
・速く作れる。根幹のデータ構造とシーケンスをしっかりやっておくと、最後のあたりで試行錯誤してスパゲティコードになってもなんとか動くモノができる
・新しいプログラミング言語を覚える時に便利。データ構造とアルゴリズムは（基本的に）普遍的なアイディアなので、それをおさえておけば一学期にまとめてphpとC#とFlashとavr-gccとかやっても混乱しない
とかがあって、基本的なデータ構造とアルゴリズムと、あとデザインパターンを知ってれば大抵のプログラミング言語はすぐわかるようになってる。
（まあ、PC内のソフトやネットワークのエンジニアリングだけをやる研究室ではないので、ある意味別のデザインルールがあるんだけど…やってる俺も未だに上手くルールが表現できない）
ちなみにJavaは長ったらしくてストリームとかも使いにくいしあまりラピッドプロトタイピング向きではないんだけど、仕様が丁寧なのでこういうのの説明に向いてるから使う。大体わかったら他の「用途に特化した処理系」に移行する。
****実際にStackを作ってみる****
■17:10版
Javaのスタッククラスを参考に、必要なインタフェースメソッドを洗い出した。
1年の秋に受けた授業のwebから、stackがどういう構造になってるか把握。
それを元にクラス図を書いた。
■17:30版
クラス図に従って、Nodeクラス、Stackクラスを作って、メソッドとプロパティだけ設定した
これから中身を作る。
■19:20版
タリーズに移動。
Nodeクラスに、次のノードを取得したり要素を取り出したりを実装した。
■19:40版
Stackクラスのpush()とpop()を実装した。
でも、入れた数以上に取り出そうとするとエラーが出る。まだ使いにくい。
■20:00版
popの実装が難しい。エラーが出ないようにするにはどうすればいいか？
１．何個入った／出たか、ずっと数えておく。残り0だったらやめる
２．次があるかカウントしておく
→ 最後のノードだったら次はないので不十分
１と２両方やった。count()メソッドも実装した
というわけで、ちょうど一時間でstack実装完了。おつかれさまでした。
■改造しよう
工房の時にその場のノリで色々考えるだろうけど、このstackをお手本に色々作ってみましょう
・javaのstackを参考にpeek()メソッドを実装。一番上の要素を取得するが、取り除かない。
・empty()メソッドを実装。要素が空かどうかわかる。while文で中身を全部取り出す時に使う
・toString()メソッドを実装。stackの中身を文字で表現する。これは大抵のクラスに実装されてて、デバッグの時便利。
・dequeにする（headを2つにして両側から出せるようにする）
・HashStackにする。値と一緒にkeyも入れて、keyで検索して取り出したりできるようにする
・リンクを2つにして、Tree（二分木）を作る。
・Iteratorを作る
・中身を逆にする reverse() メソッドを実装する
■その他
ほかに、実装しながらこんな話もしようと思う
・カプセル化、setterとgetter
・バージョン管理。ソースコードのバックアップを取る
・APIドキュメントの読み方
・エラーメッセージでぐぐれ
・継承、キャスト（型変換）
・クラス図の書き方
・値渡しと参照渡し
・Flash、PHP、C#、Cなんかではどうやってるか？