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

Question

课本练习题：

一家医院可容纳 n 名患者。每次病人进来时，他都会接受评估，如果情况非危急，则必须等待轮到他。如果情况危急，他会被转移到下一个接受治疗的地方。如果病人在被叫到时在洗手间里，他会跳过他的轮次并被视为新病人。在任何时候，医院都需要知道谁在接受治疗，以及剩余的容量。

用（能够选择多个答案）解决这个问题会更有效吗： 1. deque 2. array 3. circuluar array 4. 自定义数据结构：array + stack 5. stack

标签： javaarraysstackqueuedeque

Answer 1

1. 双端队列：这将是一个不错的选择，因为您可以在 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。