第１０回　スタックとキュー

(1)

第１０回　スタックとキュー

～データを収納する便利なデータ

構造～

(2)

学習目標

 スタック、キューの概念を説明できる



スタック、キューを利用して問題解決ができる



スタックを使ったプログラムが書ける



キューを使ったプログラムが書ける

(3)

10.1 商品の補充と販売

 10.1.1 商品の補充と販売をする

 10.1.2 最初に入れたものを最初に取り

出す

 10.1.3 配列を使ってキューを実装する

(4)

10.1.1 商品の補充と販売をする

 ① 「商品」クラス



「商品種類」は商品の種類のことでした



今日は実際の「商品」を扱います

ただし、商品の変数は

「製造年月日」だけとします。

商品

-

製造年月日

(5)

商品の補充と販売をする

 ② 商品を収納しておくクラス設計



商品保管庫には、どんな機能が必要でしょうか？

Mai n + mai n( )

商品保管庫 + 追加( )

+ 削除( ) + 表示( ) 1

1

商品 - 製造年月日 0. . n

1

1 1 1 0. . n

(6)

10.1.2 最初に

入れたものを最初に取り出す

 今回考える２種類の収納パターン



スタック

 後入れ先出し方式



キュー

 先入れ先出し方式

(7)

商品保管庫

後入れ先だし方式（スタック）

•

後から入れたものは、列の先頭に挿入される

•

取り出すときは、列の先頭から取り出される

※ 昔のコンビニのジュース販売方式

これでは、列の最後に入れられたら、取り出されるこれでは、列の最後に入れられたら、取り出される

補充する販売する

(8)

商品保管庫

先入れ先出し方式（キュー）

•

後から入れたものは、列の最後に挿入される

•

取り出すときは、列の先頭から取り出す

※ いまのコンビニのジュース販売方式

古いものから取り出されるので、商品を販売するのに向いています

補充する販売する

(9)

10.1.3 配列を使ってキューを作る

 ① プリミティブな方法

[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]

追加カーソル

(11)

この方法の問題点

 削除するたびに要素の移動が起こってしまう



１万個入っていたら削除するたびに１万個の大移動が起こる



効率が悪いね

 どうしたら効率の良いキューになりま

すか？

(12)

③ 円環状に

することにより効率を上げる

[0] [1] [2] [3] [4] [5]

追加するときは追加カーソルがあるところに追加する追加したら、追加カーソルを一つずらす

カーソル追加

カーソル

(13)

円環キュー (2)

[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)

円環キューの実装例

public class ItemStock {

private int ARRAY_SIZE = 6;//配列で円環キューを実装するときは１サイズ分大きくする。

　　　　　　 // すなわちこれは５つしか入らない。

private Item[] itemArray = new Item[ARRAY_SIZE];//商品を格納する配列 private int addCursor = 0;// 追加カーソル

private int removeCursor =0;//削除カーソル /**

* 商品を補充する

*/ public void supply(Item insertItem){

itemArray[addCursor] = insertItem;// 追加カーソルの位置に挿入する addCursor++; //追加カーソルを右にずらす

if (addCursor >= ARRAY_SIZE){// 配列の最後にきたら addCursor = 0;//ラップアラウンドする

} }・・・

}

例題

10-2

(ItemStock.java)

(17)

キューのその他の使い道

 銀行の待ち行列

 プリンタの待ち行列

 コンピュータのプロセスの待ち行列

（プライオリティーキュー）

 etc…

(18)

10.2 投入された金の管理

 10.2.1 投入された金の管理

 10.2.2 最後に入れたものを最初に取り

出す

(19)

10.2 投入された金の管理

 ① 「金」クラス



硬貨一つ一つをオブジェクトと考えます

ただし、金の変数は

「値（単位：円）」

だけとします。

値は

100,10

などの整数が入ります。

金

-

価値

(20)

② クラス設計

 金勘定



投入された金を収納する勘定が必要

 本来は勘定に記入するものだが今回は直接金を入れてしまうことにします。

 勘定にはどんな機能が必要ですか？

金

-

価値

Mai n

+ mai n()

勘定

+

追加

() +

削除

()

+

表示

() 1 0. . n

1 1 1 0. . n

1 1

(21)

