6

を使用して循環キューを実装することは可能arrayですか?

私が推測するもの：

不可能です。2 つのポインタがfrontありrear、最初のポインタがキューの最初の要素を指しているとします。

リア ポインターは 2 つの方法で定義できます。

1.キューに挿入された最後の要素を指すため、次のエントリは、挿入される次の要素の可能な場所です

2.次の要素が挿入される場所を指す

どちらの場合でも、配列の少なくとも 1 つのエントリを無駄にしないか、カウンターのカウントを維持しないと、満杯のキューと空のキューを区別できません。the number of inserted - number of deleted elements

4

4 に答える 4

2

一度実装したので、「空」と呼ばれる追加のブール値を使用しました。そうです、両方のポインターが同じ場所にある場合は区別できません。

使用するポインターによっては、1 つのポインターの最下位ビットを使用して空の変数を格納できます。
size が可変整数の場合、キューに要素がないことを示すために負の値を使用することもできます。

于 2013-06-22T10:20:30.943 に答える
1

最初に、first=0、rear=-1 とします。

次の方法で追加します..... array[rear]; リア=(リア+1)%MAX;

次の方法で削除します.. array[front]; フロント=(フロント+1)%MAX;

配列から要素を削除しながら、次のように条件を追加できます...
if(front==rear+1) first=0, rear=-1

空の条件は次のように指定できます...

if(rear==-1) printf("Empty");

完全な状態は次のようになります...

if ( ( front==(rear+1) || (front==0 && rear==(n-1) ) && rear!=-1 ) printf("Full");

これはうまくいくかもしれません。「カウント」機能は使用されていません

于 2013-12-04T17:31:48.273 に答える
0

別の方法として、3 つのポインターを使用する方法があります。3 番目のポインターは、2 つのポインターの間の場所を指します。これを実装する方法はいくつかあります。ただし、注意すべき重要なことは、中間ポインターは次の 2 つのことだけを伝える必要があるということです。

  • キューは空です。すべてのポインターは同じ場所を指します (リア ポインターの 2 番目の定義)。
  • キューには 1 つの要素があり、要素を削除すると空になります。中央のポインターと別のポインターが同じ場所を指しています。

これは、キューに 1 つ以上の要素がある限り、最初と最後のポインターの間に中間ポインターを保持し、最初または最後のポインターから 1 だけオフセットすることによって簡単に実行できます。

これはおそらく、カウンターを使用することに対するせいぜいほんのわずかな改善であり、最悪の場合さえあります。

于 2013-06-23T02:27:15.847 に答える