使用相同的隊列對隊列進行排序

Question

我已經被問及這個問題，我認爲這是可行的，但是我很難想出一個算法來做到這一點。限制是你不能使用任何其他數據結構，也不能創建另一個隊列。你也只能使用入隊，出隊和偷看（不是優先隊列）。

thanx的貢獻:)

Answer 1

Sort(Q,n): 

    for i = 0 to n-1 
    min = findMin(Q, n-i, n) 
    reorder(Q, min, n) 
    end for 

findMin(Q, k, n): 

    min = infinity 

    for i = 1 to n 
    curr = dequeue(Q) 
    if curr < min && i<=k 
     min = curr 
    end if 
    enqueue(Q,curr) 
    end for 

    return min 

reorder(Q, min, n): 

    for i = 1 to n 
    curr = dequeue(Q) 
    if (curr != min) // I'm assuming that there is a way to differentiate between any two items, this isn't hard to enforce 
     enqueue(Q, curr) 
    end if 
    end for 

    enqueue(Q,min) 

升序排序，運行在O（N^2）的時候，在空間O（1）（即，隊列是O（n）的空間，並且額外的空間所需通過該算法是O（1））

說明：

本質上，我們通過隊列n次，每次迭代成本2n個迭代。

在每次迭代時，我們會遍歷整個隊列並在相關數量的項目中選取最小值。因此，首先相關數量的項目是n，因爲我們希望它們的全部最小。下一次迭代我們需要最小的n-1個項目，然後是n-2個項目等。由於算法將在最後堆疊這些最小值。

一旦我們找到最小值，我們需要重新遍歷整個堆棧，以便抓取它並將其堆疊到最後。

這裏的主要想法是，一個出隊列表後面跟着一個相同元素的排隊將允許我們迭代隊列並檢查最小/最大值，同時保持順序。

Answer 2

冒泡使用隊列：

n <- size of queue 
repeat n times 
    x <- dequeue item 
    repeat (n-1) times 
    y <- dequeue item 
    if x < y then 
     enqueue y 
    else 
     enqueue x 
     x <- y 
    enqueue x