この記事は、プロもくチャット AdventCalendar 2024の 15 日目の記事です！

はじめに

最近、書籍テスト駆動開発を読みました。
目から鱗の内容ばかりで、大変勉強になりました。
特に、テスト駆動開発の考え方を踏まえた試行錯誤を観察することができた点が非常に興味深かったです。

この内容をぜひ揮発させたくないと思い、テスト駆動開発を使ってスタックを実装してみることにしました。

この記事の成果物

下記リポジトリにて、テスト駆動開発でスタックを実装したコードを公開しています。
コミットメッセージをスタックの実装の見出しと連動させているので、よければご覧ください。

前提条件

利用端末 : MacBook Air Apple M3 macOS Sequoia 15.1.1
Javaの実行環境がインストールされていること
対象のディレクトリでJUnitが実行できること
- 参考 : Java 素人が VSCode で『テスト駆動開発』のために Java と JUnit の実行環境を構築

テスト駆動開発とは

テスト駆動開発（Test-Driven Development: TDD）は、ソフトウェア開発手法の一つとのこと。
すでに多くの記事で紹介されていますし、何よりも書籍テスト駆動開発を読んだ方が理解が深まると思いますので、ここで深くは触れません。

ただし、下記でスタックを実装していく際の道筋となるテスト駆動開発のサイクル、レッド・グリーン・リファクタリングについては触れておきたいと思います。

レッド・グリーン・リファクタリング

レッド (Red)

✅ 目的 : 実装すべき要件を明確にするために、失敗するテストを作成する。

新しい機能や改善点を表現するテストを作成。
テストが失敗することを確認。

ポイント: テストが失敗する

グリーン (Green)

✅ 目的 : テストを通すための最小限のコードを実装する。

レッドの段階で作成したテストが通るように、最小限のコードを記述。
コードの美しさや最適性よりも「テストを通す」ことに集中。

ポイント: 必要以上の実装をさけ、シンプルな実装を目指す。

リファクタリング (Refactoring)

✅ 目的 : コードの可読性や保守性を向上させる。

動作を変えずにコードの構造を改善。
- 重複コードの削除。
- 可読性の高女王。
- パフォーマンスの向上。
テストが通ることを確認。

ポイント: 安全な環境下でコードを改善し、長期的な保守性を高める。

スタックの概要

スタックはデータ構造の一種で、「後入れ先出し」（LIFO: Last In, First Out）の原則に基づいて動作します。従って、最後に追加された要素が最初に取り出されます。
この特性のため、スタックはデータの一時的な格納や管理に適しており、再帰的な処理や式の評価、ブラウザの履歴管理など、様々な用途で利用されるようです。( ChatGPT より)

主に下記表に示すメソッドを提供します。

メソッド名	目的	詳細
`isEmpty`	スタックが空であるかを判定します	- 戻り値: スタックが空の場合は `true`、それ以外は `false`
`push`	スタックに新しい要素を追加します	- 引数: 追加するデータ - 操作: 新しいノードを作成し、先頭に追加
`peek`	スタックの先頭要素を削除せずに取得します	- 戻り値: 先頭要素のデータ - 例外: スタックが空の場合はエラーをスロー
`pop`	スタックの先頭要素を削除し、そのデータを返します	- 戻り値: 先頭要素のデータ - 操作: 先頭要素を削除、次の要素を新しい先頭に設定
`size`	スタック内の要素数を返します	- 戻り値: 現在のスタック内の要素数（整数値）
`clear`	スタック内の全要素を削除します	- 操作: 全てのノードを削除し、スタックを空にします

`Stack`クラスと`StackNode`クラス

今回の実装では、Stackクラスと StackNodeクラスを用意します。
これらクラスの役割は下記の通りです。

Stackクラス : スタックの操作を提供するクラス。データを追加、取得、削除するためのメソッドを提供します。
StackNodeクラス : スタック内の各要素を表現するクラス。データと次の要素を保持します。

