algorithm - 使用递归对队列进行排序

Question

问题是这样的:

您需要在添加到队列的新成员方法 void sort() 中对队列进行排序。

规则是:

• 你不能使用任何循环。只允许递归。
• 您可以根据需要创建任意数量的私有(private)方法。
• 您可以创建和使用两个同类的辅助队列(称之为队列 - 具有默认构造函数)。
• 你对队列的内部结构一无所知。
• 提供给您的唯一方法是:bool empty()、Data peek()、Data dequeue()、void enqueue(Data d)
如果列表为空，
• dequeue() 返回 null，enqueue() 忽略 null 输入。
• 排序顺序需要升序(队列前面的值应该是最小的)。
• 可比较的值是Data结构中的整数，称为x。

我知道可以解决。我还没有找到答案。任何想法将不胜感激。

Answer 1

开始对 N=2 个元素的队列进行排序。

现在 - 解决这个问题后 - 如果对 N 个元素进行排序，则改进对 N+1 个元素进行排序的解决方案。

---

更新:

现在，在你完成作业后，我可以在 scala 中展示一个替代解决方案:

   private def insert (a: Int): Unit = {
     if (isEmpty || a <= peek) enqueue (a)
     else {
       val h = dequeue 
       insert (a)
       enqueue (h)
     }
   }
   
   def sort (): Unit = 
    if (! isEmpty) {
      val head = dequeue
      sort 
      insert (head)
    }

它在没有明确的第二个队列的情况下工作。插入是一个 sortedInsert。

val q = new Queue (List (4))
q.enqueue (7)
q.enqueue (9)
q.enqueue (8)
q.enqueue (2)
q.enqueue (3)

val x = q.debug 
x: List[A] = List(3, 2, 8, 9, 7, 4)

q.sort 
val x = q.debug 
x: List[A] = List(2, 3, 4, 7, 8, 9)

我使用列表来实现队列，但仅将其用于创建新队列和调试原因。避开也没什么大不了的，只是速度更快，我想先从排序开始。 :)