第8回スタックとキュー - CreW 慶應義塾大学

第１０回スタックとキュー
～データを収納する便利なデータ構
造～
学習目標

スタック、キューの概念を説明できる



スタック、キューを利用して問題解決ができる
スタックを使ったプログラムが書ける
キューを使ったプログラムが書ける
10.1 商品の補充と販売



10.1.1 商品の補充と販売をする
10.1.2 最初に入れたものを最初に取り出
す
10.1.3 配列を使ってキューを実装する
10.1.1 商品の補充と販売をする

①「商品」クラス


「商品種類」は商品の種類のことでした
今日は実際の「商品」を扱います
商品
- 製造年月日
ただし、商品の変数は
「製造年月日」だけとします。
商品の補充と販売をする

②商品を収納しておくクラス設計
商品保管庫には、どんな機能が必要でしょう
か？

Main
商品保管庫
+ main()
1
+ 追加()
削除()
1+
+ 表示()
商品
- 製造年月日
1
0..n
10.1.2 最初に
入れたものを最初に取り出す

今回考える２種類の収納パターン

スタック


後入れ先出し方式
キュー

先入れ先出し方式
後入れ先だし方式（スタック）
商品保管庫
補充する
販売する
•後から入れたものは、列の先頭に挿入される
•取り出すときは、列の先頭から取り出される
※昔のコンビニのジュース販売方式
これでは、列の最後に入れられたら、取り出される
機会がほとんどなくなってしまいます
先入れ先出し方式（キュー）
商品保管庫
補充する
販売する
•後から入れたものは、列の最後に挿入される
•取り出すときは、列の先頭から取り出す
※いまのコンビニのジュース販売方式
古いものから取り出されるので、商品を販売するの
に向いています
10.1.3
配列を使ってキューを作る

①プリミティブな方法
挿入時は配列番号順に入れていく
[0]
[1]
[2]
[3]
[4]
[5]
追加追加追加追加
カーソル
カーソル
カーソル
カーソル
プリミティブな方法(2)
取り出し時は配列の先頭を削除して、
配列の中身をひとつずつずらす
[0]
[1]
[2]
[3]
[4]
[5]
追加追加追加
カーソル
カーソル
カーソル
この方法の問題点

削除するたびに要素の移動が起こってしま
う



１万個入っていたら削除するたびに１万個の
大移動が起こる
効率が悪いね
どうしたら効率の良いキューになります
か？
③円環状に
することにより効率を上げる
追加するときは追加カーソルがあるところに追加する
追加したら、追加カーソルを一つずらす
[0]
[1]
[2]
[3]
[4]
[5]
追加追加追加追加
カーソル
カーソル
カーソル
カーソル
円環キュー (2)
削除するときは削除カーソルがあるところから削除する
削除したら、削除カーソルを一つずらす
[0]
[1]
[2]
[3]
削除削除削除削除
カーソル
カーソル
カーソル
カーソル
[4]
[5]
追加
カーソル
円環キュー (3)
追加カーソルが配列
の最後まできたら、
配列の一番初めに戻す
ラップアラウンド
（最初に戻るの意）といいます
※削除も同様
[0]
[1]
[2]
[3]
追加追加追加
削除
カーソル
カーソル
カーソル
カーソル
[4]
[5]
追加
追加
カーソル
カーソル
円環キュー (4)
追加カーソルと削除カーソルが同じ位置にあるときは、
要素が入っていないことを示す
[0]
[1]
[2]
[3]
削除追加
カーソル
カーソル
[4]
[5]
円環キューの実装例
例題10-2
(ItemStock.java)
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;//ラップアラウンドする
}
}
・・・
}
キューのその他の使い道




銀行の待ち行列
プリンタの待ち行列
コンピュータのプロセスの待ち行列
（プライオリティーキュー）
etc…
10.2 投入された金の管理


10.2.1 投入された金の管理
10.2.2 最後に入れたものを最初に取り出
す
10.2 投入された金の管理

①「金」クラス

