キューを別のキューで並べ替える

Question

サイズNのキューを別のサイズのキューと変数を使用して並べ替えるにはどうしたらいいですか？

未知の実装 - キューの最小値を見つけてそれを空のキューにプッシュし、新しい最小値を見つけて押し出すなどはO（n^2）です。より効率的なアルゴリズムはありますか？

Answer 1

純粋な実装がうまくいくとは思いません。それは待ち行列なので、待ち行列の最後になければ最小の要素を取り除くことはできません。

私が考えることができる唯一の方法は次のとおりです。 2番目のキューを常にソートしておいてください。 1. q1から要素を削除します。 2.この要素> = q2の最後の要素の場合は、それをq2に挿入します。 （そのようにして、q2はまだソートされています）。 3.それ以外の場合は、q1に戻します。 q1が空になるまで上記の手順を繰り返します。

Answer 2

私のアルゴ：ここ

let the Q size = n, 
1 save = getRearValue(1stQ) 
2 pop the element from 1st Q and insert it into 2nd Q. 
3 if getFrontValue(1stQ) > getRearValue(2ndQ) 
4  then goto step 2. 
5 else 
6  pop the element from 1st Q and insert back into the same Q (1st Q). 
7  if (save != getRearValue(1stQ)) goto step 3. 
8 if (1st Q not sorted OR getFrontValue(1stQ) > getFrontValue(2ndQ)) 
9   then 
10   pop all elements of 2nd Q and insert into 1st Q (One by one). 
11   goto step 1. 
12 else 
13  pop all elements of 2nd Q and insert into 1st Q (One by one). 
14  return 1stQ 

Answer 3

は、私は私の頭の上から思い付いた単純な論理です。最悪の場合の実行時間はO（N^2）であり、理想的にはO（N）であることが理想的です。私は、即興の論理によって複雑さをさらに減らすことができると思う。

構文はJavascriptですが、わかりやすくコメントされています。

こちらがお役に立てば幸いです。

// SORT A QUEUE USING ANOTHER QUEUE 
function sortQueueUsingQueue(uq) { 
    // instantiate required variables 
    var sq = new Queue(); 
    var t = null, last = null; 
    // copy the items to a temp queue 
    // so as not to destroy the original queue 
    var tq = new Queue(uq); 
    // loop until input is not empty 
    while(!tq.isEmpty()) { 
     t = tq.dequeue(); 
     if (last && last <= t) { 
      // new element will be at the end of the queue, and we don't have to 
      // process any further - short-circuit scenario 
      // this is the best case scenario, constant time operation per new item 
      sq.enqueue(t); 
      // also keep track of the last item in the queue, 
      // which in this case is the new item 
      last = t; 
     } else { 
      // other scenario: linear time operation per new item 
      // new element will be somewhere in the middle (or beginning) so, 
      // take elements from the beginning which are less or equal to new item, 
      // and put them at the back 
      while(!sq.isEmpty() && sq.peek() <= t) { 
       sq.enqueue(sq.dequeue()); 
      } 
      // when that is done, now put the new element into the queue, 
      // i.e the insertion into the proper place 
      sq.enqueue(t); 
      // following which, shift the rest elements to the back of the queue, 
      // to reconstruct the sorted order, 
      // thus always keeping the second queue sorted per insertion 
      while(sq.peek() > t) { 
       // meanwhile, also keep a track of the last (highest) item in the queue 
       // so that we may perform a short-circuit if permitted 
       last = sq.dequeue(); 
       sq.enqueue(last); 
      } 
     } 

    } 
    return sq; 
} 

あなたはここにgithubの要旨として全体の作業コードを表示することができます。https://gist.github.com/abhishekcghosh/049b50b22e92fefc5124

Answer 4

は、ここで私は仕事かもしれないと思う方法です： -

アルゴリズムは、キューをソートするために再帰を使用しています。

たちは次のように別のキューに上のキューからコピーできる機能copy_fromを持っていると仮定します -

void copy_from (ArrayQueue&Q_from,ArrayQueue& Q_to){ 

    while(!Q_from.empty()){ 

     int t= Q_from.front(); 
     Q_to.enqueue(t); 
     Q_from.dequeue(); 
    } 

} 

示すように、メインのソート機能がある： -

void sort(ArrayQueue &Q, int element, ArrayQueue&Q2){ 

if(Q.size()==1){ 

    if(Q.front()>element){ 

     int front = Q.front(); 
     Q.dequeue(); 
     Q.enqueue(element); 
     Q.enqueue(front);  
    } 
    else{ 
     Q.enqueue(element); 
    } 

} 
else{ 

int front = Q.front(); 
Q.dequeue(); 
sort(Q,front); // sort the remaining queue. 

int sorted_front = Q.front(); //get front element of sorted queue 
if(element<sorted_front){ 

    Q2.enqueue(element); 
    copy_from(Q,Q2); 
    copy_from(Q2,Q);  

} 
else{ 
    // dequeue all elements from the queue which are lesser than element and put it into new queue. 
    // Then enqueue the new element 
    // Then enqueue whatevers bigger than element into the queue. 

     Q2.enqueue(sorted_front); 
     Q.dequeue(); 

     while(!Q.empty()&&Q.front()<element){ 
     Q2.enqueue(Q.front()); 
     Q.dequeue(); 
     } 

     Q2.enqueue(element); 
     copy_from(Q,Q2); 
     copy_from(Q2,Q); 

} 

} 
} 

ときに最初に我々 -

Queue Q, Q2; 

int front = Q.front(); 
Q.dequeue(); 
sort(Q,front,Q2); 

6> 4->と入力した場合、 9> 2-> 1の場合、結果は9→6-> 4-> 2-> 1となります。