CS61B 课程笔记（HW1 Packages Interfaces Generics Exceptions Iteration）

GitHub 链接

获取框架文件

执行 git pull skeleton master 获取作业的框架代码。

介绍

在本次作业中，您将学习如何编写和使用包，获得关于接口和抽象类的实际操作经验。您将实现一个简单的数据结构，并使用该数据结构来实现一个算法。最后，为数据结构添加迭代和异常支持。

---

包的概念

包是一个命名空间，用于组织一组相关的类和接口。它使得代码更易于管理，并避免命名冲突。使用包可以提高代码的可读性和可维护性。

合成器包

本次作业将创建一个合成器包，用于模拟乐器声音。包包括以下组件：

• BoundedQueue：接口，声明实现类必须实现的方法。
• AbstractBoundedQueue：抽象类，实现 BoundedQueue，捕获方法之间的冗余。
• ArrayRingBuffer：扩展 AbstractBoundedQueue，使用数组实现 BoundedQueue。
• GuitarString：实现 Karplus-Strong 算法，合成吉他弦的声音。

---

任务 1: BoundedQueue

接口的定义

接口定义了一个协议，类与外部世界之间的正式契约。实现接口的类必须实现接口定义的所有方法。

实现要求

创建 BoundedQueue.java，定义以下方法：

public interface BoundedQueue<T> {
    int capacity();     // 返回缓冲区的大小
    int fillCount();    // 返回当前缓冲区中的项目数
    void enqueue(T x);  // 将项目 x 添加到末尾
    T dequeue();        // 删除并返回前面的项目
    T peek();           // 返回前面的项目但不删除

    default boolean isEmpty() { // 判断缓冲区是否为空
        return fillCount() == 0;
    }

    default boolean isFull() {  // 判断缓冲区是否满
        return fillCount() == capacity();
    }
}

示例

BoundedQueue<Double> queue = new ArrayRingBuffer<>(4);
queue.isEmpty();       // 返回 true
queue.enqueue(9.3);    // 9.3
queue.enqueue(15.1);   // 9.3  15.1
queue.enqueue(31.2);   // 9.3  15.1  31.2
queue.isFull();        // 返回 false
queue.enqueue(-3.1);   // 9.3  15.1  31.2  -3.1
queue.isFull();        // 返回 true
queue.dequeue();       // 返回 9.3
queue.peek();          // 返回 15.1

实现类

接下来，我们将实现一个具体的类 ArrayRingBuffer，它实现了 BoundedQueue 接口。

ArrayRingBuffer 类的实现

public class ArrayRingBuffer<T> implements BoundedQueue<T> {
    private T[] buffer;    // 存储元素的数组
    private int capacity;   // 容量
    private int fillCount;  // 当前元素数量
    private int first;      // 指向队首的索引
    private int last;       // 指向队尾的索引

    @SuppressWarnings("unchecked")
    public ArrayRingBuffer(int capacity) {
        this.capacity = capacity;
        this.buffer = (T[]) new Object[capacity]; // 创建泛型数组
        this.fillCount = 0;
        this.first = 0;
        this.last = 0;
    }

    @Override
    public int capacity() {
        return capacity;
    }

    @Override
    public int fillCount() {
        return fillCount;
    }

    @Override
    public void enqueue(T x) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        buffer[last] = x;
        last = (last + 1) % capacity; // 循环队尾
        fillCount++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        T item = buffer[first];
        buffer[first] = null; // 清空引用
        first = (first + 1) % capacity; // 循环队首
        fillCount--;
        return item;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return buffer[first];
    }
}

示例使用

下面是如何使用 ArrayRingBuffer 类的示例代码：

public class Main {
    public static void main(String[] args) {
        BoundedQueue<Double> queue = new ArrayRingBuffer<>(4);
        
        System.out.println(queue.isEmpty());       // 返回 true
        queue.enqueue(9.3);
        queue.enqueue(15.1);
        queue.enqueue(31.2);
        
        System.out.println(queue.isFull());        // 返回 false
        queue.enqueue(-3.1);
        System.out.println(queue.isFull());        // 返回 true
        
        System.out.println(queue.dequeue());       // 返回 9.3
        System.out.println(queue.peek());          // 返回 15.1
    }
}

