Java 数据结构（特定程序的最有效结构）

Question

课本练习题：一个医院可以容纳n个病人。每次病人进来时，都会对他进行评估，如果情况非危急，则必须等待轮到他。如果情况危急，他将被转移为下一个接受治疗的人。如果患者在被呼叫时在洗手间，他会跳过轮到他并被视为新患者。在任何时候，医院都需要知道谁在接受治疗，以及剩余的容量。解决这个问题是否更有效（能够选择多个答案）： 1. deque 2. 数组 3. 循环数组 4. 自定义数据结构：数组 + 堆栈 5. 堆栈

Answer 1

1. Deque：这将是一个不错的选择，因为您可以在 O(1) 时间内从行的前端/末尾添加/删除，并且可以使用整数变量跟踪患者的数量，因此获取大小行的将是 O(1)。您还可以通过在添加患者之前检查线路的大小来确保最大容量为 N。

2. 数组：由于您需要添加到行首，普通数组不是一个好的选择，因为您必须将所有元素移动 1 个位置以在数组的开头腾出空间。这会给你 O(n) 来添加到行的前面。

3. 圆形阵列：这将是最好的选择，比双端队列更好的一个小原因......因为它有一个底层数组，所有的内存位置（排队病人的点）都是连续的，而有一个出队，这是使用底层链表实现，内存位置是随机且不连续的。这提供了一个小好处。您可以创建一个大小为 N（医院的容量）的数组，并一遍又一遍地使用相同的内存位置。如果医院没有容量（无限数量的患者可以排队），则您将需要使用出队（因为数组具有固定长度）。从前/后添加/删除是 O(1) 就像双端队列一样，并且获取行的大小也是 O(1) 因为您可以使用行的开始/结束索引来计算它。

4. 数组 + 堆栈：与仅使用数组（#2）相比，这没有任何好处，因为堆栈是无用的（参见 #5）。

5. 堆栈：由于您需要添加到行的开头和结尾，因此堆栈不起作用（它只能添加到一侧）。

所以按照从最好到最坏的顺序：3、1、2、4、5。

除了#5 之外，所有都可以使用。