キューとスタック

今回は「Java言語プログラミングレッスン」を参照します。この本に掲載されているサンプルプログラムは著者のサイトからダウンロードできますが、文字コードが Shift JIS であるため、UTF-8 に変換したものを以下に置いておきます。

第19章サンプルプログラム

復習: これまでに学んだデータ構造

クラスライブラリ基礎では、主要なデータ構造である以下の構造を学びました。

リスト (ArrayList, LinkedList)
集合 (HashSet)
マップ (HashMap)

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

まずは、これまで学んだリスト構造を思い出しましょう。どんなメソッドが用意されていたでしょうか。

復習: ArrayList

class ArrayList

(教科書 p.263-)

復習: LinkedList

class LinkedList

(教科書 p.288-)

問題 String のオブジェクトが入るリスト(ArrayList でも LinkedList でも可)を生成し、文字列をいくつか追加します。そのリストの内容を、先頭から表示するプログラムを作成してみましょう。なお、リストに入れる文字列はソースに文字列定数として記述してしまってかまいません。

問題同じリストの中から、指定したキーワードを含む文字列だけを探して表示するプログラムを作成してみましょう。

キュー

キュー (Queue) は「先入れ先出し (First-In First-Out, FIFO)」を表すデータ構造です。データを取り出す際、先に格納したものから順に取り出します。

取り出し ←

A B C

← 追加

キュー (Wikipedia)

現実世界に現れる FIFO を探してみましょう。

筒状のもの
- パイプ
- ホース
- ところてんを作る器具
- CPUのパイプライン
- 一方通行で追い越しできない道
銀行や病院やたい焼き屋の待ち行列 (先に並んだ人からサービスを受ける)
コンビニ店員の理想とする商品管理 (先に入荷したものから売る; 後ろから補充)

問題上に挙げられているものとは異なる例を探してみましょう。プログラムでシミュレーションすることを前提に考えてみてください。

Java の Collections Framework では、キューを表す Queue インタフェースが LinkedList に実装されているので、 LinkedList をキューとして使うことができます。

Queue<String> queue = new LinkedList<String>();

Queue インタフェースが提供するメソッドを確認しましょう。戻り値に注意してください。

interface Queue

(教科書 p.290)

なお、Queue には様々な亜種があり、FIFO ではない使い方ができるものもあります。興味のある人は関連するクラスを調べてみましょう。

スタック

スタック(Stack)は、「あと入れ先出し (Last-In First-Out, LIFO)」あるいは「先入れあと出し(First-In Last-Out, FILO)」を表すデータ構造です。データを取り出す際、最も後に格納したものから順に取り出します。

追加 →
取り出し ←

A B C

スタック (Wikipedia)

現実世界に現れる FILO を探してみましょう。

細長い袋状のもの
- コップ
- リュック
積ん読 (本を重ねて積んでいくと上からしか取れない)
縦長の駐車場に車2台を入れる (先に停めた車は出られない)
狭い冷藏庫 (前のものを取らないと昔入れた後ろのものが取れない)
後から後からより重要度の高い仕事がやってくる状況 (いまやっている仕事を棚上げ、の繰り返し)
UNIX系OSの push/pop コマンド

問題上に挙げられているものとは異なる例を探してみましょう。プログラムでシミュレーションすることを前提に考えてみてください。

Java (JDK 1.0) ではスタックを表すクラス Stack があります。追加は push(E item)、取り出しは pop() というメソッドを用います。

class Stack

なお、Stack クラスは ArrayList に似た Vector クラスを継承していますので、配列と同じような性質を持ちます。

Stack はインタフェースではなくクラスなので、new でインスタンスを作ることができます。

Stack<String> stack = new Stack<String>();

Java SDK 1.6 以降では、両端から要素の追加/取り出しが可能なキューである Deque (double ended queue, でっく) というインターフェイスがあり、これの片側だけを利用すると FILO になります。具体的には、例えば offerFirst(e)/pollFirst() メソッドの組み合わせ、あるいは offerLast(e)/pollLast() メソッドの組み合わせで用います。

intaface Deque

このインタフェースは、LinkedList や ArrayDeque クラスで実装されています。 ArrayDeque クラスの場合、 ArrayList と同様に初期容量を越えるとメモリを確保しなおすため、注意が必要です。

Deque<String> listStack = new LinkedList<String>();
Deque<String> arrayStack = new ArrayDeque<String>();

なお、一般には ArrayDeque クラスは Stack クラスよりも速い動作をします。

サンプル

URL のリストを格納するサンプルです。 view と入力すると、キューなら先頭、スタックなら最後に格納したものが取り出され、ブラウザ上で表示されます (Linux で Firefox がインストールされている環境のみ)。

import java.util.*;
import java.io.*;

public class PageListViewer {
    public static void main(String args[]) {
	// キュー
	Queue<String> urlQueue = new LinkedList<String>();
	// スタック
	// Stack<String> urlStack = new Stack<String>();
	Scanner scanner = new Scanner(System.in);
	scanner.useDelimiter("\n");
	System.out.println("追加するURLを入力してください(viewで表示)");
	System.out.print("> ");
	while(scanner.hasNext()) {
	    String s = scanner.next();
	    if(s.startsWith("http")) {
		// キュー
		urlQueue.offer(s);
		// スタック
		// urlStack.push(s);
		System.out.println(" 追加: " + s);
	    }
	    else if(s.startsWith("view")) {
		// キュー
		String urlString = urlQueue.poll();
		// スタック
		// String urlString = urlStack.pop();
		if(urlString != null) {
		    System.out.println(" 取り出し: " + urlString);
		    // コマンドの指定 (配列の0番目がコマンド名、それ以降が引数)
		    String[] command = {"/usr/bin/firefox", urlString};
		    // コマンドの起動
		    try {
			Runtime.getRuntime().exec(command);
		    }
		    catch (IOException e) {
			System.out.println(e.getMessage());
		    }
		}
	    }
	    else {
		System.out.println(" 入力が無効: " + s);
	    }
	    System.out.println();
	    System.out.print("> ");
	}
    }
}

問題上記のサンプルプログラムを参考に、前の問題で思いついたはずのキューとスタックの実例をシミュレートするプログラムを作成しましょう。

来週は、配列を使って自分でスタックを作ってみる、といった演習問題が出題されます。お楽しみに。

	im.dendai.ac.jp ほか
yamada@