使用相同的队列对队列进行排序

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