書籍良いコード/悪いコードで学ぶ設計入門-保守しやすい成長し続けるコードの書き方によると、次のような記載があります。

クラスが単体で正常に動作するよう設計する

この内容を踏まえると、StackクラスとStackNodeクラスを別々に実装することは低凝集の悪魔を呼び寄せるように思います。
Stackクラスは Stacknodeクラスがないと動作しないからです。

ただ、スタックの実装中に 1 クラスに全て実装する方法を思いつかなかったため、ひとまずこのような形で実装してみることにしました。

詳細は本書籍3.1 クラス単体で正常に動作するよう設計するを参照ください。

スタックの実装

レッド・グリーン・リファクタリングのサイクルに従って、スタックを実装します。
まずは 1 つの要素しか扱えないスタックを実装した後、複数の要素を扱えるように拡張していきます。

1. 1 つの要素しか扱えないスタック

1-1. `isEmpty`メソッドの実装

1-1-1. true が返却されることを確認するテスト

Stackクラスをインスタンス化した直後にisEmptyメソッドを呼び出すと、trueが返却されることを確認します。

StackTest.java

+package stack;
+
+import static org.junit.Assert.assertTrue;
+import org.junit.Test;
+
+public class StackTest {
+
+    @Test
+    public void testIsEmpty() {
+        Stack stack = new Stack();
+        assertTrue(stack.isEmpty());
+    }
+}

この状態でテストを実行すると、当然ながら失敗します。
Stackクラスを書いていないので笑

1-1-2. `isEmpty`メソッドの仮実装

続いて、1-1-1. で作成したテストが成功するようにisEmptyメソッドを仮実装します。

Stack.java

+package stack;
+
+class Stack {
+
+  boolean isEmpty() {
+    return true;
+  }
+}

こんなコードは全く意味がないですが、テストが成功することを確認するための最小限のコードです。
これでテストを実行すると、成功するはずです。

1-1-3. `isEmpty`メソッドの本実装

最後に、isEmptyメソッドを本実装します。
また、新しくStackNodeクラスを作成します。

Stack.java

package stack;

class Stack {
+  StackNode top;

  boolean isEmpty() {
-   return true;
+   return top == null;
  }
}

StackNode.java

+package stack;
+
+class StackNode {
+
+}

StackNodeクラスを追加した目的は、Stackクラスにインスタンス変数topを追加したことで発生したエラーを解消することのみです。
そのため、StackNodeクラスには何も実装していません。

StackクラスにStackNodeクラスのインスタンス変数topを追加し、isEmptyメソッドを修正しました。
topがnullであればスタックは空と判断します。
これでテストを実行すると、成功すると思います。

なお、isEmptyメソッドがfalseを返すテストは、pushメソッドを実装した後に実装します。

馬鹿らしいほど小刻みに進めていますが、この歩幅は適宜調整します。
書籍によると、「コードに不安を感じるならば、歩幅を小さくするべき」とのことです。

非常に細かなステップを窮屈に感じるならば、歩幅を大きくする。不安を感じるならば、歩幅を小さくする。TDD とは、あちらへ少し、こちらへ少しといった感じで舵を取るプロセスだ。正しい歩幅などというものは、未来永劫に存在しない。

テスト駆動開発 P. 117

1-2. `push`メソッドの実装

1-2-1. `isEmpty`メソッドの戻り値が`false`であることを確認するテスト

pushメソッドを実行した直後にisEmptyメソッドを呼び出すと、falseが返却されることを確認します。
当然このテストは失敗するはずです。

StackTest.java

package stack;

import static org.junit.Assert.assertTrue;
import org.junit.Test;

public class StackTest {

    @Test public void testIsEmpty() { Stack stack = new Stack();
        assertTrue(stack.isEmpty());

+        stack.push(1);
+        assertFalse(stack.isEmpty());
    }
}

1-2-2. インスタンス変数`top`の値が`push`メソッドの引数と等しいことを確認するテスト

