CS61B 课程笔记（Disc 06 Selecting ADTs）

1. 不可变对象 (Immutable Objects)

访问控制

访问控制允许我们限制字段、方法和类的使用：

  • public：任何人都可以访问。
  • protected：类自身、包内和任何子类可访问。
  • default（无修饰符）：类自身和包内可访问。
  • private：仅类自身可访问。

1.1 不可变类

一个类是不可变的，如果其实例在构造后不能改变。判断以下类是否不可变：

  1. Pebble 类：

    1
    2
    3
    4
    public class Pebble {
        public int weight;
        public Pebble() { weight = 1; }
    }
    • 结论：这是一个可变类。Pebble的weight字段是公共的，因此状态可以轻易改变。

  2. Rock 类：

    1
    2
    3
    4
    public class Rock {
        public final int weight;
        public Rock(int w) { weight = w; }
    }
    • 结论：这是一个不可变类。Rock的weight字段是final，因此一旦初始化后不能被重新赋值。

  3. Rocks 类：

    1
    2
    3
    4
    public class Rocks {
        public final Rock[] rocks;
        public Rocks(Rock[] rox) { rocks = rox; }
    }
    • 结论：尽管rocks不能被重新赋值，但数组中的内容可以被改变，因此Rocks是可变的。

  4. SecretRocks 类：

    1
    2
    3
    4
    public class SecretRocks {
        private Rock[] rocks;
        public SecretRocks(Rock[] rox) { rocks = rox; }
    }
    • 结论：rocks变量是私有的，外部不能重新赋值或修改其元素。然而，rox在传入时可以被外部编辑，因此SecretRocks在技术上是可变的。可以通过使用Arrays.copyOf使其不可变。

2. 选择抽象数据类型 (Selecting ADTs)

2.1 PunkRock 类

1
2
3
4
5
6
7
public class PunkRock {
    private final Rock[] band;
    public PunkRock(Rock yRoad) { band = {yRoad}; }
    public Rock[] myBand() {
        return band;
    }
}
  • 结论：通过public myBand()方法可以访问和修改PunkRock的私有数组内容，因此这个类是可变的。

2.2 MommaRock 类

1
2
3
public class MommaRock {
    public static final Pebble baby = new Pebble();
}
  • 结论：这是一个可变类，因为Pebble有公共变量可以被改变。例如，mr.baby.weight = 5。

3. 打破系统 (Breaking the System)

3.1 不良整数栈 (BadIntegerStack)

下面是一个不良实现的栈 ADT：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class BadIntegerStack {
    public class Node {
        public Integer value;
        public Node prev;
        public Node(Integer v, Node p) {
            value = v;
            prev = p;
        }
    }
    public Node top;

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

    public void push(Integer num) {
        top = new Node(num, top);
    }

    public Integer pop() {
        Integer ans = top.value;
        top = top.prev;
        return ans;
    }

    public Integer peek() {
        return top.value;
    }
}

(a) 利用缺陷

填写以下main方法以打印“Success”并导致BadIntegerStack产生NullPointerException：

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    try {
        BadIntegerStack stack = new BadIntegerStack();
        stack.pop();
    } catch (NullPointerException e) {
        System.out.println("Success!");
    }
}

(b) 利用另一个缺陷

完成以下main方法，使栈看起来无限高：

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
    BadIntegerStack stack = new BadIntegerStack();
    stack.push(1);
    stack.top.prev = stack.top; // 创建循环引用
    while (!stack.isEmpty()) {
        stack.pop();
    }
    System.out.println("This print statement is unreachable!");
}

(c) 改进建议

为了防止BadIntegerStack抛出NullPointerException或产生无限栈，可以将top设为私有(private)。

4. 设计停车场 (Design a Parking Lot)

设计一个停车场包，智能地分配停车位给汽车。确定所需的类并设计每个类的 API。

停车场需求：

  • 停车位可以是普通、紧凑或残疾专用。
  • 新车到达时，系统应根据汽车类型分配特定空间。
  • 所有汽车均可停放在普通停车位，因此紧凑型车可停放在紧凑型和普通停车位。
  • 当汽车离开时，系统应记录该停车位为空闲状态。
  • 包应设计成允许不同停车场有不同数量的三种类型停车位。
  • 停车位应考虑与入口的距离，尽量将汽车停放在离入口最近的位置。

