2つの一時キューだけを使用してキューをリバースする方法はありますか？

Question

2つの一時キュー（カウンタなどの他の変数はありません）だけを使用して、キュー内のアイテムの順序を逆にする方法はありますか？ ENQUEUE（e）、DEQUEUE（）、EMPTY（）？標準キュー操作のみ使用できます。

任意の言語または擬似コードによるソリューションは大歓迎です。

Answer 1

元のキューから最後のアイテムを最終キューに入れて、一時キューにすべてのアイテム（最後のアイテムを除く）をデキューする方法です。最後に1つのテンポラリキューから別のテンポラリキューにコピーし、最後のキューを最後のキューにコピーするたびに、繰り返します。うーん....良い方法がありますか？

Answer 2

次のことが可能です。

• Use the two queues to simulate a stack。
• 元のキューのすべての要素をこのスタックにプッシュします。
• スタックから各要素をポップし、元のキューに追加します。

Answer 3

while(!queue.EMTPY()) 
{ 
    while(!finalQueue.EMPTY()) 
    { 
     tempQueue.ENQUEUE(finalQueue.DEQUEUE()); 
    } 
    finalQueue.ENQUEUE(queue.DEQUEUE()); 
    while(!tempQueue.EMPTY()) 
    { 
     finalQueue.ENQUEUE(tempQueue.DEQUEUE()); 
    } 
} 

私はそれが動作するはずだと思います。一時キューと最終キューを元のキューからデキューするたびにスワップできる場合は、より効率的な方法があります。

Answer 4

答えははいです。私は宿題のように聞こえるので、そこに残したいと思うが、面白い問題だと思う。

これら3つの操作しか使用できない場合は、両方のテンポラリキューを使用する必要があります。

基本的にメインキューからデキューし、そのアイテムを一時キューAに入れる必要があります。一時キューB（最初は空）からすべてのアイテムをAにデキューします。次に同じことをAからBに戻しますあなたは常に空のtempキューにエンキューしてから、もう一方のtempキューのすべてのアイテムを入れます。反転させるキューが空の場合、空でない一時キューからデキューしてプライマリキューにエンキューするだけで、元に戻すことができます。

私は擬似コードを与えるでしょうが、また、私はあなたの宿題をやっていることを心配しています。

Answer 5

// REVERSE OF QUEUE USING 1 QUEUE N OTHER DEQUEUE 
void reverse() { 
    int q1[20],q2[20],f1,r1,f2,r2; 
    while(f1!=r1) { 
    q1[r2]=q1[f1]; 
    r2=r2+1; 
    f1=f1+1; 
    } 
    //whole elements of temporary queue is transfered to dequeue. 
    while(r2!=f2) { 
    q1[r1]=q2[r2]; 
    r2=r2-1; 
    r1=r1+1; 
    } 
} 

Answer 6

これは一種の似たTower of Hanoiパズルにある:)

ここ

は、C＃でのソリューションです：

static Queue<T> ReverseQueue<T>(Queue<T> initialQueue) 
{ 
    Queue<T> finalQueue = new Queue<T>(); 
    Queue<T> intermediateQueue = new Queue<T>(); 

    while (initialQueue.Count > 0) 
    { 
     // Move all items from the initial queue to the intermediate queue, 
     // except the last, which is placed on the final queue. 
     int c = initialQueue.Count - 1; 
     for (int i = 0; i < c; i++) 
     { 
      intermediateQueue.Enqueue(initialQueue.Dequeue()); 
     } 
     finalQueue.Enqueue(initialQueue.Dequeue()); 

     // Swap the 'initialQueue' and 'intermediateQueue' references. 
     Queue<T> tempQueue = initialQueue; 
     initialQueue = intermediateQueue; 
     intermediateQueue = tempQueue; 
    } 

    return finalQueue; 
} 

Answer 7

私はこのスレッドが長い死んでいる実感が、私は私が見つけたと信じてすべての要件を満たすかなり良いソリューションです。

一時キューは1つだけ必要です。元のキューが空でない限り、最後のノードへのポインタを設定し、ノードを元のキューに戻して再エンキューすることによって、キュー内の最後のノードを先頭に移動します。 その後、元のキューから削除し、一時キューにエンキューします。 その後、tempを元のキューにコピーします。

ここでC、ADTスタイルの私のソリューションです： （少なくとも私はあなたのためにあなたの宿題をやって心配する必要はありません）

QUEUE * reverseQueue（QUEUEの*キュー） {

QUEUE *temp; 
QUEUE_NODE *pLast; 
void *dataPtr; 

//Check for empty queue 
if(emptyQueue(queue)) 
    return NULL; 

//Check for single node queue 
if(queueCount(queue) == 1) 
    return queue; 

temp = createQueue(); 
while(!emptyQueue(queue)) 
{ 
    pLast = queue->rear; 
    //Move last node to front of queue 
    while(queue->front != pLast) 
    { 
     dequeue(queue, &dataPtr); 
     enqueue(queue, dataPtr); 
    } 
    //Place last node in temp queue 
    dequeue(queue, &dataPtr); 
    enqueue(temp, dataPtr); 

} 
//Copy temp queue back to original queue 
while(!emptyQueue(temp)) 
{ 
    dequeue(temp, &dataPtr); 
    enqueue(queue, dataPtr); 
} 
destroyQueue(temp); 
return queue; 

}

Answer 8

我々は最初のキューのデキューに2つの以上のキュー 最後のものを除くすべての要素を必要とし、第二のキューにそれらをキューキューコンテンツであるキューから文字列を逆にします。 キューの最後の3番目のキューに最後の要素をエンキューします.2番目から1番目のキューにトランザクションを、3番目のスタックに最後の要素をエンキューします。 両方のスタックが空になるまでこれを繰り返します。