1

我正在阅读 Robert Sedwick 在 C++ 中的算法中的 FIFO 队列数组实现。队列的内容是数组中“头”和“尾”之间的所有元素，考虑到结束时回绕回 0遇到数组。如果“头”和“尾”相等，则认为队列为空；但是如果“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，并且您将无法仅通过比较来区分空队列和完整队列head和tail。

于 2012-08-24T09:38:42.600 回答
0

我认为，如果没有额外的单元格，就无法区分具有 maxN 个元素的队列和一个空队列，因为在这两种情况下，头和尾将在同一个等价类中以 maxN 为模。

所以，我想错误处理可以在 put 之后立即进行，以检查是否不满足空标准（这意味着超出了容量）：

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 回答