代码解释

1. BoundedQueue 接口：定义了队列的基本操作和状态检查方法。
2. ArrayRingBuffer 类：
   • 使用数组存储元素，并通过循环索引实现环形结构。
   • enqueue 方法负责添加元素，并更新队尾索引。
   • dequeue 方法返回队首元素，并更新队首索引。
   • peek 方法返回队首元素而不删除它。
   • 提供了对队列是否为空和是否已满的检查方法。

异常处理

在 enqueue 和 dequeue 方法中，如果操作不合法（如在满队列上添加元素，或在空队列上移除元素），将抛出 IllegalStateException。

任务 2: AbstractBoundedQueue

抽象类的定义

抽象类允许你提供方法的部分实现。实现接口的类必须实现所有抽象方法，若未实现，类需声明为抽象。

实现要求

创建 AbstractBoundedQueue.java，包含以下方法和字段：

public abstract class AbstractBoundedQueue<T> implements BoundedQueue<T> {
    protected int fillCount;
    protected int capacity;

    public int capacity() {
        return capacity;
    }

    public int fillCount() {
        return fillCount;
    }

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

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

    public abstract T peek();
    public abstract T dequeue();
    public abstract void enqueue(T x);
}

---

任务 3: ArrayRingBuffer

ArrayRingBuffer 类的定义

ArrayRingBuffer 继承自 AbstractBoundedQueue，使用数组作为存储结构。

实现要求

创建 ArrayRingBuffer.java，包含类型为 T 的数组、填充计数、起始索引等字段：

public class ArrayRingBuffer<T> extends AbstractBoundedQueue<T> {
    private T[] buffer;    // 循环缓冲区
    private int first;      // 指向队首的索引
    private int last;       // 指向队尾的索引

    @SuppressWarnings("unchecked")
    public ArrayRingBuffer(int capacity) {
        this.buffer = (T[]) new Object[capacity];
        this.capacity = capacity;
        this.fillCount = 0;
        this.first = 0;
        this.last = 0;
    }

    @Override
    public void enqueue(T x) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        buffer[last] = x;
        last = (last + 1) % capacity; // 循环队尾
        fillCount++;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        T item = buffer[first];
        buffer[first] = null; // 清空引用
        first = (first + 1) % capacity; // 循环队首
        fillCount--;
        return item;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return buffer[first];
    }
}

---

任务 4: GuitarString

GuitarString 类的目标

使用 ArrayRingBuffer 实现 Karplus-Strong 算法合成吉他弦声音。

实现要求

创建 GuitarString.java，实现 Karplus-Strong 算法，包含以下方法：

public class GuitarString {
    private ArrayRingBuffer<Double> buffer;

    public GuitarString(double frequency) {
        int capacity = (int) Math.round(StdAudio.SAMPLE_RATE / frequency);
        buffer = new ArrayRingBuffer<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buffer.enqueue(0.0); // 初始化缓冲区为 0
        }
    }

    public void pluck() {
        while (!buffer.isEmpty()) {
            buffer.dequeue(); // 清空缓冲区
        }
        // 填充随机音符
        while (!buffer.isFull()) {
            buffer.enqueue(Math.random() - 0.5); // 随机值范围 [-0.5, 0.5]
        }
    }

    public void tic() {
        double first = buffer.dequeue();
        double second = buffer.peek(); // 获取队首但不删除
        double newSample = 0.996 * 0.5 * (first + second); // Karplus-Strong 算法
        buffer.enqueue(newSample); // 添加新的音符
    }

    public double sample() {
        return buffer.peek();
    }
}

---

提交作业

在 GitHub 中查看作业并创建 Pull Request，清晰描述实现过程，确保包括代码和任何相关文档。