スポンサード リンク

スポンサーサイト

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

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

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

前回のエントリで簡単な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の内部を配列ではなく連結リストで実装することで、要素を無限に追加できるように変更します。

Javaで学ぶデータ構造入門02-FIFOキュー

  1. Javaで学ぶデータ構造入門02-FIFOキュー(1/3)-配列による素朴な実装
  2. Javaで学ぶデータ構造入門02-FIFOキュー(2/3)-配列を環状に使う工夫(このエントリ)
  3. Javaで学ぶデータ構造入門02-FIFOキュー(3/3)-連結リストによる実装(予定)

Javaで学ぶデータ構造入門01-スタック

  1. Javaで学ぶデータ構造入門01-スタック(1/3)-基本操作の実装
  2. Javaで学ぶデータ構造入門01-スタック(2/3)-ジェネリクスの実装
  3. Javaで学ぶデータ構造入門01-スタック(3/3)-さらなる操作の実装

スポンサード リンク

テーマ:プログラミング - ジャンル:コンピュータ - ソーシャルブックマーク: この記事をクリップ! Yahoo!ブックマークに登録

00 : 00 : 31 | プログラミング-Java | トラックバック(0) | コメント(0) | page top↑
<<CCNAの問題集 | ホーム | Yahoo!メールアプリ サービス終了のお知らせ>>
コメント

コメントの投稿














管理者にだけ表示を許可する

トラックバック
トラックバックURL
http://networkprogramming.blog18.fc2.com/tb.php/30-292d04a9
この記事にトラックバックする(FC2ブログユーザー)
| ホーム |

プロフィール

TBVector

Author:TBVector

プロフィール

メールフォーム

記事検索

Google

最近の記事

人気の記事

過去の記事

カテゴリー

タグランキング

リンク

最近のコメント

最近のトラックバック

アクセスカウンタ

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