next up previous contents
Next: 25. ファイル入出力 Up: 24. キュー・スタック Previous: 24.3 スタック

24.4 課題 24

cd c を実行した後で( ~/c に移動した後で )、以下の課題を やってみよ。

課題 24.1
スタックI

スタックをリストを使って実装し、動作を確認せよ。 また、その際に typedef を用い、新しい型 STACK 型として 定義せよ。

課題 24.2
スタックII

24.1 を用い、適当なファイル(例えば kadai24_1.c)を読み込んで、 一行づつ逆順に出力するプログラムを作成せよ。 ( malloc() を用いて、メモリの効率的な利用をしなければ ならない。)

課題 24.3
キュー・スタック

前の章で学んだ双方向リンクトリストを使うと、キューとしても、 スタックとしても使えるようなデータ構造が記述できる。これを 仮にスタックキューと呼ぼう。スタックキューでは、便宜上常に データを取り出す際には、最後尾のデータが取り出されるものとする。 従って、スタックとして使う時には、最後尾にデータを追加し、 キューとして使う時には、最前列にデータを追加すれば良い。 このようなスタックキューを設計し、モジュールとして使えるように プログラムを作成せよ。

作成したプログラムをメイルで creport まで送りなさい。題は、kadai24 とする事。

前回の復習
キュー

キューは、最後に入ったデータが最後に処理されるという意味でLILO(Last In Last Out)の データ構造を扱うものである。様々な形で実装できるが、要素数の変化に対応できる点から リストを用いてしばしば実現される。

スタック

スタックは、最初に入ったデータが最後に処理されるという意味でFILO(First In Last Out)の データ構造を扱うものである。スタックの実現もキューと同じような意味からリストで 実現される事が多い。

FI,FO,LI,LO

ここまでに出て来た用語の FI(First In), FO(First Out), LI(Last In),LO(Last Out)を用いると、4種類あるので あるから、4通りのデータ構造があると言えるが、実は LILO と FIFO は同じものである (最初に入ったものが最初に処理されるのと、最後に入ったものが最後に処理されるのは 同じ)。同様に、FILO と LIFO は同じであるので、結局2種類しかない点には注意しよう。

デク

キューの性質と、スタックの性質を合わせ持ったものは、デク(DEQ: Double Ended Que) とも呼ばれる。緊急データはスタック的に処理し、それ以外の通常の順番での処理には キューとして使うような場合に用いられる。従って、リストで実現すればほとんど キューと同じである(処理の容易さから、双方向リンクトリストで実現する場合が多い)。



Noriyo Kanayama