キューの擬似コードを使用してスタックを実装する

Question

次の擬似コードで混乱します

■単一のキューを使用してスタックを実装します。具体的には、エンキュー を使用し、キューのデキュー操作を使用して、スタック上にプッシュ/ポップ操作のための 疑似コードを書き込みます。キュークラスに が与えられているとします。単一のキューqを使用します。私は、スタックの底がキューのバックであることを認識

プッシュ（x）の

s = q.size() 
q.enqueue(x) 
for(int i = 0; i < s; i++) 
q.enqueue(q.dequeue()) 

pop() 
if q.isEmpty() 
“Exception” 
return q.dequeue() 

をスタックの最上位であるキューの先頭を考えてみましょう。だから私たちがエンキューするとき、スタックの最下位に行く必要があります。だから私たちはスタックからすべてを取り除き、そのアイテムを押し込んでからすべてを戻す必要があります。私は "for（int i = 0; i <s; i ++）を理解していません。 q.enqueue（q.dequeue（））"これは私が何を話していると思っていますが、ありがとうございました！

Answer 1

スタックは、挿入される最後の要素が返される最初の要素（LIFO）であるデータ構造です。単純キュー（FIFO）は、要素が挿入された順に要素を返す構造体です。

あなたが尋ねているループは、キューの並べ替えを行うことで、挿入されたばかりの要素が最初に返されるようになりました。より正確には、他のすべての要素をデキューしてキューに入れます。これにより、最初に挿入された要素が返されます。他のすべての要素は、挿入された要素の後にキューされています。つまり、挿入された要素が最初にデキューされることを意味します。

Answer 2

forループ内でキューがどのように変化するかを分析します。キューに

6 7 8 

、あなただけの左側に追加し、のみを取ることができます。コードは、ちょうどあなたがすでに3つの値を追加したとしましょう新しい要素を追加し、残りの部分を書き換え）

s = q.size() .   // Initial queue: (in) -> A -> B -> C -> (out) 
q.enqueue(x)     //   (in) -> D -> A -> B -> C -> (out) 
for(int i = 0; i < s; i++) 
    q.enqueue(q.dequeue()) // i == 0: (in) -> C -> D -> A -> B -> (out) 
           // i == 1: (in) -> B -> C -> D -> A -> (out) 
           // i == 2: (in) -> A -> B -> C -> D -> (out) 
pop() 
if q.isEmpty() 
    “Exception” 
return q.dequeue() 

Answer 3

右。スタックと

、あなたは目標は、このように、右側の次の値（9）を追加することである。すなわち、右側に追加し、右側に取りたい：

6 7 8 9 

しかし、キューで、あなただけの左側に追加することができます。

9 6 7 8 

だから、あなたが何をしたいのか、が有効なを使用して、左から右、一度に1から値（6 7 8）を既存のサイクルでありますキューアクション：

だから、

┌─> 8 9 6 7 ─┐ 
└───────────────┘ 

┌─> 7 8 9 6 ─┐ 
└───────────────┘ 

┌─> 6 7 8 9 ─┐ 
└───────────────┘ 

、既存の値のために、あなたは、新しい値を追加し、新しい値を追加する前にキューのサイズを取り、アップフロントな回数を最後の値を動かすことを行うにはすなわち、size回。