2. 如何实现一个队列（Queue）？请使用数组和链表分别实现，并解释它们的时间复杂度。

实现一个队列（Queue）可以使用多种数据结构，其中最常见的实现方式是使用数组和链表。队列是一种先进先出（FIFO, First In First Out）的数据结构，意味着第一个入队的元素也是第一个出队的元素。

一、使用数组实现队列

1. 基本思路

在数组中实现队列，可以使用两个指针 front 和 rear 来分别指向队列的头部和尾部。front 指向队列的第一个元素，rear 指向队列最后一个元素的下一个位置。

2. 具体实现

public class ArrayQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

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

    public void enqueue(int element) {
        if (isFull()) {
            throw new RuntimeException("Queue is full");
        }
        queue[rear] = element;
        rear = (rear + 1) % capacity; // 循环队列
        size++;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int element = queue[front];
        front = (front + 1) % capacity; // 循环队列
        size--;
        return element;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue[front];
    }

    public int getSize() {
        return size;
    }

    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(5);

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println("Dequeued: " + queue.dequeue());
        queue.enqueue(4);
        System.out.println("Front element: " + queue.peek());
        System.out.println("Queue size: " + queue.getSize());
    }
}

3. 时间复杂度

• 入队（enqueue）：O(1)，只需在数组的末尾插入元素。
• 出队（dequeue）：O(1)，只需从数组的头部删除元素。
• 空间复杂度：O(n)，其中 n 是数组的容量。

解释：

数组实现队列的入队和出队操作的时间复杂度都是 O(1)，因为我们只需要移动指针 front 和 rear。为了避免数组的末尾和开头不连续，通常会使用循环数组（即 rear 和 front 都在数组中循环移动）。

二、使用链表实现队列

1. 基本思路

使用链表实现队列时，可以定义两个指针 front 和 rear，分别指向链表的头结点和尾结点。链表的插入和删除操作在两端进行，因此可以很自然地实现队列的入队和出队操作。

2. 具体实现

public class LinkedListQueue {

    private static class Node {
        int data;
        Node next;

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

    private Node front;
    private Node rear;
    private int size;

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

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

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

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int element = front.data;
        front = front.next;
        if (front == null) {
            rear = null; // 如果队列为空，重置 rear 指针
        }
        size--;
        return element;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return front.data;
    }

    public int getSize() {
        return size;
    }

    public static void main(String[] args) {
        LinkedListQueue queue = new LinkedListQueue();

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println("Dequeued: " + queue.dequeue());
        queue.enqueue(4);
        System.out.println("Front element: " + queue.peek());
        System.out.println("Queue size: " + queue.getSize());
    }
}

3. 时间复杂度

• 入队（enqueue）：O(1)，只需在链表的末尾插入一个节点。
• 出队（dequeue）：O(1)，只需从链表的头部删除一个节点。
• 空间复杂度：O(n)，其中 n 是队列中的元素数量。

解释：

链表实现队列的入队和出队操作的时间复杂度都是 O(1)，因为我们只需操作链表的头结点和尾结点，且不需要移动数据。此外，链表的优势在于它不需要预先分配固定的内存空间，可以动态调整队列的大小。

三、数组实现与链表实现的比较

特性	数组实现队列	链表实现队列
时间复杂度（入队）	O(1)	O(1)
时间复杂度（出队）	O(1)	O(1)
空间复杂度	O(n)	O(n)
动态调整容量	不容易，需手动扩容	容易，链表可以动态调整
内存使用	可能浪费（未用完的数组空间）	更节省（按需分配）
实现复杂度	简单（数组固定大小）	稍复杂（需要维护指针）
边界处理	需要处理队列满和空的情况	不需要处理（链表可动态扩展）

四、总结

• 数组实现队列：适用于需要固定容量的队列，入队和出队操作时间复杂度都是 O(1)，但需要处理数组边界和扩容问题。
• 链表实现队列：适用于需要动态调整容量的队列，入队和出队操作同样是 O(1)，且内存使用更加灵活，但实现起来稍复杂一些，需要处理链表的指针操作。

根据具体的应用场景，选择合适的数据结构来实现队列，可以更好地满足性能和资源使用的需求。