data-structures - 带 FIFO 检索的集合

Question

GRE CS：哪种数据结构最适合实现具有以下三个特征的值集合？

• 从集合中检索和删除项目FIFO
• 集合中的项目数量没有先验限制。
• 相对于内存地址所需的存储空间而言，项目的大小很大。

这是一道选择题，答案如下：

• (A) 带头尾指针的单链表
• (B) 双向链表，只有一个头指针
• (C) 阵列
• (D) 二叉树
• (E) 哈希表

我认为（C）、（D）和（E）是错误的。

Answer 1

A似乎是正确的答案。因为项目是在 FIFO 中删除的，所以您只需要对集合中的第一个和最后一个元素进行操作。A、C 和 E 都允许在恒定时间内这样做。

项目数量没有限制。这意味着 C 和 E 不再像 A 一样好，因为您最终将需要重新调整数组或哈希表的大小，因为它变大或分配的内容远远超过您开始时的需要。使用链接列表，您可以随时轻松添加。

物品的尺寸很大。这只是进一步表明 A 是正确的，因为在存储结构中添加链接地址并不重要。