キューとスタックは、古典的なデータ構造として広く知られているものですが、 実装上はリストの一種と考えることができます。
キュー
キュー (Queue) は「先入れ先出し (First-In First-Out, FIFO)」を表すデータ構造です。 データを取り出す際、先に格納したものから順に取り出します。
- 銀行や病院やたい焼き屋の待ち行列 (先に並んだ人からサービスを受ける)
- コンピューターでプリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。
データを追加する操作をエンキュー(enqueue)。
データを取り出す操作をデキュー(dequeue)という。
スタック
スタック(Stack)は、 「あと入れ先出し (Last-In First-Out, LIFO)」あるいは「先入れあと出し(First-In Last-Out, FILO)」を表すデータ構造です。 データを取り出す際、最も後に格納したものから順に取り出します。
- 積ん読 (本を重ねて積んでいくと上からしか取れない)
- コンピューターで割込みやサブルーチンを支援するために極めて有用である
スタックにデータを入れる操作をプッシュ(push)という。
スタックからデータを取り出す操作をポップ(pop)という。
キューとスタックの実装
オブジェクトの後入れ先出し（LIFO）スタックを表すStackクラスは、JDK 1.0から導入されていました。これに対して、オブジェクトの先入れ先出し（FIFO）を表す待ち行列（キュー）は、特に用意されていませんでしたが、JDK 5.0からQueueインターフェイスが新たに導入されました。
一例として、LinkedListオブジェクトによるキューと、Stackクラスによるスタックを試すプログラムを作成しました。
import java.util.*;
String[] item = {"Apple", "Banana", "Cocoa"};
Queue q = new LinkedList();
Stack s = new Stack();
for(String i: item) {
q.offer(i); // enqueue
s.push(i); // push
}
while(q.size() > 0) {
println("QUEUE:" + q.poll());
}
while(s.size() > 0) {
println("STACK:" + s.pop());
}
キューがスタックに近い形で利用可能になっているのが、実感できます。
参考：
- http://www.atmarkit.co.jp/fjava/javatips/182java064.html ーーGenericsを用いたスタックとキューのサンプルプログラム