【数据结构与算法】之队列详解

public class LinkedListQueue<T> {
    private Node<T> head; // 指向队首节点的指针
    private Node<T> tail; // 指向队尾节点的指针
    private int size; // 记录队列大小

    private static class Node<T> { // 链表节点的内部类
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public boolean isEmpty() {
        return size == 0; // 或 head == null
    }

    public int size() {
        return size;
    }


    //入队
    public void enqueue(T item) {
        Node<T> newNode = new Node<>(item);
        if (isEmpty()) {
            head = newNode; // 如果队列为空，新节点既是队首也是队尾
        } else {
            tail.next = newNode; // 否则，将新节点添加到队尾
        }
        tail = newNode; // 更新队尾指针
        size++;
    }


    //出队
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty"); // 使用更具体的异常类型
        }
        T data = head.data;
        head = head.next; // 更新队首指针
        if (head == null) { // 如果队列只有一个元素，出队后队列变空，tail 也需要置空
            tail = null;
        }
        size--;
        return data;
    }


    //返回队首元素
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return head.data;
    }
}

public class ArrayQueue<T> {
    private T[] data;
    private int head; // 队首指针
    private int tail; // 队尾指针
    private int capacity; // 数组容量
    private int size; // 队列大小

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.data = (T[]) new Object[capacity];
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }

    public boolean isEmpty() {
        return size == 0; // 或 head == tail
    }

    public boolean isFull() {
        return size == capacity; // 使用 size 判断是否满
    }

    public int size() { return size; }



    //入队
    public void enqueue(T item) {
        if (isFull()) {
            //throw new RuntimeException("Queue is full");
            resizeArray(); //  扩容操作
        }
        data[tail] = item;
        tail = (tail + 1) % capacity; // 环形数组的关键：使用模运算
        size++;
    }


    //出队
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T item = data[head];
        data[head] = null; //  避免对象游离
        head = (head + 1) % capacity; // 环形数组的关键：使用模运算
        size--;
        return item;
    }


    //返回队首元素
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return data[head];
    }


    private void resizeArray() { // 扩容方法示例
        int newCapacity = capacity * 2;
        T[] newData = (T[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(head + i) % capacity];
        }
        data = newData;
        head = 0;
        tail = size;
        capacity = newCapacity;
    }
}

return tail == size; //队列大小

return size == 0;

return size = capacity; //数组容量

return (tail + 1) % length == head;