逆転を狙う工大生の日々

絶賛留年中の落ちこぼれがなんとか頑張ろうとしている日記です

キュー(リングバッファ)をJavaで実装してみる

なんと2日も続きました。大成功といって良いのではないでしょうか。

 

今回はスタックにつづいて重要なデータ構造の一つであるキューを実装して見ようと思います。昨日に引き続いて、

「定本 Javaプログラマのためのアルゴリズムとデータ構造/近藤嘉雪 著」を参考にさせていただいております。

 

まずキューの基礎知識について簡単なおさらいを

待ち行列のように、「先頭から取り出され、末尾に追加される」いわゆるFIFO(First In First Out)となっている。

・固定長の配列で実現する場合には、配列をリング状にする必要がある(つまり、要素数nの配列において、末尾がn-1に到達したら、次の末尾のインデックスは0になる)。いわゆるリングバッファ。

・先頭から取り出す操作を「デキュー」、末尾に追加する操作を「エンキュー」という

 

こんな感じでしょうか。今回はリングバッファを実装してみました。

ーQueue.java


import java.util.Arrays;
import java.util.NoSuchElementException;

public class Queue {
	private Object[] queue;
	private int queueSize;
	private int front;
	private int rear;
	
	/*
	 * 用意した機能
	 * エンキュー、デキュー、空チェック、プリント、リセット
	 * */
	
	private static final int dQueueSize = 10;
	
	public Queue(){
		this(dQueueSize);
	}
	
	public Queue(int size){
		this.queue = new Object[size];
		queueSize = size;
		front = rear = 0;
	}
	
	//先頭・末尾の次のインデックスを返す
	//リングバッファなので、配列の最後に達した場合、次のインデックスは0に戻る
	public int next(int p){
		if(p == queueSize-1) {
			return 0;
		}else{
			return p+1;
		}
	}
	
	//キューの中身が空でないかチェックする
	//先頭と末尾が同じ時が空である
	public boolean isEmpty(){
		return front == rear;
	}
	
	//エンキュー(キューに追加する)
	//基本的な操作はスタックのspがrearに変わっただけのようです
	public void enqueue(Object o){
		if(next(rear) == front){
		 throw new IllegalStateException("容量オーバー");
		}
		queue[rear] = o;
		rear = next(rear);
	}
	
	//デキュー(キューから先頭要素を取り出す)
	//スタックと処理は変わらない?
	public Object dequeue(){
		if(front == rear){
		 throw new NoSuchElementException("キューが空です");
		}
		Object o = queue[front];
		queue[front] = null;
		front = next(front);
		return o;
	}
	
	
	public String PrintQueue(){
		StringBuilder st = new StringBuilder();
		st.append("queue = [ ");
		for(int i=front; i != rear; i=next(i)){
			if(i != rear-1){
				st.append(queue[i] + ",");
			}else{
				st.append(queue[i]);
			}
		}
		st.append(" ]");
		return st.toString();
	}
	
	public void clearQueue(){
		front = rear = 0;
		Arrays.fill(queue,0,queueSize,null);
	}

	public int getFront() {
	    return front;
	}

	public int getRear() {
	    return rear;
	}
}

実際に書いてみると、スタックの処理内容と対して変わらないことに気づく。スタックポインタspが、先頭frontと末尾rearに変わっただけです。次のインデックスを出力するnext関数を定義してリングバッファを実現しています。参考書を見てみると、

「return (p + 1) % queueSize」

 となっています。どちらも変わらない動作ではありますが、こちらの方がかっこいいですね。参考になります。たしかOSの教科書のリングバッファの図でも剰余で出した記憶が。定着度の低さが垣間見えます。

 ーMain.java


public class Main {
	public static void main(String[] args) {
		Queue q = new Queue(5); //サイズ5のキューqを生成
		
		//q.dequeue();
		
		q.enqueue("A");
		q.enqueue("B");
		q.enqueue("C");
		q.enqueue("D");
		//q.enqueue("E");
		System.out.println(q.PrintQueue());
		System.out.println("front=" + q.getFront() + " " + "rear=" + q.getRear());
		
		q.dequeue();
		q.dequeue();
		System.out.println(q.PrintQueue());
		System.out.println("front=" + q.getFront() + " " + "rear=" + q.getRear());
		
		q.clearQueue();
		System.out.println(q.PrintQueue());
	}
}

・サイズ5のキューを生成

・何もエンキューしていない状態でデキュー

 ・エンキュー

・エンキュー後のキューの中身、先頭と末尾を出力

・デキュー

・デキュー後のキューの中身、先頭と末尾を出力

・キューの状態をリセット

・リセット後のキューの中身、先頭と末尾を出力

という操作を実行して挙動を確かめてみます

ー実行結果ー

 

f:id:ikuth:20140507111219p:plain

 

こちらはコメントアウトをしたまま実行した結果です。要素A,B,C,Dをエンキューして、A,Bが正しくデキューされてますね。リセット後もちゃんと空になってます。

 

f:id:ikuth:20140507111221p:plain

続いて、「//q.enque("E");」のコメント部分をとりはらって実行してみます。サイズ5のキューに5つ目の要素Eを入れると何故か容量オーバーになる?どうして?

これは「front」は先頭要素の位置を、「rear」は末尾の次の位置を指しているので、キューを満杯にしてしまうと、「front == rear」が「キューが空の場合」と「キューが満杯の場合」の両方にあてはまってしまい、正しく動かなくなるため、キューのサイズには必ず一つだけスペースを開けておく必要があるようです。別のフラグや、キュー内の要素数を別に管理しておくという解決方法もあるようです。

 

f:id:ikuth:20140507111218p:plain

空の状態でデキューすると、エラーが出力されます。

 

今回もそんなに難しくなかった。これからprologやって夜にもう一度更新できればいいかなと思います。それでは。