查找在隊列中的最小值，並從隊列

Question

我有一次期末考試即將在幾周後刪除它，我們的做法的一個問題是這樣的：

考慮N個整數的隊列，找到隊列中的最小值並從隊列中刪除它。完成後，其餘的值必須爲 按原始順序排列。您只能使用隊列操作，即 您無權訪問陣列中的基礎存儲或鏈接的 列表。說明實施這一操作 和N.

我幾乎失去了作爲我怎麼會去這方面給予的順序（大O）時間最有效的方式。編輯：隊列操作是「排隊」，「出隊」，「isFull」，「isEmpty」，如果它是一個循環隊列，「前」和「後退」。

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）總的隊列操作 - 每元件。

有趣的事實：這個隊列的隱喻正是循環緩衝區背後的想法，它通常用於實現固定大小的隊列。