第8回 データを収納する （スタックとキュー）

Presentation on theme: "第8回 データを収納する （スタックとキュー）"— Presentation transcript:

1 第8回 データを収納する （スタックとキュー）
オブジェクト・プログラミング 第8回 データを収納する （スタックとキュー）

2 本日の目標 データを収納する２つのデータ構造 （スタック、キュー）の概念を説明できるようになる。
スタック、キューを使う利点を説明できるようになる。 スタック、キューを配列を使って実装できるようになる。

3 今日登場する新しいオブジェクト(1) 「商品」クラス 「商品情報」は単に情報だけだった。 今日は実際の「商品」を扱う
ただし、今日は商品の属性を 「製造日」 だけとします。

4 今日登場する新しいオブジェクト(2) 「お金」クラス 硬貨一つ一つがオブジェクトと考える ただし、今日はお金の属性を 「値」 だけとします。
値は100円,10円などが入ります。 100 50 10

5 今日考えること① 問題：商品の補充と販売をできるようにする。 商品を収納しておくFolderが必要です。

6 今日考える2種類の収納パターン 後入れ先出し方式 先入れ先出し方式

7 後入れ先だし方式（スタック） 商品Folder 補充する 販売する 後から入れたものは、列の先頭に挿入される。 取り出すときは、列の先頭から
※昔のコンビニのジュース販売方式 これでは、列の最後に入れられたら、取り出される 機会がほとんどなくなってしまう！

8 先入れ先出し方式（キュー） 商品Folder 販売する 補充する 後から入れたものは、列の最後に挿入される。 取り出すときは、列の先頭から
※いまのコンビニのジュース販売方式 古いものから取り出されるので、商品を販売するの に向いている。

9 キューを配列を使って作る(1) プリミティブな方法 挿入時は配列番号順に入れていく [0] [1] [2] [3] [4] [5] 追加
カーソル 追加 カーソル 追加 カーソル 追加 カーソル

10 キューを配列を使って作る(2) 取り出し時は配列の先頭を削除して、 配列の中身をひとつずつずらす [0] [1] [2] [3] [4]
[5] [0] [1] [2] [3] [4] [5] 追加 カーソル [0] [1] [2] [3] [4] [5] 追加 カーソル [0] [1] [2] [3] [4] [5] 追加 カーソル [0] [1] [2] [3] [4] [5] 追加 カーソル [0] [1] [2] [3] [4] [5] 追加 カーソル [0] [1] [2] [3] [4] [5] 追加 カーソル

11 この方法の問題点 削除するたびに要素の移動が起こる。 効率はO(N)のオーダーで悪くなる 要素が少なければいいけど、多いと、 効率が悪いね。

12 配列で円環キューを作る(1) 今日の課題でつかうのはこの方法 追加するときは追加カーソルがあるところに追加する
追加したら、追加カーソルを一つずらす [0] [1] [2] [3] [4] [5] 追加 カーソル 追加 カーソル 追加 カーソル 追加 カーソル

13 配列で円環キューを作る(2) 削除するときは削除カーソルがあるところから削除する 削除したら、削除カーソルを一つずらす [0] [1]
[2] [3] [4] [5] [0] [1] [2] [3] [4] [5] [0] [1] [2] [3] [4] [5] [0] [1] [2] [3] [4] [5] 削除 カーソル 削除 カーソル 削除 カーソル 削除 カーソル 追加 カーソル

14 配列で円環キューを作る(3) 追加カーソルが配列を最後まできたら、 配列の一番初めに戻す。 →ラップアラウンド（最初に戻るの意）といいます。
[0] [1] [2] [3] [4] [5] 削除 カーソル 追加 削除 カーソル 追加 カーソル ※削除も同様

15 配列で円環キューを作る(4) 追加カーソルと削除カーソルが同じ位置にあるときは、 要素が入っていないことを示す。 [0] [1] [2]
[3] [4] [5] 削除 カーソル 追加 カーソル

16 この方法の効率 効率はO(1)になる。 ただし、少しコードが複雑になる。