硬貨一つ一つをオブジェクトと考えます
金
- 価値
ただし、金の変数は
「値（単位：円）」
だけとします。
値は100,10などの整数が入ります。
②クラス設計

金勘定

投入された金を収納する勘定が必要


本来は勘定に記入するものだが今回は直接金を
入れてしまうことにします。
勘定にはどんな機能が必要ですか？
勘定
Main
+ main()
1
+ 追加()
1 + 削除()
+ 表示()
金
- 価値
1
0..n
Undoしたい

投入したお金をUndoできる自動販売機を
作って欲しい
※実際の自動販売機でこの例のようなケースは、
あまりありませんが、一般のソフトウエアでの
Undo機能は重要な機能ですね
勘定の仕様

1.
2.
3.
一般的なシナリオ
100円,10円,50円の順番でお金を入れる
（この時点で投入金額は160円）
Undoを実行すると、最後に入れたお金
が戻る。（50円が取り消され、投入金額
が110円になる）
もう一度Undoすると10円が戻る
スタック VS キュー


スタックVSキュー
考えてみましょう！
Undoを実現するには追加と逆順で
削除する必要があります。
この場合、スタックを使うべきです。

10.2.2 最後に
入れたものを最初に取り出す

スタック
勘定
投入する
Undoする
10.2.3 配列を使って
スタックを実装する
スタックへのお金の追加
[0]
[1]
[2]
[3]
[4]
追加&削除
追加&削除
追加&削除
追加&削除
カーソルカーソルカーソルカーソル
[5]
配列でスタックを作る(2)
スタックからお金の削除(Undo)
[0]
[1]
[2]
[3]
[4]
追加&削除
追加&削除
追加&削除
追加&削除
カーソルカーソルカーソルカーソル
[5]
Javaでスタックを実装する

実装コード

実装されていないところは、今回の練習問題
スタックのその他の使い道




算術式のパース(解析)
XML,HTMLなどの入れ子構造の解析
食堂のトレー置き場
etc
算術式のパース

問題：
3+4*5
(4 + 5) * (8 - 4)
などをコンピュータはどうやって計算する
か？
答え


コンピュータはそのまま計算できない。
→特別な記法に変換する必要がある。
例)
3+4*5
中置記法
→
345*+
後置記法
(逆ポーランド記法)
後置記法で書かれた式を計算
する

ルール




左から一文字ずつ読む
数字がきたらスタックにつむ
演算子がきたらスタックの上から２つの数字を
取り出して演算する
演算したら結果をスタックの上に積む
これを式の最後まで繰り返す
後置記法で書かれた式を計算
する
計算対象
345*+
５
２０
４
２３
３
スタック
中置記法と後置記法
中置記法
後置記法
A+B-C
AB+C-
A*B/C
AB*C/
A+B*C
ABC*+
A*B+C
AB*C+
A*(B+C)
ABC+*
A*B+C*D
AB*CD*+
(A+B)*(C-D)
AB+CD-*
((A+B)*C)-D
AB+C*D-
後置記法と日本語



3+4*5
345*+
→3に4と5をかけたものを足す
5*8+7*3
58*73*+
→5と8をかけたものと7と3をかけたものを足
す
日本語と語順が同じ。
→日本語とコンピュータは相性がいい。
中置記法を後置記法に変換す
る

ルール



左から一文字ずつ読む
数字がきたら、結果に書き出す
かっこがきたら



かっこ以外の演算子がきたら



開きかっこの場合→スタックに積む
閉じかっこの場合→開きかっこを見つけるまで、スタックから
演算子を取り出して、結果に書き出す
スタックが空なら→スタックに積む
スタックを覗いて、スタック演算子よりも優先順位の低い演算
子だったら、結果に書き出す。そうでなければ、スタックに積
む
式を最後まで読み取ったら、スタックに入っているもの
をすべて出力する
中置記法を後置記法に変換す
る
対象
3+4*5
出力
345*+
*
+
スタック
10.3
インタラクティブなプログラム


10.3.1 キーボード入力
10.3.2 キーボード入力のメソッドはどこに
配置する？
10.3.1 キーボード入力