pushメソッドを実行した直後に、インスタンス変数topの値がpushメソッドの引数と等しいことを確認します。
今回は新しくtestPushメソッドを追加することにしました。
このテストも失敗するはずです。

StackTest.java

package stack;

+import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
        Stack stack = new Stack();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

+    @Test
+    public void testPush() {
+        Stack stack = new Stack();
+        stack.push(1);
+        assertEquals(1, stack.top.value);
+    }
}

assertEqualsメソッドの引数としてstack.top.valueを指定しています。
メソッドチェーンでインスタンス変数にアクセスするのは嫌ですが、このステップはアサーションを行うことが目的であるためこのまま進めます。

1-2-3. `push`メソッドの実装

Stackクラスにpushメソッドを追加します。
pushメソッドの引数として受け取った値でStackNodeクラスをインスタンス化し、インスタンス変数topに代入します。

Stack.java

package stack;

class Stack {
  StackNode top;

  boolean isEmpty() {
    return top == null;
  }

+  void push(int value) {
+    top = new StackNode(value);
+  }
+}

1-2-4. `StackNode`クラスのコンストラクタを追加

StackNodeクラスにコンストラクタがないと怒られました。
コンストラクタを追加します。
また、StackNodeクラスにインスタンス変数valueも追加しました。

StackNode.java

package stack;

class StackNode {
+  int value;

+  StackNode(int value) {
+    this.value = value;
+  }
+}

このステップの目的はStackNodeクラスにコンストラクタを追加することです。
そのため、変数valueの可視性をprivateにするか否かは考慮しません。

1-3. `peek` メソッドの実装

続いて、peekメソッドを実装します。

1-3-1. `peek` メソッドの戻り値が`push`メソッドの引数と等しいことを確認するテスト

まずはテストコードからです。
pushメソッドを実行した直後にpeekメソッドを呼び出すと、pushメソッドの引数と等しい値が返却されることを確認します。

StackTest.javaに新しくtestPeekメソッドを追加しました。

StackTest.java

package stack;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
        Stack stack = new Stack();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

    @Test
    public void testPush() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.top.value);
    }

+    @Test
+    public void testPeek() {
+        Stack stack = new Stack();
+        stack.push(1);
+        assertEquals(1, stack.peek());
+    }
}

当然、peekメソッドがないと怒られました。
次のステップに進みます。

1-3-2. `peek` メソッドの実装

Stackクラスにpeekメソッドを実装します。
以下のようなコードを追加しました。

Stack.java

package stack;

class Stack {
  StackNode top;

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
    top = new StackNode(value);
  }

+  int peek() {
+    return top.value;
+  }
}

これでテストを実行すると、成功するはずです。

1-3-3. スタックが空の場合に`peek` メソッドを呼び出すと例外がスローされることを確認するテスト

peekメソッドはスタックが空の場合に例外をスローする必要があります。
StackEmptyExceptionという例外クラスを新規作成し、peekメソッドがスローする想定にします。

そして、これをテストするためにtestPeekThrowsExceptionWhenStackIsEmptyメソッドを追加しました。

StackTest.java

package stack;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
        Stack stack = new Stack();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

    @Test
    public void testPush() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.top.value);
    }

    @Test
    public void testPeek() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.peek());
    }

+    @Test
+    public void testPeekThrowsExceptionWhenStackIsEmpty() {
+        Stack stack = new Stack();
+
+        try {
+            stack.peek();
+            fail("peek() should throw an exception when the stack is empty");
+        } catch (Exception e) {
+            assertTrue(e instanceof StackEmptyException);
+            assertEquals("Stack is empty", e.getMessage());
+        }
+    }
+}

failメソッドを使って、peekメソッドが例外をスローしなかった場合にテストが失敗するようにしました。

1-3-4. `peek`メソッドの例外処理を実装

上記テストコードを通過するために、peekメソッドに例外処理を追加します。
StackEmptyExceptionクラスを新規作成しつつ、peekメソッドが本例外をスローするようにします。

