CS61B 课程笔记（Project 1A Data Structures）

双端队列（Deque）:
- 定义：双端队列是一种允许在两端进行插入和删除操作的数据结构。
- 操作：
  - addFirst(T item)：在前端添加元素。
  - addLast(T item)：在后端添加元素。
  - removeFirst()：从前端移除并返回元素。
  - removeLast()：从后端移除并返回元素。
  - get(int index)：获取指定索引的元素。
链表实现:
- 使用节点（Node）来存储数据和指向前后节点的引用。
- 操作必须在常数时间内完成，避免循环或递归的复杂性。
- 设计中考虑使用哨兵节点以简化边界条件的处理。
数组实现:
- 通过动态数组来实现双端队列。
- 需实现数组的循环使用（将前指针和后指针设定为环形）。
- 调整数组大小时，需正确处理数据迁移和指针位置。
泛型编程:
- 实现一个支持泛型的双端队列，使其可以存储任意类型的数据。
测试与验证:
- 编写单元测试以确保实现的正确性。
- 使用 JUnit 进行结构化测试，确保每个操作都能按预期工作。

解决方案

1. 链表双端队列实现（LinkedListDeque.java）

public class LinkedListDeque<T> {
    private class Node {
        T item;
        Node prev;
        Node next;
        
        Node(T item) {
            this.item = item;
        }
    }
    
    private Node front;
    private Node back;
    private int size;

    // 创建空的双端队列
    public LinkedListDeque() {
        front = null;
        back = null;
        size = 0;
    }

    // 在前端添加元素
    public void addFirst(T item) {
        Node newNode = new Node(item);
        if (size == 0) {
            front = back = newNode;
        } else {
            newNode.next = front;
            front.prev = newNode;
            front = newNode;
        }
        size++;
    }

    // 在后端添加元素
    public void addLast(T item) {
        Node newNode = new Node(item);
        if (size == 0) {
            front = back = newNode;
        } else {
            newNode.prev = back;
            back.next = newNode;
            back = newNode;
        }
        size++;
    }

    // 移除并返回前端元素
    public T removeFirst() {
        if (size == 0) return null;
        T item = front.item;
        front = front.next;
        if (front != null) front.prev = null;
        size--;
        return item;
    }

    // 移除并返回后端元素
    public T removeLast() {
        if (size == 0) return null;
        T item = back.item;
        back = back.prev;
        if (back != null) back.next = null;
        size--;
        return item;
    }

    // 获取指定索引的元素
    public T get(int index) {
        if (index < 0 || index >= size) return null;
        Node current = front;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.item;
    }

    // 获取指定索引的元素（递归）
    public T getRecursive(int index) {
        return getRecursiveHelper(front, index);
    }

    private T getRecursiveHelper(Node node, int index) {
        if (node == null || index < 0) return null;
        if (index == 0) return node.item;
        return getRecursiveHelper(node.next, index - 1);
    }

    // 检查是否为空
    public boolean isEmpty() {
        return size == 0;
    }

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

    // 打印队列元素
    public void printDeque() {
        Node current = front;
        while (current != null) {
            System.out.print(current.item + " ");
            current = current.next;
        }
        System.out.println();
    }
}

1. 构造函数 `LinkedListDeque()`

public LinkedListDeque() {
    front = null; // 🚪 队列前端为空
    back = null;  // 🚪 队列后端为空
    size = 0;     // 📏 队列大小为0
}

原理：初始化一个空的双端队列，前后端指针都设为 null，大小设为0。

2. `addFirst(T item)`

public void addFirst(T item) {
    Node newNode = new Node(item); // 🎉 创建新节点
    if (size == 0) {
        front = back = newNode; // 🌟 队列为空时，前后端都指向新节点
    } else {
        newNode.next = front; // 📈 新节点的下一个指向当前前端
        front.prev = newNode; // 🔄 当前前端的前一个指向新节点
        front = newNode;      // 🚀 更新前端为新节点
    }
    size++; // 📊 增加队列大小
}

原理：在前端添加新元素。如果队列为空，新节点成为前后端；否则，将新节点插入前端，并更新指针。

3. `addLast(T item)`

public void addLast(T item) {
    Node newNode = new Node(item); // 🎊 创建新节点
    if (size == 0) {
        front = back = newNode; // 🌈 队列为空时，前后端都指向新节点
    } else {
        newNode.prev = back; // 📬 新节点的前一个指向当前后端
        back.next = newNode; // 📥 当前后端的下一个指向新节点
        back = newNode;      // 🏁 更新后端为新节点
    }
    size++; // 📈 增加队列大小
}

原理：在后端添加新元素。逻辑与 addFirst 类似，只不过是向后端插入。

4. `removeFirst()`

