排序int queqe的限制

Question

我需要僅使用一個其他隊列，最終數量的變量，並且只使用「isEmpty」，「enqueue」，「dequeue」對隊列進行排序。 我試過這樣做了一天，我只是沒有找到它。我在各地搜查，這種限制沒有問題，你認爲這可能嗎？

Answer 1

如果它在java中，這是一個正常的冒泡排序。

public void sort(Queue<Integer> q){ 

    //save first num into copy 
    Queue<Integer> copy = new Queue<Integer>(); 
    int length=0; 
    while(!q.isEmpty()){ 

     copy.add(q.remove()); 
     length ++; 
    } 

    int maxNum, temp; 
    while(!copy.isEmpty()){ 

     maxNum=copy.remove(); 
     temp=0;   
     copy.add(maxNum); 
     //search for the max number 
     for(int i=0; i<length-1; i++){ 
      temp = copy.remove(); 
      if(temp > maxNum) maxNum= temp; 
      copy.add(temp); 
     } 
     //delete it from copy and add it to q 
     for(int i=0; i<length; i++){ 

      temp = copy.remove();  
      if(temp == max){ 
       q.add(max); 
       break; 
      } 
      copy.add(temp); 
     } 
     length --; 
    } 
} 

它應該工作。 so，說明：

計數q並保存在副本中。 現在你可以通過複製來刺激它，知道它有多少值。 因此搜索最大數量，將其插入q並從中移除副本。 做完之後，減小長度，因爲 現在複製的元素少了一個元素並重復，直到長度== 0 並對q進行排序。

排序q並需要兩個隊列的算法如下所示： q中的foreach元素 將q插入副本時，找到它的最大值。 確保你以某種方式將q插入到沒有最大編號 的副本中，然後將其插入到新的排序隊列中。 完成之後，重新插入q並複製，直到最後q爲空 。

該算法的整點是我們使用 一個額外的隊列通過q刺激。 和另一個爲了保存結果，同時刺激。 因爲如果我們不會使用另一個隊列來刺激q 我們將無法知道何時停止刺激。

但是如果我們知道何時停止通過q的刺激（知道它的長度） 我們並不需要額外的隊列，所以我們只能使用另一個隊列。

我不認爲你甚至需要另一個隊列。給我 半小時，我會用 只給我們的隊列編程一個算法。

當您對數組進行排序時，使用我們目前擁有的排序算法的 類型，爲了排序它小於O（n^2），您必須使用O（n）的內存。 這與說你永遠不會使用最終數量的變量 如果你想要小於O（n^2）相同。 你希望它使用最終數量的變量，所以我自動假設你只需要一個簡單的O（n^2）算法。 我認爲你可以做合併排序。我明天去做吧。

Answer 2

什麼是變量的最終數量？問題陳述缺失的是如何比較每個隊列的前端元素。是否有返回隊列中元素數量的大小函數？

對於2個隊列，可以實現自底向上合併排序，但每個隊列需要一些變量來跟蹤每個隊列中的邏輯邊界。邏輯邊界將每個隊列有效地分爲兩部分，即前（舊）部分和後（新）部分。這是一種時間複雜度爲O（n log（n））的排序。

調用A和B上所有元素的兩個隊列。如果沒有大小函數，則將A複製到B以生成元素數。

在A和B之間均勻分開元素（一個爲A，一個爲B，...）。

合併排序重複合併來自A和B的運行，交替A和B之間的合併運行輸出。在第一次傳遞時，合併大小爲1的運行形成大小爲2的運行，下一次大小爲2被合併以形成大小爲4的運行，依此類推，直到2次運行合併到單個隊列中的最後一次通過。