数据结构——循环队列

可参考这篇文章，循环队列一般用静态数组实现，称之为队列的顺序存储类型。可使用如下结构体：

typedef struct
{
  Queue_EleType Buffer[Queue_Buffer_Size + 1];
  uint8_t front;    /*!<数据头 */
  uint8_t rear;     /*!<数据尾 */
} CircularQueue;

循环队列入队及出队示意图见下图：

循环队列实现的核心问题在于队满情况的判断。最普遍的做法是牺牲一个单元来区分队空和队满，入队时少用一个队列单元，即图中(d2)的情况。约定以“队头指针在队尾指针的下一位置“作为队满的标志，故在上述循环队列结构体定义中，Buffer的大小为Queue_Buffer_Size + 1。

下面给出循环队列具体实现：

初始化

void CircularInit(CircularQueue * Q)
{
  Q->front = 0;
  Q->rear = 0;
}

判断队列是否为空

bool CircularIsEmpty(CircularQueue * Q)
{
  if (Q->front == Q->rear)
    return TRUE;
  else
    return FALSE;
}

入队

ErrorStatus CircularEnQueue(CircularQueue * Q, Queue_EleType x)
{
  if ((Q->rear + 1) % (Queue_Buffer_Size + 1) == Q->front)
    return ERROR;
  Q->Buffer[Q->rear] = x;
  Q->rear = (Q->rear + 1) % (Queue_Buffer_Size + 1);
  return SUCCESS;
}

出队

ErrorStatus CircularDeQueue(CircularQueue * Q, Queue_EleType * x)
{
  if (Q->front == Q->rear)
    return ERROR;
  *x = Q->Buffer[Q->front];
  Q->front = (Q->front + 1) % (Queue_Buffer_Size + 1);
  return SUCCESS;
}

完整代码。