Java 数据结构篇-用链表、数组实现队列（数组实现：循环队列）

队列是一种重要的数据结构，具有先进先出（FIFO）的特性，广泛应用于各种计算机科学领域，例如操作系统的进程调度、任务管理等。在Java中，我们可以使用链表和数组（循环队列）来实现队列。本文将介绍这两种实现方法，并提供相应的代码示例。

一、使用链表实现队列

链表是一种动态数据结构，具有灵活的内存管理优势。我们可以借助链表来实现队列的基本操作，主要包括入队（enqueue）和出队（dequeue）。

下面是一个使用链表实现队列的示例代码：

class Node {
    int data;
    Node next;

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

class LinkedListQueue {
    private Node front;
    private Node rear;
    private int size;

    LinkedListQueue() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    // 入队
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    // 出队
    public int dequeue() {
        if (front == null) {
            throw new IllegalStateException("Queue is empty");
        }
        int data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        size--;
        return data;
    }

    // 获取队列大小
    public int getSize() {
        return size;
    }

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

在上面的代码中，我们定义了一个节点类Node，并通过LinkedListQueue类实现了队列的基本功能。在enqueue方法中，我们将新的节点添加到队列尾部；在dequeue方法中，我们从队列头部移除节点并返回其值。

二、使用循环数组实现队列

循环队列是一种利用数组实现的队列，其优势在于能够有效利用存储空间。循环队列利用模运算来处理数组的尾部与头部之间的关系，从而实现循环的效果。

下面是一个使用循环数组实现队列的示例代码：

class CircularArrayQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int capacity;

    CircularArrayQueue(int size) {
        capacity = size;
        queue = new int[capacity];
        front = rear = 0;
    }

    // 入队
    public void enqueue(int data) {
        if ((rear + 1) % capacity == front) {
            throw new IllegalStateException("Queue is full");
        }
        queue[rear] = data;
        rear = (rear + 1) % capacity;
    }

    // 出队
    public int dequeue() {
        if (front == rear) {
            throw new IllegalStateException("Queue is empty");
        }
        int data = queue[front];
        front = (front + 1) % capacity;
        return data;
    }

    // 获取队列大小
    public int size() {
        return (rear - front + capacity) % capacity;
    }

    public boolean isEmpty() {
        return front == rear;
    }
}

在循环数组实现中，我们使用一个数组和两个指针（front和rear）来表示队列的头尾。同时，为了避免数组溢出，当队列已满时，我们通过(rear + 1) % capacity来判断。

总结

通过以上示例，我们可以看到使用链表和循环数组都能有效地实现队列。链表实现的队列在动态内存管理上具有优势，而循环数组实现的队列则在空间利用上表现更佳。选择哪种实现方式通常取决于具体的应用场景和需求。在实际开发中，根据需求的不同使用合适的数据结构将大大提升程序的性能和可维护性。