Document

スタックとキュー
データ構造とプログラミング
（第５回）
スタックとキュー
配列はコンピュータのメモリーの抽象化
スタックとキューはアルゴリズム実現用の特
別な記憶装置
アクセスに制限を加えてある
抽象的な構造で、配列でも（以下で現れる）リ
ストで実現することもできる
スタック(Stack, LIFO)
データをつみ上げる（後入れ先出し）
アクセスは一番上のデータだけ
カッコと対応を確認するなどの応用が典型的
最初の電卓はスタックを使った（今でも使われてい
る）
Javaの仮想計算機もスタック上で演算を行なう
メソッドの呼出しでは、計算環境をスタックに記憶さ
せて、再開の準備をする
スタックの応用
文字列の反転
カッコの対応関係成立
カッコの対応
c(d)
a{b(c)d}e
a{b(c}d}e
a[b(c)d]e}
a{b(c)
キュー(Queue, FIFO)
先入れ先出し
insert(); remove(); peek(); isEmpty(); isFull();
size();
Circular queue or Ring buffer ( Front と Rear を
つなげる)

Download Report