1. 根据Java所学内容，完成循环队列类的定义，并实现其基本操作。 2. 根据Java所学内容，完成链队列类的定义，并实现其基本操作。 3. 给定一个整数循环队列q，已知该队列当前元素个数为n，编写算法，实现利用队 列基本运算进队和出队第k个元素。

1. **循环队列类定义及基本操作**[^1]:

public class CircularQueue {
    private int[] queue;
    private int front; // 前端指针
    private int rear; // 后端指针
    private int capacity;

    public CircularQueue(int size) {
        queue = new int[size];
        front = -1;
        rear = -1;
        capacity = size;
    }

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

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

    // 查看队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    // 查看队列是否已满
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    // 返回队列大小（实际存储元素的数量）
    public int size() {
        return Math.abs(front - rear);
    }
}

2. **链队列类定义及基本操作**:

public class LinkedListQueue {
    private Node head;
    private Node tail;

    // ...省略节点类定义

    // 入队操作
    public void enqueue(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int item = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return item;
    }

    // ...其他辅助方法
}

3. **从循环队列中获取第k个元素**:

// 假设队列已经入满并且元素按照先进先出顺序排列
public int getKthElement(CircularQueue q, int k) {
    if (k < 1 || k > q.size()) {
        throw new IllegalArgumentException("Invalid index");
    }
    int count = 0;
    while (count < k && !q.isEmpty()) {
        q.dequeue();
        count++;
    }
    return q.isEmpty() ? -1 : q.dequeue(); // 如果k等于队列长度，返回最后一个元素，否则返回第k个元素
}