6.Stack and Queue

キューとスタックは、古典的なデータ構造として広く知られているものですが、 実装上はリストの一種と考えることができます。

キュー

キュー (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を用いたスタックとキューのサンプルプログラム