スポンサード リンク

スポンサーサイト

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

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

Javaで学ぶデータ構造入門02-FIFOキュー(1/3)-配列による素朴な実装

キューは先入れ先出し(FIFO : First In First Out)に基づくデータ構造です。(cf. スタック)

基本的かつ応用上重要なデータ構造であるため、標準ライブラリなどの形でサポートされているプログラミング言語もあります。JavaのAPIにもjava.util.Queueというインタフェースがあります。これはあくまでインタフェースなので、それを継承したjava.util.LinkedListなどのインスタンスを生成して使います。

/* JavaAPIのQueueの使用例 */
Queue<Integer> queue = new LinkedList<Integer>();

キューは一般的に以下の操作を備えています。ここでも、これらの機能を実装しました。

  • Enqueue : キューにデータを入れる。
  • Dequeue : キューからデータを取り出す。
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 MyQueue(int initialCapacity) {
		capacity = initialCapacity;
		queue = (T[]) new Object[initialCapacity];
		fpnt = 0;
		rpnt = 0;
	}
	
	public void enqueue(T item) {
		if(rpnt >= capacity)
			System.out.println("Queue is full.");
		else
			queue[rpnt++] = item;
	}
	
	public T dequeue() {
		if(fpnt == rpnt) {
			System.out.println("Queue is empty");
			return null;
		} else {
			return queue[fpnt++];
		}
	}
}

問題点

この実装ではキューの内部が配列にデータを保持しているため、格納できる要素数に限りがあります。また、先頭要素と最後尾の要素へのポインタは進む一方なので、Dequeueした領域は二度と使うことができず、初めに作った配列のサイズまでしか要素を入れることができません。

解決策

  1. Dequeueのたびに配列の要素を前にずらす。
  2. 剰余演算によってポインタを計算することで、配列を環状に使う。
  3. キュー内部を配列ではなく連結リストで実装する。

解決策1は配列の要素を前にずらすときに時間がかかるという欠点があります。

解決策2は今回のようにキューの内部を配列で実装する場合には有効な工夫であるといえます。次回のエントリではこの方法でプログラムを改良します。しかし、配列を使っている以上、依然として最大容量の問題は残っていることに注意が必要です。

解決策3は上で挙げた問題を完全に解決してくれます。3回目のエントリではこの方法によってプログラムを改良します。

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!ブックマークに登録

23 : 35 : 30 | プログラミング-Java | トラックバック(0) | コメント(0) | page top↑
<<2008年2月の人気記事ランキング | ホーム | Javaで学ぶデータ構造入門01-スタック(3/3)-さらなる操作の実装>>
コメント

コメントの投稿














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

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

プロフィール

TBVector

Author:TBVector

プロフィール

メールフォーム

記事検索

Google

最近の記事

人気の記事

過去の記事

カテゴリー

タグランキング

リンク

最近のコメント

最近のトラックバック

アクセスカウンタ

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