enqueue（）メソッドは、キューに要素を1つ追加します。C++で実装する方法は？

Question

C++の配列添字がゼロで始まるので、このメソッドを実装しようとするのは苦労しています。このメソッドは、1つの要素をキューに追加します。 f（前）およびr（後）ポインタとサイズnのシーケンシャルリストを使用できます。追加の変数が必要であることがわかったら、無料になりました。ありがとう。私の試しザッツ

が、私はその間違って知っている：私はポインタで動作するにはどうすればよい

void QueueAr::enqueue(const Object& x){ 
    prov = (r % n) + 1; 
    if(prov != f){ 
     r = prov; 
     queueArray[r] = x; 
     if(f = -1){ 
      f = 0 
     } 
    }else{ 
     //queue is full 
    } 
} 

を？私がNULLを指すように開始すると、ポインタ演算を使用できなくなります。

Answer 1

プレーン・アレイを使用してキューを実装するには、循環的に処理します。つまり、配列内の空き領域がなくなると、0に折り返します。フロント・リアのレコードをあなたは注意します。 （Xは、キュー内のアイテムを表している）の例としては：

// Rear is where to enqueue into, Front is where to dequeue from 
Empty Array: 
| - - - | 
Front = -1, Rear = 0 

Enqueue() 
| X - - | 
Front = 0, Rear = 1 

Enqueue() 
| X X - | 
Front = 0, Rear = 2 

Dequeue() 
| - X - | 
Front = 1, Rear = 2 

Enqueue() 
| - X X | 
Front = 1, Rear = 0 // Looped around 

Dequeue() 
| - - X | 
Front = 2, Rear = 0 

Enqueue() 
| X - X | 
Front = 2, Rear = 1 

あなただけの周りにラップする剰余演算を使用する必要があります。もちろん、これはサイズが限られています（要素が足りなくなると、より多くのメモリを割り当てる必要があります）が、配列を扱うときに得られるものです。ここで

は（私は全くそれをチェックしていない）スタートとしていくつかのコードです：

// Private class variables: 
// These should be set in the constructor of your queue class 
unsigned int rear = 0; // back of the queue 
unsigned int front = -1; // front of the queue 
unsigned int numStored = 0; 
unsigned int length; 
Object* array = new Object[length]; 

QueueAr::Enqueue(Object& obj) 
{ 
    if (front == rear) 
    { 
     // Throw an exception: queue is full! 
    } 
    else 
    { 
     array[rear] = obj; // Insert the object at the back 
     rear++; 
     rear = rear % length; 
     numStored++; 
    } 
} 
// For kicks, here's the queue code 
QueueAr::Dequeue(Object& obj) 
{ 
    if (numStored == 0) 
    { 
     // Throw an exception: queue is empty! 
    } 
    front++; 
    front = front % length; 
    numStored--; 
} 

Answer 2

STLを使用していない場合は、リンクリストを使用することができます。エンキューするには、リストの最後に追加します。デキューするには、リストの先頭から削除します。パフォーマンスと利便性のために、リストの両端にポインタを格納する必要があります。

Answer 3

あなたは、特定の配列のサイズに制限している場合は、「プレーンオールを使用して簡単にキューを実装することができますCアレイ。 2つのポインタ/インデックス（キューの先頭とキューの終わり）が必要です。配列自体も必要です。

キューがオーバーフローするのを防ぐには、（1）ラップするか、（2）最後に到達したときに配列をコピーします。どちらの方法もやや簡単ですが、ラッピングは簡単で高速です。データ要素の折り返しは、circular bufferを使用して呼び出され、キューおよびオーディオバッファーに共通です。

Queue: 0 1 4 3 6 8 0 0 0 0 0 
Start: ^
End:    ^

Dequeue: return 4 (read, then move start to right) 
Queue: 0 1 4 3 6 8 0 0 0 0 0 
Start:  ^
End:    ^

Enqueue: 9 (write, then move end to right) 
Queue: 0 1 4 3 6 8 9 0 0 0 0 
Start:  ^
End:    ^

Wrapping enqueue: 2 (write, then move to right and wrap to beginning) 
Queue: 0 1 4 3 6 8 9 3 4 7 2 
Start:  ^
End: ^