2

クラスでの循環キューについて学習しているところですが、いくつか質問があります。以下に示すように、テールを最後の値の横の空のスペースとして定義するため、次のようになります。 

|1| |3|4|5|6|

頭は数字の3を指し、尻尾は1と3の間の空きスペースを指します。そのスペースがいっぱいになるとどうなるか混乱しています。たとえば、以下のようになります。

|1|2|3|4|5|6|

その場合、頭は引き続き3を指しますが、尾は前の空白のボックスの後の次のボックスを指す必要があるため、3またはヘッダーを指します。これについてどうすればよいですか？

4

4 に答える 4

6

When this situation occurs, your queue is full. You have a few options when to deal with new items that can be pushed:

  1. discard the pushed event: only when some other item is popped can now items be pushed again. Neither head nor tail is updated.

    Example: Think of an event queue that has filled up, new requests are simple ignored.

  2. discard (pop) the oldest event on the queue: in this case you update both the head and tail pointer one place.

    Example: buffering incomming image frames from a webcam for processing. For a 'live' feed you may prefer to discard the older frames when the processing has a hickup.

  3. create a bigger queue: that is, allocate more memory on the fly

    Example: you use a circular queue since it an efficient implementation that doesn't require memory allocation most of the time when you push items. However, you do not want to loose items on the queue so you allow reallocating more memory once in a while

What the right action is depends on your application.

PS.: Your implementation is based on keeping an empty slot in your queue to distinguish full and empty buffer. Another option is to keep a counter on the number of elements in your queue to make this distinction. More info can be found on Circular buffer (Wikipedia).

于 2012-07-05T21:06:50.183 に答える
3

私が思ったように、循環キューは「いっぱい」にならないため、部分的に循環しています。常に設定された数の要素を保持し、必要に応じて古い要素を破棄します。

したがって、空のスペースを埋めることは決してありません。新しい要素を挿入すると、古い要素が削除されるため、空のスペースが残ります。

つまり、ダイアグラムで新しい番号、たとえば0を挿入すると、キューは次のようになります（1最後の要素3が最初の要素であると想定）。

|1| |3|4|5|6|

次のようになります。

| |0|3|4|5|6|

ただし、循環キューの一部の実装では、必要に応じて、完全な長さに達したときに例外/エラーをスローするだけです。たとえば、これをチェックしてください。

于 2012-07-05T20:59:05.807 に答える
0

ヘッドとテールが同じ場所を指している場合、キューがいっぱいであると言います。これ以上要素を追加できません。要素を追加するには、キューから要素を削除する必要があります。これにより、ヘッドがインクリメントされ、スペースが再び生成されます。

于 2014-03-17T13:01:45.833 に答える
0

これは、私がこれまでに見つけたキューに関する最も簡潔な説明です。この基盤に基づいて、キューを拡張できます。出典: Robert Sedgewick による「アルゴリズム」。

const max=100;

var queue: aray[0..max]of integer;
     head,tail: integer;

procedure put(v:integer);    
  begin
    queue[tail] := v;   
    tail := tail + 1;   
    if (tail > max) then tail := 0;
  end;

function get: integer;  
  begin
    get := queue[head];
    head := head + 1;   
    if (head > max) then head := 0; 
  end;

procedure queueinitialize;   
  begin
    head := 0;
    tail := 0;
  end;

function queueempty: boolean;   
  begin   
    queueempty := (head = tail);
  end;

"キューの先頭 (head) と末尾 (tail) の 2 つのインデックスを維持する必要があります。配列の末尾に到達すると、「ラップアラウンド」は 0 に戻ります。head = tail の場合、キューは空であると定義されます。head = tail + 1、または tail = max かつ head = 0 の場合、キューはいっぱいであると定義されます。 "

于 2013-07-09T00:44:25.663 に答える