随机队列的实现-随机性的思想

Question

我正在Coursera学习算法课程。以下是其中一项任务：

随机化队列。随机队列类似于堆栈或队列， 除了删除的项目是在项目中随机随机选择的 在数据结构中。

我正在尝试找到一种在恒定时间内实现出队（随机删除项目）的方法。我想到了一种方法，需要双端队列（这支持在固定时间内从正面和背面移除和添加项目）。我的想法如下：

• 将双端队列用作随机队列中的基础数据结构
• 入队-使用库函数生成介于0和1之间（含0和1）的整数。如果整数为0，则将该项添加到双端队列的前面。否则，将其添加到背面。
• 出队-任何方向都可以。

之所以会在入队中而不是在出队中发生随机性，是因为我发现它不是完全随机的（例如，n对入队的调用将使出队仅返回第一个或第n个项目）。因此，为确保将物品随机移除，我决定将它们随机入队。

这个想法对我来说似乎很好，因为我无法在其中发现漏洞，但问题是我无法证明我的想法确实可行。我对随机性了解不多。实际上，这只是我第五次使用随机数据结构。

我的想法正确吗？它会生成一个数据结构来随机删除项目吗？

Answer 1

由于统一性要求，我认为您建议的方法不会起作用。均匀性意味着队列中的每个项目都有相同的出队可能性。您的建议始终将元素添加到一端，而从一端或另一端出队。因此，在任何给定的出队请求中，非结束元素被选择的可能性为零。

一种替代方法是使用基于数组的堆栈。在堆栈的末尾添加元素，但是要使队列出队，请随机选择一个元素，将其与最后一个元素交换，然后将其弹出。这将具有统一的选择，并且所有组件操作都是恒定时间。

Answer 2

仅在末端入队不会产生一致的随机序列。将要入队的最后一个项目必定在两端，而将其他项目入队后，要入队的第一个项目更可能位于中间的某个地方，而不是在两端。

为了说明，取三个项目{1, 2, 3}的集合，这是不会导致均匀分布的最小集合。按此顺序将它们排入队列将得到以下可能的结果（括号中为将下一个项目排入队列的位置。）>

[1] -> (front) -> [1, 2] -> (front) -> [1, 2, 3]
[1] -> (front) -> [1, 2] -> (back) -> [3, 1, 2]
[1] -> (back) -> [2, 1] -> (front) -> [2, 1, 3]
[1] -> (back) -> [2, 1] -> (back) -> [3, 2, 1]
这四个结果是唯一的可能性，并且都具有同等的可能性。如您所见，最后一项永远不会在中间，而第一项和第二项都两次在中间。

您想要在随机位置出队。但是您无需保留其他项目的顺序，因为它们是均匀分布的。这意味着您可以将最后一个项目与一个随机项目交换，然后使该项目出队（成为最后一个项目）。