🧩

【Java】キュー

2024/11/24に公開

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

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

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

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

 基本用語確認データ構造
キュー

 リングバッファキューは配列を用いて実現するが、デキューを行うたびに全要素を先頭に向かってずらす必要がある。この作業を行わずにキューを実現させるために、配列の末尾が先頭につながるリングバッファ（ring buffer）というデータ構造を用いる。
リングバッファの実現方法として、論理的な先頭要素と末尾要素をそれぞれ変数（front, rear）を用いて識別することで実現する。
Java
package chap04;

public class IntQueue {
  
  private int[] queue;     // キュー用の配列
  private int   capacity;  // キューの容量
  private int   front;     // 先頭要素カーソル
  private int   rear;      // 末尾要素カーソル
  private int   num;       // 現在のデータ数
  
  //--- 実行時例外：キューが空 ---//
  public class EmptyIntqueueueException extends RuntimeException {
    
    // 例外発生時の処理は利用例にて記述する
    public EmptyIntqueueueException() {}
  }
  
  //--- 実行字例外：キューが満杯 ---//
  public class OverflowIntqueueueException extends RuntimeException {
    
    // 例外発生時の処理は利用例にて記述する
    public OverflowIntqueueueException() {}
  }
  
  //--- コンストラクタ ---//
  public IntQueue(int maxlen) {
    
    // 初期化
    capacity = maxlen;
    front    = 0;
    rear     = 0;
    num      = 0;
    
    // 例外：キュー本体用の配列を生成失敗
    try {
      queue = new int[capacity];
    } catch (OutOfMemoryError e) {
      capacity = 0;
    }
  }
  
  //--- エンキュー---//
  public int enqueue(int x) throws OverflowIntqueueueException {
    
    // キューが満杯のとき
    if (num >= capacity) {
      throw new OverflowIntqueueueException();
    }
    
    queue[rear++] = x;
    num++;
    
    // rearが配列の末尾に来たら
    if (rear == capacity) {
      // 先頭のインデックスに戻す
      rear = 0;
    }
    
    return x;
  }
  
  //--- デキュー ---//
  public int dequeue() throws EmptyIntqueueueException {
    
    // キューが空のとき
    if (num <= 0) {
      throw new EmptyIntqueueueException();
    }
    
    int x = queue[front++];
    num--;
    
    if (front == capacity) {
      front = 0;
    }
    
    return x;
  }
  
  //--- ピーク ---//
  public int peek() throws EmptyIntqueueueException {
    
    if (num <= 0) {
      throw new EmptyIntqueueueException();
    }
    
    return queue[front];
  }
  
  //--- キューを空にする ---//
  public void clear() {
    
    // 初期化
    front = 0;
    rear  = 0;
    num   = 0;
  }
  
  //--- インデックスを返す ---//
  public int indexOf(int x) {
    
    for (int i = 0; i < num; i++) {
      int idx = (i + front) % capacity;
      
      // 探索成功
      if (queue[idx] == x) {
        return idx;
      }
    }
    
    // 探索失敗
    return -1;
  }
  
  //--- キューの容量を返す ---//
  public int getCapacity() {
    return capacity;
  }
  
  //--- キューに蓄えられているデータ数を返す ---//
  public int size() {
    return num;
  }
  
  //--- キューは空であるか ---//
  public boolean isEmpty() {
    return num <= 0;
  }
  
  //--- キューは満杯であるか ---//
  public boolean isFull() {
    return num >= capacity;
  }
  
  //--- キュー内の全データを先頭→末尾の順に表示 ---//
  public void dump() {
    
    if (num <= 0) {
      System.out.println("キューは空です。");
    } else {
      for (int i = 0; i < num; i++) {
        System.out.print(queue[(i + front) % capacity] + " ");
      }
      System.out.println();
    }
  }
}

 利用例Java
package chap04;

import java.util.Scanner;

public class IntQueueTester {
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    IntQueue s = new IntQueue(64);
    
    System.out.println("【キュー】");
    
    while (true) {
      System.out.printf("現在のデータ数：%d / %d\n", s.size(), s.getCapacity());
      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.enqueue(x);
          } catch (IntQueue.OverflowIntqueueueException e) {
            System.out.println("キューが満杯です。");
          }
          break;
          
        // (2)デキュー
        case 2:
          try {
            x = s.dequeue();
            System.out.println("デキューしたデータは" + x + "です。");
          } catch (IntQueue.EmptyIntqueueueException e) {
            System.out.println("キューが空です。");
          }
          break;
          
        // (3)ピーク
        case 3:
          try {
            x = s.peek();
            System.out.println("ピークしたデータは" + x + "です。");
          } catch (IntQueue.EmptyIntqueueueException 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
デキューしたデータは1です。
現在のデータ数：3 / 64
(1)エンキュー　(2)デキュー　(3)ピーク　(4)ダンプ　(0)終了：4
2 3 4 
現在のデータ数：3 / 64
(1)エンキュー　(2)デキュー　(3)ピーク　(4)ダンプ　(0)終了：0
\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}

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

基本用語確認

リングバッファ

利用例

実行結果

Discussion