Scalaの配列を使用したキュー実装のエンキューメソッド

Question

def enqueue(elem: T): Unit = {  
    A(rear) = elem 
    rear += 1 
    size += 1 
    if (size == 0) { 
     front = 0 
     rear = 0 
     } 
    if (size == A.length) { 
     grow() 
     } 
    } 

配列を使用してキューを実装していますが、エンキューメソッドに問題がありますが、間違いが正確にどこにあるのかわかりません。だから、私が間違いを犯した箇所についていくつかのヒントを教えてください。 上記のコードでは、sizeは配列キュー内の要素の数です。growは、配列が一杯になったときに配列を倍にする関数です。前もって感謝します。

Answer 1

あなたは何がうまくいかないかについて何も言わないので、これは暗闇の中のショットであり、選択したデータ構造については議論していません。

テストsize == 0は役に立ちません。enqueueの直後にサイズはゼロになりません。しかし、デキューが発生したときに何をするかを伝えることは、おそらく要素をfrontに戻し、frontを増やして、sizeを減分することです。

ので、いくつかの発言

1. 決して起こらないかもしれません エンキューの次の呼び出しのために、予防的に成長呼び出すことは驚くべきことです。 スペースが足りないときは、エンキューが非常に始まります
2. デキューとエンキュー時にデータが配列の右側に移動します。したがって、非常に少ないアイテム（サイズが小さい）のキューであっても、アイテムはアレイの右端にあり、スペースが足りなくなる可能性があります。成長のためのテスト（または少なくとも何かをするための）は、サイズではなくリアでなければなりません。
3. 結果的に、アレイの容量が必要以上に大きくなったとしても、成長するか、少なくとも何かをする必要があります。配列がほぼ満杯の場合は、実際には大きくなるはずです（スペースが残っていても、エンキュー/デキューのサイクルですべての値がコピーされ、パフォーマンスはO（N）になります）。しかし、自由空間の要素を配列の先頭に戻してください。

概要：リアは、配列の長さである場合にエンキューの開始時に、あなたは大きさが、配列、フロントの先頭に要素をコピーし、半分のスペースを言う未満

• でなければならない場合= 0、リア=サイズ
• サイズが大きい場合は、新しい配列を割り当て、あなたがsize == 0をテストしようとしている場合は、あなたが最初のことを行う必要があり、新しい配列

Answer 2

の先頭に要素をコピーします。

クラスのインバリアントとメソッドの事前条件と事後条件を文書化して、各メソッドがキューインプリメンテーション内部のキープロパティを保持していることを確認するのに役立ちます。 http://en.wikipedia.org/wiki/Design_by_contractを参照してください。

不変量は、サイズのようなものは、配列の長さ又はサイズ> = 0に常に以下であるとすることができます。