考虑以模板类buffer实现. 假设buffer<T>类中包含一个长为n的vector<T>型向量Q, 需要实现如下成员函数:
void buffer<T>::push(const T& item);    // 将新元素item放到队尾.
void buffer<T>::pop();                  // 删除队首元素.
bool buffer<T>::full() const;           // 判断队列是否已满.
bool buffer<T>::empty() const;          // 判断队列是否为空.
此外, 我们还得保证n > 0. 为简便起见, 下面略去代码实现中关于模板参数的部分, 并且以图6.2为例讲解.

    而在讨论设计之前, 必须对其做简单的模型假设. 首先push操作必须和full操作搭配使用, 而pop操作也必须和empty操作搭配使用.其次push操作和pop操作的总次数基本相等, 因为每个元素的出入基本守恒. 基于上述考虑, 我们必须设计出综合性能较好的方案,
即不能为某个成员函数特殊优化. 一般而言, 实现一种抽象数据类型之前, 对其作出简单且有针对性的考察会大有裨益.

6.3.1 使用两个位置指示
    不妨在buffer模板类中设置front和rear两个size_t型变量表示队列首尾元素的位置信息,下面基于这两个变量实现buffer}模板类的成员函数.

利用真实首尾位置

    容易想到的方案是真实位置: 令front为队首元素位置(对应图6.2中q_0),而rear为队尾元素位置(对应图6.2中q_4). 于是入队和出队操作分别实现为:
void buffer<T>::push(const T& item)
{
  rear = (rear + 1) % n;    // 先改变队尾位置.
  Q[rear] = item;           // 再插入新元素.
}

void buffer<T>::pop()
{
  front = (front + 1) % n;
}

    据此可设计判断队空和队满的条件. 若队列中仅有一个元素, 则此时front和rear应相等, 逆向思考此前的入队操作,于是empty函数为:
bool buffer<T>::empty() const
{
  return (front == (rear + 1) % n);
}
但是随之而来的问题是队列中不能存储n个元素, 因为这样会使队空和队满的判断条件完全一样而招致错误(例如队列全满时无法执行出队操作).为此需限制队列中最少得留一个空位, 因此full函数为:
bool buffer<T>::full() const
{
  return (front == (rear + 2) % n);
}

    front和rear的初值需满足队空条件, 且最好取值为Q中真实位置, 例如front可取0,而rear取n - 1.

队尾位置挪后

    可以看出, 直接使用真实队尾位置时, 判断队空和队满的条件都比较复杂. 关键在于对rear的操作, 不妨将其向后挪一格, 让rear指向队尾后一元素的位置(即图6.2中e_0).于是可实现buffer模板类的成员函数如下:
void buffer<T>::push(const T& item)
{
  Q[rear] = item;           // 注意此时先插入新元素.
  rear = (rear + 1) % n;    // 再改变队尾位置.
}

void buffer<T>::pop()
{
  front = (front + 1) % n;
}

bool buffer<T>::empty() const
{
  return (front == rear);
}

bool buffer<T>::full() const
{
  return (front == (rear + 1) % n);
}
可以看出这里实际上相当于用(rear + 1) % n替换了rear, 从而减少了判断时的算术运算.有兴趣的读者可思考为何不用(rear + 2) % n替换rear而去简化判断队满操作呢?

    front和rear的初值选取规则可相应给出. 注意为保证首次入队时数据能存于Q[0], 应令front和rear初始均为0.

    事实上, 此方案的物理意义也很明确, 即front}指向队首元素, 而rear}指向当前需要插入的位置.处理队首元素找front}即可, 而rear}位置当前无元素, 入队可直接放入.

队首位置提前

    虽然从逻辑上看, front向前挪一格可以取得与rear向后挪一格相同的效果,但是这样会让队首元素变为Q[(front + 1) % n], 而实际中我们常常要操作队首元素而很少关心队尾元素, 因此该方案不甚合适.

使用计数信息

    仅使用队列首尾位置不但不能利用向量的所有空间, 还会让判断队空和队满的条件变得复杂. 然而, 究其本质是信息不足.实际上, 无论在哪种方案中, 若固定队列的front变量, 则队列中元素个数存在n + 1种情况(注意存在队空状态),而rear变量的取值只有n种可能(从0到n - 1).矛盾正在这里. 此外, 这也是前文中我们先定好队空条件再考虑队满条件的原因,若设定队满条件为向量所有元素均被利用, 那么队空条件就无法考虑了.

    由于队列中有一个元素无法利用, 我们索性再加入变量count来记录队列中当前元素个数, 从而简化了判断队空和队满操作.而从抽象数据类型角度看, 队列通常得具备size成员函数, 因此count变量一身二任, 非常划算.

取模运算优化

    注意到这里的取模运算其实意义不大而且速度较慢, 仅在变量取值为n}时才变成0}, 所以我们可以改用判断语句来提升效率. 

缓冲区

    我们采用count作为状态信息, 注意到缓冲区实际上是一个循环意义下的区间(队尾位置挪后), 所以改用left和right的表述形式, 这样就得到了一个较好的缓冲区实现方案.

在线代码27 https://github.com/xiexiexx/DSAD/blob/main /second-edition/src/buffer.h
#include <vector>

#ifndef BUFFER_CLASS
#define BUFFER_CLASS

template <typename T>
class buffer {
public:
buffer(size_t n);
  T&front();
  const T&front() const;
  void push(const T& item);
  void pop();
size_tsize() const;
  bool empty() const;
  bool full() const;
size_tcapacity() const;
private:
std::vector<T> Q;
  // 缓冲区容量实为Q.size(), 单独设置length是为了避免频繁调用.
size_tlength;
  // 缓冲区元素个数.
size_tcount;
  // 缓冲区循环意义下的区间[left, right).
size_tleft;
size_tright;
};

// 构造函数的实现.
template <typename T>
buffer<T>::buffer(size_t n)
  : Q(n), length(n), count(0), left(0), right(0)
{
}

// 返回队首.
template <typename T>
T& buffer<T>::front()
{
  return Q[left];
}

// 返回队首的常量版本.
template <typename T>
const T& buffer<T>::front() const
{
  return Q[left];
}

// 入队操作.
template <typename T>
void buffer<T>::push(const T& item)
{
  // 由用户判断是否缓冲区已满, 此处只实现入队.
  Q[right++] = item;
  if (right == length)
    right = 0;
  ++count;
}

// 出队操作.
template <typename T>
void buffer<T>::pop()
{
  if (++left == length)
    left = 0;
  --count;
}

// 返回缓冲区实有元素个数.
template <typename T>
size_t buffer<T>::size() const
{
  return count;
}

// 判断缓冲区是否为空.
template <typename T>
bool buffer<T>::empty() const
{
  return (count == 0);
}

// 判断缓冲区是否已满.
template <typename T>
bool buffer<T>::full() const
{
  return (count == length);
}

// 返回缓冲区最大容量.
template <typename T>
size_t buffer<T>::capacity() const
{
  return size;
}

#endif  // BUFFER_CLASS