1

Robert Sedwick による C++ のアルゴリズムでの FIFO キュー配列の実装について読んでいます。配列が検出されました。「頭」と「尾」が等しい場合、キューは空であると見なされます。しかし、「put」で then が等しくなる場合は、満杯であると見なされます。エラーチェックを行うようにこのプログラムを拡張できるように、配列のサイズをクライアントがキューで見ると予想する要素の最大数よりも 1 大きくしています。

template <class Item>
class QUEUE
  {
    private:
      Item *q; int N, head, tail;
    public:
      QUEUE(int maxN)
        { q = new Item[maxN+1]; 
          N = maxN+1; head = N; tail = 0; }
      int empty() const
        { return head % N == tail; }
      void put(Item item)
        { q[tail++] = item; tail = tail % N; }
      Item get()
        { head = head % N; return q[head++]; }
  };

エラーチェックを行うためにユーザーが指定したよりも大きい配列1を割り当てるテキストで言及されているように、なぜ作者が私の質問です。ユーザー要求よりも 1 大きい割り当てがエラー チェックにどのように役立つかわかりません。サンプルコードを教えてください。

お時間をいただきありがとうございます。

4

2 に答える 2

3

配列が要素の最大数と同じサイズの場合、最後の要素を挿入するとtailが と等しくなり、 と を比較するだけでは空のキューとhead満杯のキューを区別できないためです。headtail

于 2012-08-24T09:38:42.600 に答える
0

余分なセルがなければ、maxN 要素を持つキューと空のキューを区別する方法はないと思います。どちらの場合も、ヘッドとテールは maxN を法とする同じ等価クラスにあるからです。

したがって、プットの直後にエラー処理を実行して、空の基準が満たされていないことを確認できると思います (つまり、容量を超えていることを意味します)。

void put(Item item)
{
  q[tail++] = item;
  tail = tail % N;
  // check that capacity is not exceeded.
  if (head % N == tail)
    throw;
}

同様に、get の開始時に、キューが空でないことを確認します。

それは理にかなっていますか？

于 2012-08-24T09:40:33.723 に答える