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

1. **循环队列（Circular Queue）的Java实现**:

public class CircularQueue {
    private int[] queue;
    private int front, rear, size;

    // 初始化队列
    public CircularQueue(int capacity) {
        this.queue = new int[capacity];
        this.front = -1;
        this.rear = -1;
        this.size = 0;
    }

    // 插入元素 (先进先出)
    public boolean enqueue(int value) {
        if (isFull()) return false;
        if (front == -1) front = 0;
        rear = (rear + 1) % queue.length; // 循环更新
        queue[rear] = value;
        size++;
        return true;
    }

    // 删除元素 (先进后出)
    public int dequeue() {
        if (isEmpty()) return -1;
        int removedValue = queue[front]; // 保存并删除第一个元素
        if (front == rear) { // 队列只剩下一个元素
            front = rear = -1;
        } else {
            front = (front + 1) % queue.length; // 更新front
        }
        size--;
        return removedValue;
    }

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

    // 检查队列是否满
    public boolean isFull() {
        return rear == (front + size - 1) % queue.length;
    }

    // 返回队列大小
    public int getSize() {
        return size;
    }
}

2. **链式队列（Linked Queue）的Java实现**:

public class LinkedListQueue {
    private Node head, tail;
    
    // 定义节点类
    static class Node {
        int data;
        Node next;
        
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

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

    // 入队
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    // 出队
    public int dequeue() {
        if (head == null) return -1;
        int removedValue = head.data;
        head = head.next;
        if (head == null) tail = null; // 如果头也是尾，清空队列
        return removedValue;
    }

    // 检查队列是否为空
    public boolean isEmpty() {
        return head == null;
    }
}

// 算法示例：获取循环队列第k个元素
int kthElement(CircularQueue q, int n, int k) {
    int index = (front + k - 1) % q.getSize(); // 计算相对位置
    if (index < size) { // 如果在队列内
        return q.dequeue(); // 调用dequeue获取对应元素
    } else {
        return q.enqueue(0); // 若超出范围，从队首开始计算，直到找到第k个元素
    }
}