StackEmptyException.java

+package stack;
+
+class StackEmptyException extends RuntimeException {
+    public StackEmptyException() {
+        super("Stack is empty");
+    }
+}

Stack.java

package stack;

class Stack {
  StackNode top;

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
    top = new StackNode(value);
  }

  int peek() {
+    if (isEmpty()) {
+      throw new StackEmptyException();
+    }

    return top.value;
  }
}

これでテストを実行すると、成功するはずです。

1-3-5. テストコードのリファクタリング

testPushメソッドとtestPeekメソッドで同じ処理をしているため、リファクタリングします。
testPeekメソッドを削除し、testPushメソッドにpeekメソッドのテストを追加しました。

StackTest.java

package stack;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
        Stack stack = new Stack();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

    @Test
-    public void testPush() {
+    public void testPushAndPeek() {
        Stack stack = new Stack();
        stack.push(1);
-        assertEquals(1, stack.top.value);
+        assertEquals(1, stack.peek());
    }

-    @Test
-    public void testPeek() {
-        Stack stack = new Stack();
-        stack.push(1);
-        assertEquals(1, stack.peek());
-    }

    @Test
    public void testPeekThrowsExceptionWhenStackIsEmpty() {
        Stack stack = new Stack();

        try {
            stack.peek();
            fail("peek() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }
}

1-4. `pop`メソッドの実装

1-4-1. `pop`メソッドの戻り値が`push`メソッドの引数と等しいことを確認するテスト

pushメソッドを実行した直後にpopメソッドを呼び出すと、pushメソッドの引数と等しい値が返却されることを確認します。
新しくtestPushAndPopメソッドを追加しました。

StackTest.java

package stack;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
        Stack stack = new Stack();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

    @Test
    public void testPushAndPeek() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.peek());
    }

+    @Test
+    public void testPushAndPop() {
+        Stack stack = new Stack();
+        stack.push(1);
+        assertEquals(1, stack.pop());
+    }

    @Test
    public void testPeekThrowsExceptionWhenStackIsEmpty() {
        Stack stack = new Stack();

        try {
            stack.peek();
            fail("peek() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }
}

1-4-2. `pop`メソッドの実装

Stackクラスにpopメソッドを追加します。

なお、popメソッドはpeekメソッドと同様にスタックが空の場合に例外をスローする必要があります。
今回はこのステップで例外処理も実装してしまいました。

Stack.java

package stack;

class Stack {
  StackNode top;

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
    top = new StackNode(value);
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

+  int pop() {
+    if (isEmpty()) {
+      throw new StackEmptyException();
+    }
+
+    int value = top.value;
+    top = null;
+    return value;
+  }
+}

これでテストを実行すると、成功するはずです。

1-4-3. スタックが空の場合に`pop`メソッドを呼び出すと例外がスローされることを確認するテスト

スタックが空の場合にpopメソッドが例外をスローすることを確認するために、testPopThrowsExceptionWhenStackIsEmptyメソッドを追加しました。

StackTest.java

package stack;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
        Stack stack = new Stack();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

    @Test
    public void testPushAndPeek() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.peek());
    }

    @Test
    public void testPushAndPop() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.pop());
    }