17 円環キューの実装 //円環キューを使って商品を収納するクラス public class ItemQueue {
int arrayMax = 5;//配列のサイズ Item[] itemArray = new Item[arrayMax];//商品が入る配列 int addCursol = 0;//追加カーソル int removeCursol =0;//削除カーソル //挿入するメソッド public void insert(Item insertItem){ itemArray[addCursol] = insertItem;//追加カーソルの位置に挿入する addCursol++; //追加カーソルを１増やす if (addCursol >= arrayMax){//配列の最後にきたら addCursol = 0;　　　　　　　　//ラップアラウンドする } 　//この後削除メソッドは次のページ

18 円環キューの実装 //前ページの続き。円環キューを使って商品を収納する //商品を削除するメソッド
　public Item remove(){ if(addCursol == removeCursol){//商品がない return null;//何も入っていないのでnullを返す } 　 Item item = itemArray[removeCursol];//削除カーソルのところの商品を取り出す itemArray[removeCursol]=null;//削除カーソルのところの商品を削除する removeCursol++;//削除カーソルを1増やす if (removeCursol >= arrayMax){//配列の最後にきたら removeCursol =0; //ラップアラウンドする return item;//削除した商品を返す }//ItemQueueの終わり

19 キューのその他の使い道 銀行の待ち行列 プリンタの待ち行列 コンピュータのプロセスの待ち行列 （プライオリティーキュー） etc…

20 今日考えること② 要求:お金を入れたのをUndoできる自動販売機を考えます。
①100円,10円,50円の順番でお金を入れる。 （この時点で投入金額は160円） ②Undoを実行すると、最後に入れたお金が戻る。（50円が取り消され、投入金額が110円になる） ③もう一度Undoすると10円が戻る ※実際の自動販売機でこの例のようなケースは、 あまりありませんが、一般のソフトウエアでの Undo機能は重要な機能です。

21 どちらをデータ構造を利用すべきか スタックVSキュー 考えてみましょう！（簡単ですね。）
Undoを実現するには追加と逆順で削除する必要があります。 この場合、スタックを使うべきです。

22 配列でスタックを作る(1) スタックの実装はキューに比べて簡単です。 スタックへのお金の追加 10 50 100 50 10 50 100
[0] [1] [2] [3] [4] [5] 10 100 追加&削除 カーソル 追加&削除 カーソル 追加&削除 カーソル 追加&削除 カーソル

23 配列でスタックを作る(2) スタックからお金の削除(Undo) [0] [1] [2] [3] [4] [5] 100 10 [0] [1]
50 100 10 [0] [1] [2] [3] [4] [5] 追加&削除 カーソル 追加&削除 カーソル 追加&削除 カーソル 追加&削除 カーソル 削除は追加カーソルの一つ前を削除します。

24 スタック 実装コード 簡単なのでここでは取り上げません。 課題を参照してください。 効率 O(1)という非常に高速オーダーで機能します。

25 スタックのその他の使い道 算術式のパース(解析) XML,HTMLなどの入れ子構造の解析 食堂のトレー置き場 etc

26 算術式のパース 問題： * 5 (4 + 5) * (8 - 4) などをコンピュータはどうやって計算するか？

27 答え コンピュータはそのまま計算できない。 →特別な記法に変換する必要がある。 例) 3 + 4 * 5 → 3 4 5 * + 中置記法
例) * → * + 中置記法 後置記法 (逆ポーランド記法)

28 後置記法で書かれた式を計算する ルール 左から一文字ずつ読む 数字がきたらスタックにつむ
演算子がきたらスタックの上から２つの数字を取り出して演算する 演算したら結果をスタックの上に積む これを式の最後まで繰り返す

29 後置記法で書かれた式を計算する 計算対象 3 4 5 * + ２０ ５ ２３ ４ ３ スタック

30 中置記法と後置記法 中置記法 後置記法 A+B-C AB+C- A*B/C AB*C/ A+B*C ABC*+ A*B+C AB*C+
A*B+C*D AB*CD*+ (A+B)*(C-D) AB+CD-* ((A+B)*C)-D AB+C*D-