Undo したい

 投入したお金を Undo できる自動販売機を作って欲しい

※ 実際の自動販売機でこの例のようなケースは、

あまりありませんが、一般のソフトウエアでの

Undo

機能は重要な機能ですね

(22)

勘定の仕様

 一般的なシナリオ

1. 100 円 ,10 円 ,50 円の順番でお金を入れる（この時点で投入金額は 160 円）

2. Undo を実行すると、最後に入れたお金が戻る。（ 50 円が取り消され、投入金額が 110 円になる）

3. もう一度 Undo すると 10 円が戻る

(23)

スタック VS キュー

 スタック VS キュー

 考えてみましょう！



Undo を実現するには追加と逆順で削除する必要があります。



この場合、スタックを使うべきです。

(24)

10.2.2 最後に

入れたものを最初に取り出す

 スタック

勘定投入する

Undo

する

(25)

10.2.3 配列を使ってスタックを実装する

追加

&

削除カーソル

スタックへのお金の追加

[0] [1] [2] [3] [4] [5]

追加

&

削除

カーソル追加

&

削除

カーソル追加

&

削除カーソル

(26)

配列でスタックを作る (2)

スタックからお金の削除

(Undo)

[0] [1] [2] [3] [4] [5]

追加

&

削除追加

&

削除カーソル

追加

&

削除カーソル追加

&

削除カーソル

カーソル

[0] [1] [2] [3] [4] [5]

(27)

Java でスタックを実装する

 実装コード



実装されていないところは、今回の練習問

題

(28)

スタックのその他の使い道

 算術式のパース ( 解析 )

 XML,HTML などの入れ子構造の解析

 食堂のトレー置き場

 etc

(29)

算術式のパース

 問題：

3 + 4 * 5

(4 + 5) * (8 - 4)

などをコンピュータはどうやって計算

するか？

(30)

答え

 コンピュータはそのまま計算できない。

→特別な記法に変換する必要がある。

 例 )

3 + 4 * 5 3 4 5 * + →

中置記法後置記法

(

逆ポーランド記法

)

(31)

後置記法で書かれた式を計算する

 ルール



左から一文字ずつ読む



数字がきたらスタックにつむ



演算子がきたらスタックの上から２つの数字を取り出して演算する

演算したら結果をスタックの上に積む



これを式の最後まで繰り返す

(32)

後置記法で書かれた式を計算する

スタック計算対象

3 4 5 * +

３４５２０２３

(33)

中置記法と後置記法

中置記法後置記法

A+B-C AB+C-

AB/C ABC/

A+BC ABC+

AB+C ABC+

A(B+C) ABC+

AB+CD ABCD+

(A+B)(C-D) AB+CD-

(34)

後置記法と日本語



3 + 4 * 5 3 4 5 * +

→ 3 に 4 と 5 をかけたものを足す



5 * 8 + 7 * 3 5 8 * 7 3 * +

→ 5 と 8 をかけたものと 7 と 3 をかけたものを足す

 日本語と語順が同じ。

→日本語とコンピュータは相性がいい。

(35)

中置記法を後置記法に変換する

 ルール

 左から一文字ずつ読む

 数字がきたら、結果に書き出す

 かっこがきたら

 開きかっこの場合→スタックに積む

 閉じかっこの場合→開きかっこを見つけるまで、スタックから演算子を取り出して、結果に書き出す

 かっこ以外の演算子がきたら

 スタックが空なら→スタックに積む

 スタックを覗いて、スタック演算子よりも優先順位の低い演算子だったら、結果に書き出す。そうでなければ、スタックに積む

 式を最後まで読み取ったら、スタックに入っているものをすべて出力する

(36)

中置記法を後置記法に変換する

対象 3 + 4 * 5

出力

3

スタック

+

3 4

*

3 4 5 出力

3

スタック

+

3 4

3 4 5 * 出力

33 4

スタック

3 4 5 * +

(37)

10.3 インタラクティブなプログラム

 10.3.1 キーボード入力

 10.3.2 キーボード入力のメソッドはど

こに配置する？

(38)

10.3.1 キーボード入力

 今回のプログラムは、少しインタラクティブに、コンソール（標準入力）から文字を読み込むプログラムにします

（ Example6_2Item.java,Example6_2Mo ney.java)

