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