Javaで学ぶアルゴリズム -スタック

スタック

• 一時的にデータを保存しておくためのデータ構造
• 後入れ先出し（LIFO : Last In, First Out）で行われる
  • push：スタックにデータを入れる
  • pop：スタックからデータを取り出す
  • peek：次にpopする際に取り出されるデータをのぞき見する
• ちなみに Java のメソッド呼び出しと実行はLIFOスタックの概念に基づいて行われている（コールスタック）

実行環境

• JUnit 5
• Java 8

テストコード

IntStackTest.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;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;

public class IntStackTest {

	private IntStack intStack;

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

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

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

		@DisplayName("push時の例外")
		@Nested
		class PushExceptionTest {
			@Test
			void testOverflowIntStackException() {
				intStack = new IntStack(3);
				assertThrows(OverflowIntStackException.class, () -> {
					intStack.push(1);
					intStack.push(2);
					intStack.push(3);
					intStack.push(4);
				});
			}
		}

		@DisplayName("pop時の例外")
		@Nested
		class PopExceptionTest {
			@Test
			void testEmptyIntStackException() {
				intStack = new IntStack(3);
				assertThrows(EmptyIntStackException.class, () -> {
					intStack.pop();
				});
			}

			@Test
			void testEmptyIntStackExceptionAfterClearPop() {
				intStack = new IntStack(3);
				intStack.push(1);
				intStack.clear();
				assertThrows(EmptyIntStackException.class, () -> {
					intStack.pop();
				});
			}
		}

		@DisplayName("peek時の例外")
		@Nested
		class PeekExceptionTest {
			@Test
			void testEmptyIntStackExceptionPeek() {
				intStack = new IntStack(3);
				assertThrows(EmptyIntStackException.class, () -> {
					intStack.peek();
				});
			}
		}
	}

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

		@BeforeEach
		void setUp() {
			intStack = new IntStack(5);
			intStack.push(1);
			intStack.push(2);
			intStack.push(3);
		}

		@DisplayName("最後にpushしたスタックをpopできること")
		@Test
		void testPush() {
			assertThat(intStack.pop(), is(3));
		}

		@DisplayName("3番目にpushしたスタックをpopしたあとは2番目にpushしたスタックが取り出せる状態になっていること")
		@Test
		void testPop() {
			intStack.pop();
			assertThat(intStack.pop(), is(2));
		}

		@DisplayName("最後にpushしたスタックをpeekできること")
		@Test
		void testPeek() {
			assertThat(intStack.peek(), is(3));
		}

		@DisplayName("スタックをクリアした後にpushした次の値をpopできること")
		@Test
		void testClear() {
			intStack.clear();
			intStack.push(4);
			assertThat(intStack.pop(), is(4));
		}

		@ParameterizedTest
		@CsvSource({
				"0, -1",
				"1, 0",
				"2, 1",
				"3, 2",
				"4, -1"
		})
		void testIndexOf(int data, int expected) {
			assertThat(intStack.indexOf(data), is(expected));
		}
	}
}

スタックアルゴリズム

IntStack.java

public class IntStack {

	private int capacity; // スタックの容量
	private int[] stack; // 今回はリサイズ不可でスタックを考えるため配列を使う
	private int pointer; // スタックに積まれている個数

	public IntStack(int size) {
		if (size <= 0) {
			throw new IllegalArgumentException("size must be greater than 0");
		}
		this.capacity = size;
		this.stack = new int[capacity];
		this.pointer = 0;
	}

	/**
	 * スタックにデータを積む
	 * pushされたら溢れちゃう場合に例外を投げる
	 * @param data
	 */
	public void push(int data) {
		if (pointer >= capacity) {
			throw new OverflowIntStackException();
		}
		stack[pointer++] = data;
	}

	/**
	 * スタックからデータを取り出す
	 * ポインタが0以下だったら何も取り出せないので例外を投げる
	 * @return  data
	 */
	public int pop() {
		if (pointer <= 0) {
			throw new EmptyIntStackException();
		}
		return stack[--pointer];
	}

	/**
	 * スタックの一番上のデータを覗き見する
	 * ポインタが0以下だったら何も覗き見できないので例外を投げる
	 * @return data
	 */
	public int peek() {
		if (pointer <= 0) {
			throw new EmptyIntStackException();
		}
		return stack[pointer - 1];
	}

	/**
	 * スタックに積まれているデータを削除する
	 * ポインタを使ってpush/pop/peekするので、ポインタを0にするだけでOK
	 * 実際に配列の中は削除されていないが、pushで上書きできるので問題ない
	 */
	public void clear() {
		pointer = 0;
	}

	/**
	 * スタック内のデータを探索し、インデックスを探す
	 * 見つからない場合は -1 を返す
	 * @param data
	 * @return index
	 */
	public int indexOf(int data) {
		for (int i = pointer - 1; i >= 0; i--) {
			if (stack[i] == data) {
				return i;
			}
		}
		return -1;
	}
}

EmptyIntStackException.java

public class EmptyIntStackException extends RuntimeException {
	public EmptyIntStackException() {
		super("スタックが空っぽだよ");
	}

	public EmptyIntStackException(String message) {
		super(message);
	}
}

OverflowIntStackException.java

public class OverflowIntStackException extends RuntimeException {
	public OverflowIntStackException() {
		super("スタックがいっぱいだよ");
	}

	public OverflowIntStackException(String message) {
		super(message);
	}
}