プログラム文字の読み込み

(39)

Java でコンソール

から文字を読み込む方法

 Java には、ファイルや標準入出力を簡単にするためのクラス群が用意されています「 java.io 」パッケージに入っています

BufferedReader + readLi ne() I nputStreamReader

+ read()

(40)

今回使うクラスの役割

プログラム

「 System.in 」

BufferedReader + readLi ne( )

I nputStreamReader + read()

バッファリングして一行ずつ読み込む役割のクラス

読み込む役割のクラス

(41)

実装方法

/** *

ユーザの入力を一行読み込む

* 変更不要

*/ public String getInput(){

String buf = null;//

読み込んだ文字列を保存する

try{

//

読み込むための

BufferedReader クラスをインスタンス化する

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

buf = br.readLine();// 一行読み込む }catch(Exception ex){

ex.printStackTrace();// 入出力エラーが起きた場合エラーを表示する }

return buf;// 読み込んだ文字列を返す }

例題

10-4

(Example10_4Item.java)

(42)

10.3.2 キーボード

入力のメソッドはどこに配置する？

 ① メインクラスに書く

 ② 入力を受け付けるクラスを作る

 ③ クラスメソッドを利用する

(43)

Exampl e10_4I tem + mai n()

+ getI nput()

Exampl e10_4Money + mai n()

+ getI nput()

① メインクラスに書く

 コンソールから読み込むメソッドを作ったのはいいですが、両方の

Example に書かなければいけなくなり

ました

重複コードになってしまいました

(44)

② 入力を

受け付けるクラスを作る

 メソッドの分類によって、より意味が明確なプログラムに

I nput + getI nput ( )

Exampl e10_4I tem + mai n()

+ getI nput()

Exampl e10_4Money + mai n()

+ getI nput()

(45)

入力クラス

 入力を受け付ける意味のクラスを作ることによってコードの重複を防ぐことができる



ただし、様々な所で入力するコードを書く

たびに、 Input クラスをインスタンス化す

る必要がある

Input input = new Input();// ユーザからの入力を得るためのインスタンス String menu = input.getInput()//

コンソールからユーザの入力を得る

(46)

メモリの無駄使い

Input

インスタンス

Input

インスタンス

Input

インスタンス

Input

インスタンス

Example

プログラム

Example

プログラム

Example

プログラム

getInput()

１つでもいいのでは？

メモリの無駄使いです

(47)

無駄なインスタンスは作りたくない

Input

インスタンス

Example

プログラム

Example

プログラム

Example

プログラム

getInput()

 インスタンスは一つでもこと足ります



このような仕組みはどうしたらできます

か？

(48)

③ クラスメソッドを利用する

Input

クラス

 一般的なプログラムでは

Input

インスタンス

インスタンス化して

Example

プログラム

getInput()

(49)

クラスメソッドにすると

 クラスメソッドは直接呼び出すことができます

Input

クラス

Example

プログラム

getInput()

Example

プログラム

Example

プログラム

getInput() getInput()

(50)

/**

*

ユーザの入力を一行読み込む

* 変更不要

*/ public static String getInput(){

String buf = null;//

読み込んだ文字列を保存する

try{

//

読み込むための

BufferedReader クラスをインスタンス化する

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

buf = br.readLine();// 一行読み込む }catch(Exception ex){

ex.printStackTrace();// 入出力エラーが起きた場合エラーを表示する }

return buf;// 読み込んだ文字列を返す }

クラスメソッドにするには

 メソッドに static 修飾子をつけます

例題

10-6

(Input.java)

(51)

クラスメソッドを呼び出すには

Input input = new Input();//

ユーザからの入力を得るためのインスタンス

String menu = input.getInput()// コンソールからユーザの入力を得る

「Example10_3Item.java,Example10_3Money.java 」より抜粋

String menu = Input.getInput()// コンソールからユーザの入力を得る

「Example10_4Item.java,Example10_4Money.java 」より抜粋

インスタンスメソッドの呼び出し

クラスメソッドの呼び出し

インスタンス変数名

クラス名

(52)

static

 static をメソッドに付けると、クラスメ

ソッドになります

 static を変数に付けると、クラス変数に

なります

Input

クラス

(53)

第１０回 スタックとキュー