队列介绍

队列是什么

队列（Queue）是一种基础的数据结构，它按照先进先出（First In First Out，FIFO）的原则存储和操作数据。队列可以看作是一种线性容器，只能在容器的一端进行插入操作（入队），在另一端进行删除操作（出队）。入队操作在队列的尾部添加元素，出队操作从队列的头部删除元素。

队列的基本操作包括入队（Enqueue）和出队（Dequeue）操作。队列还可以进行查看队头元素（Front）和判断队列是否为空（IsEmpty）等操作。

队列的应用非常广泛，比如任务调度、广度优先搜索、缓存等。在任务调度中，任务被放入队列中按照先进先出的原则进行调度；在广度优先搜索中，每个节点先被放入队列中，然后按照先进先出的顺序进行遍历；在缓存中，缓存中的数据按照先进先出的原则被替换。

队列可以使用数组或链表来实现。如果使用数组来实现队列，需要预先分配一定的内存空间，当队列满时需要重新分配更大的空间。如果使用链表来实现队列，可以动态地添加或删除节点，不需要预先分配内存空间。

队列的操作的时间复杂度通常为O(1)，因为所有操作都是在队头或队尾进行的，不需要遍历整个队列。但是，如果使用数组实现队列时，当队列满时需要重新分配更大的空间，这会带来额外的开销。

队列实现

public class Queue<V> {
    private int maxSize;
    private V[] array;
    private int front;
    private int back;
    private int currentSize;

    @SuppressWarnings("unchecked")
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        array = (V[]) new Object[maxSize];
        front = 0;
        back = -1;
        currentSize = 0;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public int getCurrentSize() {
        return currentSize;
    }

    public V top() {
        return array[front];
    }

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

    public boolean isFull() {
        return currentSize == maxSize;
    }

    public void enqueue(V value) {
        if (isFull())
            return;
        back = (back + 1) % maxSize; 
        array[back] = value;
        currentSize++;
    }

    public V dequeue() {
        if (isEmpty())
            return null;

        V temp = array[front];
        front = (front + 1) % maxSize; 
        currentSize--;

        return temp;
    }
}