🧩

【Java】スタック

2024/11/23に公開

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。
ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。

アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。
【リンク紹介】

・Javaで学ぶアルゴリズムとデータ構造

・これまで書いたシリーズ記事一覧
この記事はデータ構造のスタックについてまとめました。

 基本用語確認
 データ構造データ単位とデータ自身との間の物理的または論理的な関係。

（「JIS X0015」より。JISとは日本産業規格のこと。）

 データ構造の例
 1.配列同一型のデータを直線状に連続して並べたデータ構造。配列本体内の個々の構成要素のアクセスは、インデックス式で行う。配列の一種としてハッシュ表、スタック、キューがある。

 1.1.スタック（stack）最後に入れられたデータが最初に取り出されるデータ構造。後入れ先出し（Last In First Out（LIFO））方式。

頂上（top）：スタックにおいて、最も奥（データが最初に入り、最後に取り出される）側のこと。

底（bottom）：スタックにおいて、データを出し入れする頂上の反対に位置する側のこと。

プッシュ（push）：スタックにデータを入れる操作。

ポップ（pop）：スタックからデータを取り出す操作。

ピーク（peek）：スタックの頂上のデータを閲覧する操作。

ダンプ（dump）：スタックに積まれているデータすべてを底から頂上へと順に表示する操作。

 1.2.キュー（queue）最初に入れられたデータが最初に取り出されるデータ構造。先入れ先出し（First In First Out（FIFO））方式。

先頭（front）：キューにおいて、データが取り出される側のこと。

末尾（rear）：キューにおいて、データが押し込まれる側のこと。

エンキュー（en-queue）：データを追加する操作。

デキュー（de-queue）：データを取り出す操作。

 2.リスト（list）データが順序付けられて並んだデータ構造。線形リスト（連結リスト）や循環リスト（重連結リスト）などがある。

 3.木（tree）（第9章をまとめた際にリンク付きで記述）

 スタックJava
public class IntStack {
  
  private int[] stack;   // スタック用の配列
  private int capacity;  // スタックの容量
  private int pointer;   // スタックポインタ
  
  //--- 実行時例外：スタックが空 ---//
  public class EmptyIntStackException extends RuntimeException {
    
    // 例外発生時の処理は利用例にて記述する
    public EmptyIntStackException() {}
  }
  
  //--- 実行時例外：スタックが満杯 ---//
  public class OverflowIntStackException extends RuntimeException {
    
    // 例外発生時の処理は利用例にて記述する
    public OverflowIntStackException() {}
  }
  
  
  //--- コンストラクタ ---//
  public IntStack(int maxlen) {
    
    // 初期化
    pointer  = 0;
    capacity = maxlen;
    
    // 例外：スタック用の配列の生成失敗
    try {
      stack = new int[capacity];
    } catch (OutOfMemoryError e) {
      capacity = 0;
    }
  }
  
  //--- プッシュ ---//
  public int push(int x) throws OverflowIntStackException {
    
    // スタックが満杯のとき
    if (pointer >= capacity) {
      throw new OverflowIntStackException();
    }
    return stack[pointer++] = x;
  }
  
  //--- ポンプ ---//
  public int pop() throws EmptyIntStackException {
    
    // スタックが空のとき
    if (pointer <= 0) {
      throw new EmptyIntStackException();
    }
    return stack[--pointer];
  }
  
  //--- ピーク(頂上のデータを覗き見) ---//
  public int peek() throws EmptyIntStackException {
    
    // スタックが空のとき
    if (pointer <= 0) {
      throw new EmptyIntStackException();
    }
    return stack[pointer - 1];
  }
  
  //--- スタックを空にする ---//
  public void clear() {
    pointer = 0;
  }
  
  //--- スタックからxを探してインデックスを返す ---//
  public int indexOf(int x) {
    for (int i = pointer - 1; i >= 0; i--) {
      if (stack[i] == x) {
        return i;
      }
    }
    return -1;
  }
  
  //--- スタックの容量を返す ---//
  public int getCapaciry() {
    return capacity;
  }
  
  //--- スタックに積まれているデータ数を返す ---//
  public int size() {
    return pointer;
  }
  
  //--- スタックは空であるか ---//
  public boolean isEmpty() {
    return pointer <= 0;
  }
  
  //--- スタックは満杯であるか ---//
  public boolean isFull() {
    return pointer >= capacity;
  }
  
  //--- スタック内の全データを底→頂上の順に表示 ---//
  public void dump() {
    
    if (pointer <= 0) {
      System.out.println("スタックは空です。");
    } else {      
      for (int i = 0; i < pointer; i++) {
        System.out.print(stack[i] + " ");
      }
      System.out.println();
    }
  }
}

 利用例Java
import java.util.Scanner;

public class IntStackTester {
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    IntStack s = new IntStack(64);

    System.out.println("【スタック】");
    
    while (true) {
      System.out.printf("現在のデータ数：%d / %d\n", s.size(), s.getCapaciry());
      System.out.print("(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：");
      
      int menu = stdIn.nextInt();
      // (0)終了
      if (menu == 0) break;
      
      int x;
      switch (menu) {
        // (1)プッシュ
        case 1:
          System.out.print("データ：");
          x = stdIn.nextInt();
          try {
            s.push(x);
          } catch (IntStack.OverflowIntStackException e) {
            System.out.println("スタックが満杯です。");
          }
          break;
          
        // (2)ポップ
        case 2:
          try {
            x = s.pop();
            System.out.println("ポップしたデータは" + x + "です。");
          } catch (IntStack.EmptyIntStackException e) {
            System.out.println("スタックが空です。");
          }
          break;
          
        // (3)ピーク
        case 3:
          try {
            x = s.peek();
            System.out.println("ピークしたデータは" + x + "です。");
          } catch (IntStack.EmptyIntStackException e) {
            System.out.println("スタックが空です。");
          }
          break;
          
        // (4)ダンプ
        case 4:
          s.dump();
          break;
      }
    }
  }
}

 実行結果【スタック】
現在のデータ数：0 / 64
(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：1
データ：1
現在のデータ数：1 / 64
(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：1
データ：2
現在のデータ数：2 / 64
(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：1
データ：3
現在のデータ数：3 / 64
(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：1
データ：4
現在のデータ数：4 / 64
(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：4
1 2 3 4 
現在のデータ数：4 / 64
(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：2
ポップしたデータは4です。
現在のデータ数：3 / 64
(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：4
1 2 3 
現在のデータ数：3 / 64
(1)プッシュ　(2)ポップ　(3)ピーク　(4)ダンプ　(0)終了：0
\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}

ご協力のほどよろしくお願いします。

基本用語確認

データ構造

データ構造の例

1.配列

1.1.スタック（stack）

1.2.キュー（queue）

2.リスト（list）

3.木（tree）

スタック

利用例

実行結果

Discussion