Javaで学ぶデータ構造入門02－FIFOキュー(2/3)－配列を環状に使う工夫

Ads by Google

-- / -- / -- ( -- )

上記の広告は１ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

スポンサードリンク

-- : -- : -- | スポンサー広告 | page top↑

Javaで学ぶデータ構造入門02－FIFOキュー(2/3)－配列を環状に使う工夫

2008 / 03 / 08 ( Sat )

前回のエントリで簡単なFIFOキューを作りました。しかし、その実装には「ポインタは進む一方なので、Queueに入れることのできるのべアイテム数が初めに作った配列のサイズになってしまう」という問題がありました。

そこで、今回は剰余演算を利用して次のポインタを求めることで、配列を環状に利用する工夫をした実装をしました。

public class MyQueue<T> {
	private T queue[];
	private int fpnt, rpnt;
	private final static int DEFAULT_CAPACITY = 10;
	private int capacity;
	
	public MyQueue() {
		this(DEFAULT_CAPACITY);
	}
	
	public MyQueueR(int initialCapacity) {
		capacity = initialCapacity;
		queue = (T[]) new Object[initialCapacity];
		fpnt = 0;
		rpnt = 0;
	}

	private int nextp(int pnt) {
		return ((pnt + 1) % capacity);
	}

	public void enqueue(T item) {
		if(nextp(rpnt) == fpnt)
			System.out.println("Queue is full");
		else {
			rpnt = nextp(rpnt);
			queue[rpnt] = item;
		}
	}
	
	public T dequeue() {
		if(fpnt == rpnt) {
			System.out.println("Queue is empty");
			return null;
		} else {
			T tmp = queue[fpnt];
			fpnt = nextp(fpnt);
			return tmp;
		}
	}
}

赤色が追加/変更部分です。

次のポインタを求めるメソッドnextpを導入し、これをenqueueとdequeueから利用しています。

ここで、Queueがいっぱい/空の判定法を考えてみましょう。

まず、Queueが空かどうか調べる場合です。この場合はこれまで通り先頭ポインタfpntと末尾ポインタrpntが等しいかどうかしらべることで判定できます。

次に、Queueがいっぱいになる場合です。これも、末尾ポインタrpntと先頭ポインタfpntが同じかどうか判定すればよさそうですが・・・本当にそれでよいのでしょうか？――実はそれではいけません。配列を環状に使っているため、この判定法ではQueueが空なのかいっぱいなのか区別が付かないのです。

そこで、配列に空の要素を一つ設けることによって、この問題を解決します。よって、末尾ポインタrpntの次のポインタnextp(rpnt)と先頭ポインタfpntの比較を行うことになります。

次回は、Queueの内部を配列ではなく連結リストで実装することで、要素を無限に追加できるように変更します。