今回のプログラムは、少しインタラクティブ
に、コンソール（標準入力）から文字を読み
込むプログラムにします
（Example6_2Item.java,Example6_2Mon
ey.java)
プログラム
文字の
読み込み
Javaでコンソール
から文字を読み込む方法

Javaには、ファイルや標準入出力を簡単に
するためのクラス群が用意されています
「java.io」パッケージに入っています
InputStreamReader
+ read()
BufferedReader
+ readLine()
今回使うクラスの役割
読み込む役割のクラス
InputStreamReader
+ read()
「System.in」
バッファリングして
一行ずつ読み込む
役割のクラス
BufferedReader
+ readLine()
プログラム
実装方法
例題10-4
(Example10_4Item.java)
/**
* ユーザの入力を一行読み込む
* 変更不要
*/
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.3.2 キーボード
入力のメソッドはどこに配置す
る？



①メインクラスに書く
②入力を受け付けるクラスを作る
③クラスメソッドを利用する
①メインクラスに書く

コンソールから読み込むメソッドを作ったの
はいいですが、両方のExampleに書かな
ければいけなくなりました
Example10_4Item
+ main()
+ getInput()
Example10_4Money
+ main()
+ getInput()
重複コードになってしまいました
②入力を
受け付けるクラスを作る

メソッドの分類によって、より意味が明確な
プログラムに
Example10_4Item
Example10_4Money
+ main()
+ getInput()
+ main()
+ getInput()
Input
+ getInput()
入力クラス

入力を受け付ける意味のクラスを作ること
によってコードの重複を防ぐことができる

ただし、様々な所で入力するコードを書くたび
に、Inputクラスをインスタンス化する必要があ
る
Input input = new Input();//ユーザからの入力を得るためのインスタンス
String menu = input.getInput()//コンソールからユーザの入力を得る
メモリの無駄使い
１つでも
いいのでは？
Input
インスタンス
getInput()
Example
プログラム
Input
インスタンス
getInput()
Example
プログラム
Input
インスタンス
getInput()
Example
プログラム
Input
インスタンス
getInput()
メモリの無駄使いです
無駄な
インスタンスは作りたくない

インスタンスは一つでもこと足ります

このような仕組みはどうしたらできますか？
getInput()
Input
インスタンス
getInput()
getInput()
Example
プログラム
Example
プログラム
Example
プログラム
③クラスメソッドを利用する

一般的なプログラムでは
Input
クラス
インスタンス化して
Input
インスタンス
getInput()
Example
プログラム
クラスメソッドにすると

クラスメソッドは直接呼び出すことができま
す
getInput()
Input
クラス
Example
プログラム
getInput()
Example
プログラム
getInput()
Example
プログラム
クラスメソッドにするには

メソッドにstatic修飾子をつけます
例題10-6
/**
(Input.java)
* ユーザの入力を一行読み込む
* 変更不要
*/
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;//読み込んだ文字列を返す
}
クラスメソッドを呼び出すには
インスタンスメソッドの呼び出し
Input input = new Input();//ユーザからの入力を得るためのインスタンス
String menu = input.getInput()//コンソールからユーザの入力を得る
「Example10_3Item.java,Example10_3Money.java」より抜粋
インスタンス変数名
クラスメソッドの呼び出し
String menu = Input.getInput()//コンソールからユーザの入力を得る
「Example10_4Item.java,Example10_4Money.java」より抜粋
クラス名
static


staticをメソッドに付けると、クラスメソッドに
なります
staticを変数に付けると、クラス変数になり
ます
Input
クラス
注意点

クラスメソッド、変数はプログラムのどこか
らでも呼べるので便利ですが、むやみやた
らに使うと、コードが複雑化します




あっちこっちに飛ぶプログラム
global変数は注意しないとバグの原因
基本はインスタンス生成で
ユーティリティークラスを作るときには便利
mainメソッドが
最初に呼ばれる仕組み
%java Example10_4
起動
main()
Java
バーチャルマシン
Example10_4
クラス

Download Report