31 後置記法と日本語 日本語と語順が同じ。 →日本語とコンピュータは相性がいい。
3 + 4 * * + →3に4と5をかけたものを足す 5 * * * 7 3 * + →5と8をかけたものと7と3をかけたものを足す 日本語と語順が同じ。 →日本語とコンピュータは相性がいい。

32 中置記法を後置記法に変換する ルール 左から一文字ずつ読む 数字がきたら、結果に書き出す かっこがきたら かっこ以外の演算子がきたら
開きかっこの場合→スタックに積む 閉じかっこの場合→開きかっこを見つけるまで、スタックから演算子を取り出して、結果に書き出す かっこ以外の演算子がきたら スタックが空なら→スタックに積む スタックを覗いて、スタック演算子よりも優先順位の低い演算子だったら、結果に書き出す。そうでなければ、スタックに積む 式を最後まで読み取ったら、スタックに入っているものをすべて出力する

33 中置記法を後置記法に変換する 対象 3 + 4 * 5 出力 3 3 4 3 4 5 * + 出力 3 3 4 3 4 5 * 出力 3
スタック 3 3 4 3 4 5 * + 出力 スタック 3 + 3 4 3 4 5 * * 出力 + 3 3 4 5 3 4 スタック

34 今日の課題(1) ２種類のプログラムを配ります。 商品を補充、販売するプログラム お金を入れてUndoができるプログラム Item.java
ItemQueue.java ItemMain.java お金を入れてUndoができるプログラム Money.java MoneyStack.java MoneyMain.java

35 今日の課題(2) 配ったプログラムを完成させなさい。 ①ItemQueueクラスのdisplay()メソッドを実装しなさい。
②MoneyStackクラスのdisplay()メソッドを実装しなさい。

36 今日の課題(3) ItemQueueクラスのdisplay()メソッドの出力仕様 ---キューの先頭--- 商品製造日:2000/01/01
商品製造日:2000/01/02 商品製造日:2000/01/03 商品製造日:2000/01/04 ---キューの最後--- ※配列をラップアラウンドしてもきちんとした結果が でるようにしてください。

37 今日の課題(4) MoneyStackクラスのdisplay()メソッドの出力仕様 ---スタックの先頭--- お金:10円 お金:50円
お金:100円 ---スタックの最後---

38 課題プログラム解説 今日のプログラムは、少しインタラクティブに、コンソール（標準入力）から文字を読み込むプログラムです。 プログラム 文字の
読み込み

39 Javaでコンソールから文字を読み込む方法
先週のファイルからの入力とほとんど同じやり方でできます。 詳しくは、ソースを熟読した上でTAにご質問を //コンソールから一行読み込んで文字列を返すメソッド public static String readStringFromConsole(){ String buf = null;//読み込んだ文字列を保存する try{ //読み込むためのBufferedReaderオブジェクトをインスタンス化する BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); buf = br.readLine();//一行読み込む }catch(Exception ex){ ex.printStackTrace();//入出力エラーが起きた場合エラーを表示する } return buf;//読み込んだ文字列を返す ここが先週と違う

40 課題プログラムのUMLクラス図

41 発展課題 発展課題① 発展課題② 発展課題③（難） 身の回りにあるキュー、スタックを探してみよう！
キュー10例、スタック10例あげてください。 発展課題② 今日のプログラムは、配列を超えて挿入したり、何も入っていないときに削除したりするとエラーでプログラムがとまります。これはまずいです。 できない操作をしたときは、「～だからできません」とユーザに教えてあげるプログラムにしましょう。 発展課題③（難） 算術式をパースするプログラムを書いてみよう！ 必修課題とは別にソースを添付してください。

42 提出方法 objprog-08@crew.sfc.keio.ac.jp宛て。
今回はソースのみを送ってください。 （ただし、ItemQueue,MoneyStackだけでよい。) (感想を任意でお願いします。) Subjectはログイン名を必ず書いてください。 ex) t96844ym 余計な[]などをつけないでください。 水曜まで。