+    @Test
+    public void testPopThrowsExceptionWhenStackIsEmpty() {
+        Stack stack = new Stack();
+
+        try {
+            stack.pop();
+            fail("pop() should throw an exception when the stack is empty");
+        } catch (Exception e) {
+            assertTrue(e instanceof StackEmptyException);
+            assertEquals("Stack is empty", e.getMessage());
+        }
+    }

    @Test
    public void testPeekThrowsExceptionWhenStackIsEmpty() {
        Stack stack = new Stack();

        try {
            stack.peek();
            fail("peek() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }
}

このテストも成功するはずです。

例外処理のテストコードは、peekメソッドのテストコードとほぼ同じです。
ただ、今回はこのままにしようと思います。
テストコードが冗長である一方で、各々のテストコードは別々の責務を持っていると考えたためです。
この判断についてご意見があれば、コメントいただけると嬉しいです！

2. 複数の要素を扱えるスタック

ここまでで、スタックが 1 つの要素しか扱えない状態まで実装しました。
次は、複数の要素を扱えるように拡張していきます。

2-1. スタックの拡張

2-1-1. スタックが LIFO 動作することを確認するテスト

pushメソッドを複数回実行した後、popメソッドを同回数実行すると、pushメソッドで追加した値を逆順で取得できることを確認します。
また、最後にスタックが空になることも確認します。

StackTest.java

package stack;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
        Stack stack = new Stack();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

    @Test
    public void testPushAndPeek() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.peek());
    }

    @Test
    public void testPushAndPop() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.pop());
    }

    @Test
    public void testPopThrowsExceptionWhenStackIsEmpty() {
        Stack stack = new Stack();

        try {
            stack.pop();
            fail("pop() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }

    @Test
    public void testPeekThrowsExceptionWhenStackIsEmpty() {
        Stack stack = new Stack();

        try {
            stack.peek();
            fail("peek() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }

+    @Test
+    public void testPushMultipleElementsAndPopInOrder() {
+        Stack stack = new Stack();
+        stack.push(1);
+        stack.push(2);
+        stack.push(3);
+
+        assertEquals(3, stack.pop());
+        assertEquals(2, stack.pop());
+        assertEquals(1, stack.pop());
+        assertTrue(stack.isEmpty());
+    }
+}

このテストは失敗するはずです。

2-1-2. スタックの拡張

StackNodeクラスにインスタンス変数nextを追加します。
nextは次の要素を指す参照という建て付けです。

StackNode.java

package stack;

class StackNode {
  int value;
+  StackNode next;

-  StackNode(int value) {
+  StackNode(int value, StackNode next) {
    this.value = value;
+    this.next = next;
  }
}

2-1-3. `push`メソッドの修正

StackNodeクラスのコンストラクタを変更したため、pushメソッドでエラーが発生しています。
pushメソッドを修正します。

Stack.java

package stack;

class Stack {
  StackNode top;

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
-    top = new StackNode(value);
+    top = new StackNode(value, top);
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
    top = null;
    return value;
  }
}

2-1-4. `pop`メソッドの拡張

今までのpopメソッドは、Stackクラスのインスタンス変数topにnullを代入していました。
これを修正し、インスタンス変数topのプロパティnextをtopに設定するように変更します。

Stack.java

package stack;

class Stack {
  StackNode top;

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
    top = new StackNode(value, top);
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
-    top = null;
+    top = top.next;
    return value;
  }
}

2-2. `size`メソッドの実装

2-2-1. スタックの要素数を取得する`size`メソッドのテスト

sizeメソッドを追加し、スタックの要素数を取得するテストコードを追加します。

StackTest.java

package stack;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
        Stack stack = new Stack();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

    @Test
    public void testPushAndPeek() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.peek());
    }

    @Test
    public void testPushAndPop() {
        Stack stack = new Stack();
        stack.push(1);
        assertEquals(1, stack.pop());
    }

    @Test
    public void testPopThrowsExceptionWhenStackIsEmpty() {
        Stack stack = new Stack();

        try {
            stack.pop();
            fail("pop() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }

    @Test
    public void testPeekThrowsExceptionWhenStackIsEmpty() {
        Stack stack = new Stack();

        try {
            stack.peek();
            fail("peek() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }

    @Test
    public void testPushMultipleElementsAndPopInOrder() {
        Stack stack = new Stack();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        assertEquals(3, stack.pop());
        assertEquals(2, stack.pop());
        assertEquals(1, stack.pop());
        assertTrue(stack.isEmpty());
    }

+    @Test
+    public void testSize() {
+        Stack stack = new Stack();
+        assertEquals(0, stack.size());
+
+        stack.push(1);
+        assertEquals(1, stack.size());
+
+        stack.push(2);
+        assertEquals(2, stack.size());
+
+        stack.pop();
+        assertEquals(1, stack.size());
+    }
}

2-2-2. `size`メソッドの実装

Stackクラスにsizeメソッドを追加します。
この時、新しくStackクラスにインスタンス変数stackSizeを追加し、pushメソッドとpopメソッドで値を更新します。
sizeメソッドはstackSizeの値を返却する実装です。

Stack.java

package stack;

class Stack {
  StackNode top;
  int stackSize;

+  Stack() {
+    top = null;
+    stackSize = 0;
+  }

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
    top = new StackNode(value, top);
+    stackSize++;
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
    top = top.next;
+    stackSize--;

    return value;
  }

+  int size() {
+    return stackSize;
+  }
}

これでテストを実行すると、成功するはずです。

これで、スタックの実装は完了です！

3. スタックのリファクタリング

ここからは、実装したスタックのコードをリファクタリングしていきます。

3-1. `Stack`クラスと`StackNode`クラスの統合

StackクラスとstackNodeクラスで述べた通り、StackクラスとStackNodeクラスを統合します。

3-1-1. 文字列`StackNode`の削除

Stackクラスから文字列StackNodeを削除します。

Stack.java

package stack;

class Stack {
-  StackNode top;
+  Stack top;
  int stackSize;

  Stack() {
    top = null;
    stackSize = 0;
  }

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
-    top = new StackNode(value, top);
+    top = new Stack(value, top);
    stackSize++;
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
    top = top.next;
    stackSize--;

    return value;
  }

  int size() {
    return stackSize;
  }
}

3-1-2. `Stack`クラスにコンストラクタを追加

3-1-1の変更により、pushメソッド内でエラーが発生しています。
解消するために、Stackクラスにコンストラクタを追加しました。

Stack.java

package stack;

class Stack {
  Stack top;
  Stack next;
  int value;
  int stackSize;

+  Stack() {
+    top = null;
+    stackSize = 0;
+  }
+
+  private Stack(int value, Stack next) {
+    this.value = value;
+    this.next = next;
+  }

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
    top = new Stack(value, top);
    stackSize++;
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
    top = top.next;
    stackSize--;

    return value;
  }

  int size() {
    return stackSize;
  }
}

テストを実行すると、成功することを確認できました。
テストコードがあるおかげで、動作が変わっていないことに自信を持てます。

3-2. `Stack`クラス内の可視性・不変性を変更

3-2-1. インスタンス変数の可視性を変更

Stackクラスのインスタンス変数top、stackSize、value、stackSizeの可視性を変更します。

Stack.java

package stack;

class Stack {
+  private Stack top;
+  private Stack next;
+  private int value;
+  private int stackSize;

  Stack() {
    top = null;
    stackSize = 0;
  }

  private Stack(int value, Stack next) {
    this.value = value;
    this.next = next;
  }

  boolean isEmpty() {
    return top == null;
  }

  void push(int value) {
    top = new Stack(value, top);
    stackSize++;
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
    top = top.next;
    stackSize--;

    return value;
  }

  int size() {
    return stackSize;
  }
}

3-2-2. メソッド引数の不変性を変更

Stackクラスのコンストラクタ・pushメソッドの引数をfinalに変更します。

Stack.java

package stack;

class Stack {
  private Stack top;
  private Stack next;
  private int value;
  private int stackSize;

  Stack() {
    top = null;
    stackSize = 0;
  }

-  private Stack(int value, Stack next) {
+  private Stack(final int value, final Stack next) {
    this.value = value;
    this.next = next;
  }

  boolean isEmpty() {
    return top == null;
  }

-  void push(int value) {
+  void push(final int value) {
    top = new Stack(value, top);
    stackSize++;
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
    top = top.next;
    stackSize--;

    return value;
  }

  int size() {
    return stackSize;
  }
}

3-3. ファクトリメソッドによるコンストラクタの隠蔽

3-3-1. ファクトリメソッドの追加

Stackクラスにファクトリメソッドを追加し、コンストラクタを隠蔽します。

Stack.java

package stack;

class Stack {
  private Stack top;
  private Stack next;
  private int value;
  private int stackSize;

  private Stack() {
    top = null;
    stackSize = 0;
  }

+  private Stack(final int value, final Stack next) {
    this.value = value;
    this.next = next;
  }

+  static Stack create() {
+    return new Stack();
+  }

  boolean isEmpty() {
    return top == null;
  }

  void push(final int value) {
    top = new Stack(value, top);
    stackSize++;
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
    top = top.next;
    stackSize--;

    return value;
  }

  int size() {
    return stackSize;
  }
}

3-3-2. テストコードの修正

Stackクラスのコンストラクタがprivateになったため、テストコードを修正します。

StackTest.java

package stack;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class StackTest {

    @Test
    public void testIsEmpty() {
-        Stack stack = new Stack();
+        Stack stack = Stack.create();
        assertTrue(stack.isEmpty());

        stack.push(1);
        assertFalse(stack.isEmpty());
    }

    @Test
    public void testPushAndPeek() {
-        Stack stack = new Stack();
+        Stack stack = Stack.create();
        stack.push(1);
        assertEquals(1, stack.peek());
    }

    @Test
    public void testPushAndPop() {
-        Stack stack = new Stack();
+        Stack stack = Stack.create();
        stack.push(1);
        assertEquals(1, stack.pop());
    }

    @Test
    public void testPopThrowsExceptionWhenStackIsEmpty() {
-        Stack stack = new Stack();
+        Stack stack = Stack.create();

        try {
            stack.pop();
            fail("pop() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }

    @Test
    public void testPeekThrowsExceptionWhenStackIsEmpty() {
-        Stack stack = new Stack();
+        Stack stack = Stack.create();

        try {
            stack.peek();
            fail("peek() should throw an exception when the stack is empty");
        } catch (Exception e) {
            assertTrue(e instanceof StackEmptyException);
            assertEquals("Stack is empty", e.getMessage());
        }
    }

    @Test
    public void testPushMultipleElementsAndPopInOrder() {
-        Stack stack = new Stack();
+        Stack stack = Stack.create();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        assertEquals(3, stack.pop());
        assertEquals(2, stack.pop());
        assertEquals(1, stack.pop());
        assertTrue(stack.isEmpty());
    }

    @Test
    public void testSize() {
-        Stack stack = new Stack();
+        Stack stack = Stack.create();
        assertEquals(0, stack.size());

        stack.push(1);
        assertEquals(1, stack.size());

        stack.push(2);
        assertEquals(2, stack.size());

        stack.pop();
        assertEquals(1, stack.size());
    }
}

3-4. `Node`クラスの追加

以前StackNodeクラスをStackクラスに統合しましたが、Stackクラスの内部クラスにしようと思います。

3-4-1. `Node`クラスの追加

Stackクラス内にNodeクラスを追加します。

Stack.java

package stack;

class Stack {
-  private Stack top;
-  private Stack next;
-  private int value;
+  private Node top;
  private int stackSize;

+  private class Node {
+    private final Node next;
+    private final int value;
+
+    private Node(final int value, final Node next) {
+      this.value = value;
+      this.next = next;
+    }
+  }

  private Stack() {
    top = null;
    stackSize = 0;
  }

-    private Stack(final int value, final Stack next) {
-      this.value = value;
-      this.next = next;
-    }

  static Stack create() {
    return new Stack();
  }

  boolean isEmpty() {
    return top == null;
  }

  void push(final int value) {
-    top = new Stack(value, top);
+    top = new Node(value, top);
    stackSize++;
  }

  int peek() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    return top.value;
  }

  int pop() {
    if (isEmpty()) {
      throw new StackEmptyException();
    }

    int value = top.value;
    top = top.next;
    stackSize--;

    return value;
  }

  int size() {
    return stackSize;

参考