Java でキューの挿入および削除操作を実装する方法

Java でキューの挿入および削除操作を実装する方法

キューは、先入れ先出し (FIFO) 原則に従う一般的に使用されるデータ構造です。 Java では、配列またはリンク リストを使用してキューを実装できます。以下に 2 つの実装方法を紹介し、コード例を示します。

1. 配列を使用してキューを実装する:

配列を使用してキューを実装するという考え方は、キューの基礎となるデータ構造として配列を使用し、挿入を維持することです。先頭ポインタと末尾ポインタを維持して削除を実行します。

コード例:

public class ArrayQueue {
    private int[] queueArray;    // 队列数组
    private int front;  // 队头指针
    private int rear;   // 队尾指针
    private int maxSize;    // 队列的最大容量

    public ArrayQueue(int size) {
        queueArray = new int[size];
        maxSize = size;
        front = 0;
        rear = -1;
    }

    // 入队操作
    public void enqueue(int data) {
        if (isFull()) {
            throw new IllegalStateException("队列已满，无法入队");
        }
        rear++;
        queueArray[rear] = data;
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法出队");
        }
        int data = queueArray[front];
        front++;
        return data;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (rear + 1 == front);
    }

    // 判断队列是否已满
    public boolean isFull() {
        return (rear == maxSize - 1);
    }
}

2. リンク リストを使用してキューを実装する:

リンク リストを使用してキューを実装するというアイデアは次のとおりです。挿入および削除操作を実装するために、キューの先頭へのポインターとキューの末尾へのポインターを維持します。新しい要素が挿入されるたびに、その要素はキューの最後に追加され、キューの最後にあるポインタは新しい要素を指します。要素が削除されるたびに、キューの先頭にあるポインタは新しい要素を指します。次の要素。

コード例:

public class LinkedQueue {
    private Node front;    // 队头指针
    private Node rear;     // 队尾指针

    public LinkedQueue() {
        front = null;
        rear = null;
    }

    // 节点类
    private class Node {
        private int data;   // 数据
        private Node next;  // 指向下一个节点的指针

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 入队操作
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法出队");
        }
        int data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return data;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (front == null);
    }
}

上記は、Java でキューの挿入および削除操作を実装する 2 つの方法です。配列実装を使用するとランダム アクセスの効率がある程度向上しますが、リンク リスト実装を使用するとより柔軟でキューのサイズを動的に調整できます。実際のニーズに応じて適切な実装方法を選択してください。

以上がJava でキューの挿入および削除操作を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。