Java で先入れ先出しデータ構造を実装の方法

1年 ago
桜, 春樹
1 minute

Javaでは、以下のデータ構造を使用して先入れ先出し(FIFO)特性を実装できます:

  1. キュー（Queue）：キューとは、先入れ先出しの線形データ構造であり、JavaではLinkedListクラスを使用して実装します。LinkedListクラスには、add()、offer()、remove()、poll()など、一般的なキュー操作メソッドが用意されています。
import java.util.LinkedList;
import java.util.Queue;

public class FIFOQueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // 入队操作
        queue.add("A");
        queue.add("B");
        queue.offer("C");

        // 出队操作
        String element = queue.remove(); // A
        System.out.println(element);

        String peekElement = queue.peek(); // B
        System.out.println(peekElement);
    }
}
  1. スタック（Stack）：スタックは本来後入れ先出し（LIFO）のデータ構造だが、 LinkedList クラスの push() と pop() メソッドを利用することで先入れ先出しの挙動をシミュレートできる。
import java.util.LinkedList;

public class FIFOStackExample {
    public static void main(String[] args) {
        LinkedList<String> stack = new LinkedList<>();

        // 入栈操作
        stack.push("A");
        stack.push("B");
        stack.push("C");

        // 出栈操作
        String element = stack.pop(); // C
        System.out.println(element);

        String peekElement = stack.peek(); // B
        System.out.println(peekElement);
    }
}
  1. 配列（Array）：配列を使えば先入れ先出しを実現することができます．ポインタを使ってキューの先頭を指し示し、出列操作の度にポインタを一つ後ろに動かします．
public class FIFODynamicArray {
    private int[] array;
    private int head;
    private int tail;
    private int size;

    public FIFODynamicArray(int capacity) {
        array = new int[capacity];
        head = 0;
        tail = 0;
        size = 0;
    }

    public void enqueue(int element) {
        if (size == array.length) {
            throw new IllegalStateException("Queue is full");
        }
        
        array[tail] = element;
        tail = (tail + 1) % array.length;
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            throw new IllegalStateException("Queue is empty");
        }
        
        int element = array[head];
        head = (head + 1) % array.length;
        size--;

        return element;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}
bannerAds