类设计：

  1. Car 类：

    • public Car(boolean isCompact, boolean isHandicapped)：创建具有给定大小和权限的汽车。
    • public boolean isCompact()：返回汽车是否可以适应紧凑停车位。
    • public boolean isHandicapped()：返回汽车是否可以停在残疾专用停车位。
    • public boolean findSpotAndPark(ParkingLot lot)：尝试在停车场停放此汽车，成功返回true。
    • public void leaveSpot()：腾出此汽车的停车位。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    public class Car {
        private boolean isCompact; // 是否为紧凑型车
        private boolean isHandicapped; // 是否为残疾专用车
        private Spot currentSpot; // 当前占用的停车位

        // 构造函数：创建具有给定大小和权限的汽车
        public Car(boolean isCompact, boolean isHandicapped) {
            this.isCompact = isCompact;
            this.isHandicapped = isHandicapped;
        }

        // 返回汽车是否为紧凑型车
        public boolean isCompact() {
            return isCompact;
        }

        // 返回汽车是否为残疾专用车
        public boolean isHandicapped() {
            return isHandicapped;
        }

        // 尝试在停车场停放此汽车，成功返回true
        public boolean findSpotAndPark(ParkingLot lot) {
            return lot.findSpotAndPark(this);
        }

        // 腾出此汽车的停车位
        public void leaveSpot() {
            if (currentSpot != null) {
                currentSpot.vacate(); // 腾出停车位
                currentSpot = null; // 重置当前停车位
            }
        }

        // 设置当前占用的停车位
        void setCurrentSpot(Spot spot) {
            this.currentSpot = spot;
        }
    }

  2. Spot 类（私有）：

    • private Spot(String type, int proximity)：创建特定类型和接近度的停车位。
    • private boolean isHandicapped()：返回此停车位是否为残疾司机保留。
    • private boolean isCompact()：返回此停车位是否仅能容纳紧凑型车。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    private class Spot {
        private String type; // 停车位类型: "handicapped", "compact", "regular"
        private int proximity; // 停车位距离入口的距离
        private boolean isOccupied; // 停车位是否被占用

        // 构造函数：创建特定类型和接近度的停车位
        private Spot(String type, int proximity) {
            this.type = type;
            this.proximity = proximity;
            this.isOccupied = false; // 初始化为空闲状态
        }

        // 返回此停车位是否为残疾司机保留
        private boolean isHandicapped() {
            return "handicapped".equals(type);
        }

        // 返回此停车位是否仅能容纳紧凑型车
        private boolean isCompact() {
            return "compact".equals(type);
        }

        // 返回停车位是否被占用
        public boolean isOccupied() {
            return isOccupied;
        }

        // 停放车辆
        public void park() {
            isOccupied = true; // 标记为已占用
        }

        // 腾出停车位
        public void vacate() {
            isOccupied = false; // 标记为可用
        }

        // 获取停车位的接近度
        public int getProximity() {
            return proximity;
        }
    }

  3. ParkingLot 类：

    • public ParkingLot(int[] handicappedDistances, int[] compactDistances, int[] regularDistances)：创建停车场，包含指定数量的残疾停车位、紧凑停车位和普通停车位。
    • public boolean findSpotAndPark(Car toPark)：尝试为给定汽车找到停车位并停放。若无可用停车位则返回false。
    • public void removeCarFromSpot(Car toRemove)：记录停车位被腾出，并使停车位再次可用。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    import java.util.*;

    public class ParkingLot {
        private PriorityQueue<Spot> handicappedSpots; // 残疾停车位的优先队列
        private PriorityQueue<Spot> compactSpots; // 紧凑停车位的优先队列
        private PriorityQueue<Spot> regularSpots; // 普通停车位的优先队列
        private Map<Car, Spot> occupiedSpots; // 记录每辆车和其占用的停车位

        // 构造函数：创建停车场，包含指定数量的三种类型停车位
        public ParkingLot(int[] handicappedDistances, int[] compactDistances, int[] regularDistances) {
            // 初始化优先队列，根据停车位的接近度进行排序
            handicappedSpots = new PriorityQueue<>(Comparator.comparingInt(Spot::getProximity));
            compactSpots = new PriorityQueue<>(Comparator.comparingInt(Spot::getProximity));
            regularSpots = new PriorityQueue<>(Comparator.comparingInt(Spot::getProximity));
            occupiedSpots = new HashMap<>(); // 初始化已占用停车位的记录

            // 将残疾停车位添加到优先队列
            for (int distance : handicappedDistances) {
                handicappedSpots.offer(new Spot("handicapped", distance));
            }
            // 将紧凑停车位添加到优先队列
            for (int distance : compactDistances) {
                compactSpots.offer(new Spot("compact", distance));
            }
            // 将普通停车位添加到优先队列
            for (int distance : regularDistances) {
                regularSpots.offer(new Spot("regular", distance));
            }
        }

        // 尝试为给定汽车找到停车位并停放
        public boolean findSpotAndPark(Car toPark) {
            Spot spot = null; // 初始化停车位

            // 根据汽车类型寻找合适的停车位
            if (toPark.isHandicapped() && !handicappedSpots.isEmpty()) {
                spot = handicappedSpots.poll(); // 从残疾停车位队列中取出一个停车位
            } else if (toPark.isCompact() && !compactSpots.isEmpty()) {
                spot = compactSpots.poll(); // 从紧凑停车位队列中取出一个停车位
            } else if (!regularSpots.isEmpty()) {
                spot = regularSpots.poll(); // 从普通停车位队列中取出一个停车位
            }

            // 如果找到停车位，则进行停放
            if (spot != null) {
                spot.park(); // 停放车辆
                occupiedSpots.put(toPark, spot); // 记录车辆和其占用的停车位
                toPark.setCurrentSpot(spot); // 设置当前停车位
                return true; // 停放成功
            }
            return false; // 没有可用停车位
        }

        // 记录停车位被腾出，并使停车位再次可用
        public void removeCarFromSpot(Car toRemove) {
            Spot spot = occupiedSpots.remove(toRemove); // 移除记录并获取停车位
            if (spot != null) {
                spot.vacate(); // 腾出停车位
                // 将空闲的停车位重新加入相应的优先队列
                switch (spot.type) {
                    case "handicapped":
                        handicappedSpots.offer(spot); // 重新加入残疾停车位队列
                        break;
                    case "compact":
                        compactSpots.offer(spot); // 重新加入紧凑停车位队列
                        break;
                    case "regular":
                        regularSpots.offer(spot); // 重新加入普通停车位队列
                        break;
                }
            }
            toRemove.leaveSpot(); // 腾出汽车的停车位
        }
    }

数据结构选择：

优先队列：使用优先队列来管理停车位，以便根据距离入口的接近度进行停车位的选择。

Map<Car, Spot>：通过Map跟踪每辆车和它所占用的停车位，以便在车辆离开时能够快速找到并释放停车位。