data-structures - 可以仅使用哈希表来实现队列吗？

Question

我的意思是，实现只能独立分配少量（O（1）/O（log n））内存 - 队列的大部分数据必须在哈希表内。

编辑：这个数据结构应该支持 (Push,Pop,Top,Len) 操作，但在幕后，它不是链表/数组，而是使用哈希表。所需的大部分 O(n) 内存将包含在哈希表中。

标签： data-structuresqueuehashtable

Answer 1

任何类似列表的数据结构都可以用哈希表表示，其中列表中的每个元素都映射到它的位置。所以这个列表：[a, b, c, d]可以用这样的哈希表表示：

0: a
1: b
2: c
3: d

队列是一种先进先出的数据结构：先进先出。所以元素的弹出顺序与它们被推送的顺序相同。它可以用类似列表的数据结构来建模，我们通过将新元素添加到尾部来将它们推送到列表中，并通过从头部取出元素来弹出元素。

该实现只能独立分配少量 (O(1)/O(log n)) 内存

独立于哈希表本身处理的唯一必要数据是head和tail索引。

因此，使用该[a, b, c, d]示例，我们的头部指向索引0（对应于a），尾部指向索引3（对应于d）。

要将一个新元素推入队列（例如e），我们将其插入到带有 key 的哈希表中tail + 1，即4，并将我们的值加tail1。

要弹出一个元素，我们获取该head位置的元素，将其从哈希表中删除并递增head1。

在此之后，我们的哈希表最终是这样的：

1: b
2: c
3: d
4: e

有了这个实现，实现top起来len就很简单了。

这个基本思想可以扩展到处理更复杂的哈希表。