查找队列中的最小值，并将其从队列中删除

Question

几周后我有期末考试，我们的练习题是这样的：

给定一个N个整数的队列，在队列中找到最小值并将其从队列中删除。当您完成时，其余的值必须按照它们原来的顺序。您只能使用队列操作，也就是说，您无权访问数组或链表中的基础存储。描述实现此操作的最省时的方法，并给出以N表示的顺序（大O）。

编辑：队列操作是“enqueue”、“dequeue”、“isfull”、“isempty”，如果是循环队列，则是“front”和“back”。

Answer 1

如果您有一个队列，并且只允许在其上执行入列和出列操作，那么在队列中查找任意值的唯一方法是执行查找特定值所需的许多出列操作。如果您不知道该值在队列中的位置，那么在最坏的情况下，您可能必须检查队列中的所有n个元素，这需要花费θ(n)个时间。所以从这个意义上说，在最坏的情况下，我们想出的任何解决方案都必须至少做θ(n)功。

这样做的一种方法是，假设队列是一个元素环，在某个位置有一个光标指示前面。如果您出列一个元素，然后立即重新排队，就好像您将光标顺时针（或逆时针--这毕竟只是一个比喻）移动了一个点。因此，可以考虑通过在队列中移动光标来解决这个问题，直到找到要删除的元素，然后在不重新排队的情况下将其出列，然后将光标移动到开始的位置。这里有一种方法：

/* Store the number of elements in the queue, since it will change as
 * the loop runs. We want to visit each element exactly once.
 */
int numElems = queue.size();
for (int i = 0; i < numElems; i++) {
    ValueType elem = queue.dequeueMin();

    /* Remove the element if it matches the thing to get rid of, or,
     * equivalently, preserve the element if it isn't.
     */
    if (elem != theThingToRemove) {
        queue.enqueue(elem);
    }
}

这个算法总是做θ(n)个工作--循环对每个元素访问一次，并对每个元素做O(1)个总工作和O(1)个队列操作。

有趣的事实：队列的这个比喻正是循环缓冲区背后的思想，循环缓冲区通常用于实现固定大小的队列。