public T removeFirst() {
    if (size == 0) return null; // 🚫 如果队列为空，返回null
    T item = front.item; // 💼 保存前端元素
    front = front.next; // ⏭️ 更新前端指向下一个节点
    if (front != null) front.prev = null; // 🔄 更新后的前端前一个指向null
    size--; // 📉 减少队列大小
    return item; // 🎁 返回移除的元素
}

原理：移除并返回前端元素。如果队列为空，返回 null。否则，更新前端指针并返回移除的元素。

5. `removeLast()`

public T removeLast() {
    if (size == 0) return null; // 🚫 如果队列为空，返回null
    T item = back.item; // 💼 保存后端元素
    back = back.prev; // ⏮️ 更新后端指向前一个节点
    if (back != null) back.next = null; // 🔄 更新后的后端后一个指向null
    size--; // 📉 减少队列大小
    return item; // 🎁 返回移除的元素
}

原理：移除并返回后端元素。逻辑与 removeFirst 类似，只不过是向后端移除。

6. `get(int index)`

public T get(int index) {
    if (index < 0 || index >= size) return null; // 🚫 索引不合法，返回null
    Node current = front; // 🔍 从前端开始查找
    for (int i = 0; i < index; i++) {
        current = current.next; // ⏭️ 遍历到指定位置
    }
    return current.item; // 🎯 返回找到的元素
}

原理：获取指定索引的元素。通过从前端开始遍历节点，直到到达指定索引。

7. `getRecursive(int index)`

1
2
3

public T getRecursive(int index) {
    return getRecursiveHelper(front, index); // 🌱 从前端开始递归查找
}

原理：使用递归获取指定索引的元素，通过调用辅助方法。

8. `getRecursiveHelper(Node node, int index)`

private T getRecursiveHelper(Node node, int index) {
    if (node == null || index < 0) return null; // 🚫 递归边界，返回null
    if (index == 0) return node.item; // 🎯 找到元素，返回
    return getRecursiveHelper(node.next, index - 1); // 🌿 继续递归
}

原理：递归遍历节点。如果找到目标索引则返回相应元素，否则继续向下递归。

9. `isEmpty()`

1
2
3

public boolean isEmpty() {
    return size == 0; // 🌌 判断队列是否为空
}

原理：判断队列的大小是否为0，返回 true 或 false。

10. `size()`

1
2
3

public int size() {
    return size; // 📈 返回队列当前的大小
}

原理：返回当前队列的大小。

11. `printDeque()`

public void printDeque() {
    Node current = front; // 🔍 从前端开始打印
    while (current != null) {
        System.out.print(current.item + " "); // 🖨️ 打印元素
        current = current.next; // ⏭️ 遍历到下一个节点
    }
    System.out.println(); // 📝 换行
}

原理：遍历队列并打印所有元素，直到遇到 null。

2. 数组双端队列实现（ArrayDeque.java）

public class ArrayDeque<T> {
    private T[] items;
    private int size;
    private int front;
    private int back;

    // 创建空的数组双端队列
    public ArrayDeque() {
        items = (T[]) new Object[8];
        size = 0;
        front = 0;
        back = 0;
    }

    // 在前端添加元素
    public void addFirst(T item) {
        if (size == items.length) resize(items.length * 2);
        front = (front - 1 + items.length) % items.length;
        items[front] = item;
        size++;
    }

    // 在后端添加元素
    public void addLast(T item) {
        if (size == items.length) resize(items.length * 2);
        items[back] = item;
        back = (back + 1) % items.length;
        size++;
    }

    // 移除并返回前端元素
    public T removeFirst() {
        if (size == 0) return null;
        T item = items[front];
        front = (front + 1) % items.length;
        size--;
        if (size > 0 && size == items.length / 4) resize(items.length / 2);
        return item;
    }

    // 移除并返回后端元素
    public T removeLast() {
        if (size == 0) return null;
        back = (back - 1 + items.length) % items.length;
        T item = items[back];
        size--;
        if (size > 0 && size == items.length / 4) resize(items.length / 2);
        return item;
    }

    // 获取指定索引的元素
    public T get(int index) {
        if (index < 0 || index >= size) return null;
        return items[(front + index) % items.length];
    }

    // 检查是否为空
    public boolean isEmpty() {
        return size == 0;
    }

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

    // 打印队列元素
    public void printDeque() {
        for (int i = 0; i < size; i++) {
            System.out.print(get(i) + " ");
        }
        System.out.println();
    }

    // 调整数组大小
    private void resize(int capacity) {
        T[] newArray = (T[]) new Object[capacity];
        for (int i = 0; i < size; i++) {
            newArray[i] = get(i);
        }
        items = newArray;
        front = 0;
        back = size;
    }
}

1. 构造函数 `ArrayDeque()`

public ArrayDeque() {
    items = (T[]) new Object[8]; // 🎉 创建一个大小为8的数组
    size = 0;                     // 📏 队列大小初始化为0
    front = 0;                    // 🚪 前端索引初始化为0
    back = 0;                     // 🚪 后端索引初始化为0
}

