Javaで学ぶアルゴリズム -キュー

キュー

• 一時的にデータを保存しておくためのデータ構造
• 先入れ先出し（FIFO : Fist In, First Out）で行われる
  • enqueue：キューにデータを入れる
  • dequeue：キューからデータを取り出す
  • peek：次にdequeueする際に取り出されるデータをのぞき見する
• dequeueする際に毎回、2番目以降のデータの位置をすべて前倒しにするのは非効率なので、リングバッファというデータ構造を使うとよい

実行環境

• JUnit 5
• Java 8

テストコード

IntQueueTest.java

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.jupiter.api.Assertions.assertThrows;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

public class IntQueueTest {

	private IntQueue queue;

	@DisplayName("例外がスローされること")
	@Nested
	class IntQueueExceptionTest {

		@DisplayName("初期化時の例外")
		@Nested
		class InitializationExceptionTest {
			@Test
			void testInvalidInitializationThrowsException() {
				assertThrows(IllegalArgumentException.class, () -> {
					queue = new IntQueue(0);
				});
			}

			@Test
			void testInvalidInitializationThrowsExceptionNegative() {
				assertThrows(IllegalArgumentException.class, () -> {
					queue = new IntQueue(-1);
				});
			}
		}

		@DisplayName("enqueue時の例外")
		@Nested
		class enqueueExceptionTest {
			@Test
			void testOverflowIntQueueException() {
				queue = new IntQueue(3);
				assertThrows(OverflowIntQueueException.class, () -> {
					queue.enqueue(1);
					queue.enqueue(2);
					queue.enqueue(3);
					queue.enqueue(4);
				});
			}
		}

		@DisplayName("dequeue時の例外")
		@Nested
		class PopExceptionTest {
			@Test
			void testEmptyIntQueueException() {
				queue = new IntQueue(3);
				assertThrows(EmptyIntQueueException.class, () -> {
					queue.dequeue();
				});
			}

			@Test
			void testEmptyIntQueueExceptionAfterClearPop() {
				queue = new IntQueue(3);
				queue.enqueue(1);
				queue.clear();
				assertThrows(EmptyIntQueueException.class, () -> {
					queue.dequeue();
				});
			}
		}

		@DisplayName("peek時の例外")
		@Nested
		class PeekExceptionTest {
			@Test
			void testEmptyIntQueueExceptionPeek() {
				queue = new IntQueue(3);
				assertThrows(EmptyIntQueueException.class, () -> {
					queue.peek();
				});
			}
		}
	}

	@DisplayName("正常系のテスト")
	@Nested
	class IntQueueNormalTest {

		@BeforeEach
		void setUp() {
			queue = new IntQueue(10);
			queue.enqueue(1);
			queue.enqueue(2);
			queue.enqueue(3);
		}

		@Test
		@DisplayName("最初にenqueueしたキューがdequeueできること")
		void testEnqueueAndDequeue() {
			assertThat(queue.dequeue(), is(1));
		}

		@Test
		@DisplayName("dequeueしたあとにpeekすると２つ目にenqueueしたデータが覗き見れること")
		void testPeek() {
			queue.dequeue();
			assertThat(queue.peek(), is(2));
		}

		@Test
		@DisplayName("clear後にenqueueしたものがdequeueできること")
		void testClear() {
			queue.clear();
			queue.enqueue(4);
			assertThat(queue.dequeue(), is(4));
		}

		@Test
		@DisplayName("enqueueとdequeueでリングバッファの循環動作が正しいこと")
		void testCircularBehavior() {
			queue.clear();
			for (int i = 0; i < 10; i++) {
				queue.enqueue(i);
			}
			queue.dequeue();
			queue.dequeue();
			queue.dequeue();
			queue.enqueue(10);
			queue.enqueue(11);
			queue.enqueue(12);
			assertThat(queue.dequeue(), is(3));
		}
	}
}

キューアルゴリズム

IntQueue.java

public class IntQueue {

	private int[] queue; // キュー本体
	private int capacity; // キューのキャパ
	private int front; // キューの先頭を示すポインタ
	private int rear; // キューの末尾を示すポインタ
	private int dataSize; // 現在のデータ数

	public IntQueue(int size) {
		if (size <= 0) {
			throw new IllegalArgumentException("size must be greater than 0");
		}
		this.capacity = size;
		this.queue = new int[capacity];
		this.front = 0;
		this.rear = 0;
		this.dataSize = 0;
	}

	/**
	 * キューからデータをエンキュー（追加）する
	 * enqueueされたら溢れちゃう場合に例外を投げる
	 * @param data
	 */
	public void enqueue(int data) {
		if (dataSize >= capacity) {
			throw new OverflowIntQueueException();
		}
		queue[rear++] = data;
		dataSize++;
		// 配列のインデックス上限を越えないようにハンドリング
		if (rear == capacity) {
			rear = 0;
		}
	}

	/**
	 * キューからデータをデキュー（取り出し）する
	 * キューにデータがない場合に例外を投げる
	 * @return
	 */
	public int dequeue() {
		if (dataSize <= 0) {
			throw new EmptyIntQueueException();
		}
		int data = queue[front++];
		dataSize--;
		// 配列のインデックス上限を越えないようにハンドリング
		if (front == capacity) {
			front = 0;
		}
		return data;
	}

	/**
	 * キューの先頭データを覗き見する
	 * キューにデータがない場合に例外を投げる
	 * @return data
	 */
	public int peek() {
		if (dataSize <= 0) {
			throw new EmptyIntQueueException();
		}
		return queue[front];
	}

	/**
	* キューのデータをクリアする
	*/
	public void clear() {
		dataSize = front = rear = 0;
	}
}

補足

実際には java.util.Queue インターフェースを実装したクラスを使うとよい