原理：初始化一个空的数组双端队列，创建一个长度为8的数组，前后端指针都指向0。

2. `addFirst(T item)`

public void addFirst(T item) {
    if (size == items.length) resize(items.length * 2); // 🔄 如果数组满了，则扩容
    front = (front - 1 + items.length) % items.length; // ⏭️ 更新前端索引
    items[front] = item; // 🎈 将新元素放入前端
    size++; // 📈 增加队列大小
}

原理：在前端添加新元素。如果数组已满，则将数组大小翻倍。更新前端索引并将新元素放入。

3. `addLast(T item)`

public void addLast(T item) {
    if (size == items.length) resize(items.length * 2); // 🔄 如果数组满了，则扩容
    items[back] = item; // 🎊 将新元素放入后端
    back = (back + 1) % items.length; // ⏭️ 更新后端索引
    size++; // 📈 增加队列大小
}

原理：在后端添加新元素。逻辑与 addFirst 类似，只不过是向后端插入。

4. `removeFirst()`

public T removeFirst() {
    if (size == 0) return null; // 🚫 如果队列为空，返回null
    T item = items[front]; // 💼 保存前端元素
    front = (front + 1) % items.length; // ⏭️ 更新前端索引
    size--; // 📉 减少队列大小
    if (size > 0 && size == items.length / 4) resize(items.length / 2); // 🔄 缩容
    return item; // 🎁 返回移除的元素
}

原理：移除并返回前端元素。如果队列为空，返回 null。更新前端指针，减少大小，并在必要时缩小数组。

5. `removeLast()`

public T removeLast() {
    if (size == 0) return null; // 🚫 如果队列为空，返回null
    back = (back - 1 + items.length) % items.length; // ⏮️ 更新后端索引
    T item = items[back]; // 💼 保存后端元素
    size--; // 📉 减少队列大小
    if (size > 0 && size == items.length / 4) resize(items.length / 2); // 🔄 缩容
    return item; // 🎁 返回移除的元素
}

原理：移除并返回后端元素。逻辑与 removeFirst 类似，只不过是向后端移除。

6. `get(int index)`

public T get(int index) {
    if (index < 0 || index >= size) return null; // 🚫 索引不合法，返回null
    return items[(front + index) % items.length]; // 🎯 根据前端索引计算元素位置
}

原理：获取指定索引的元素。根据前端索引计算实际位置并返回相应元素。

7. `isEmpty()`

1
2
3

public boolean isEmpty() {
    return size == 0; // 🌌 判断队列是否为空
}

原理：判断队列的大小是否为0，返回 true 或 false。

8. `size()`

1
2
3

public int size() {
    return size; // 📈 返回队列当前的大小
}

原理：返回当前队列的大小。

9. `printDeque()`

public void printDeque() {
    for (int i = 0; i < size; i++) {
        System.out.print(get(i) + " "); // 🖨️ 打印每个元素
    }
    System.out.println(); // 📝 换行
}

原理：遍历队列并打印所有元素，直到遍历到大小。

10. `resize(int capacity)`

private void resize(int capacity) {
    T[] newArray = (T[]) new Object[capacity]; // 🎈 创建新数组
    for (int i = 0; i < size; i++) {
        newArray[i] = get(i); // 🔄 复制旧数组中的元素
    }
    items = newArray; // 🌱 更新数组
    front = 0; // 🚪 重置前端索引
    back = size; // 🚪 更新后端索引
}

原理：调整数组大小，创建一个新数组并复制元素。如果扩容或缩容，则更新前后端指针。

CS61B 课程笔记（Project 1A Data Structures）

解决方案

1. 链表双端队列实现（LinkedListDeque.java）

1. 构造函数 LinkedListDeque()

2. addFirst(T item)

3. addLast(T item)

4. removeFirst()

5. removeLast()

6. get(int index)

7. getRecursive(int index)

8. getRecursiveHelper(Node node, int index)

9. isEmpty()

10. size()

11. printDeque()

2. 数组双端队列实现（ArrayDeque.java）

1. 构造函数 ArrayDeque()

2. addFirst(T item)

3. addLast(T item)

4. removeFirst()

5. removeLast()

6. get(int index)

7. isEmpty()

8. size()

9. printDeque()

10. resize(int capacity)

1. 构造函数 `LinkedListDeque()`

2. `addFirst(T item)`

3. `addLast(T item)`

4. `removeFirst()`

5. `removeLast()`

6. `get(int index)`

7. `getRecursive(int index)`

8. `getRecursiveHelper(Node node, int index)`

9. `isEmpty()`

10. `size()`

11. `printDeque()`

1. 构造函数 `ArrayDeque()`

2. `addFirst(T item)`

3. `addLast(T item)`

4. `removeFirst()`

5. `removeLast()`

6. `get(int index)`

7. `isEmpty()`

8. `size()`

9. `printDeque()`

10. `resize(int capacity)`