数据结构——循环队列

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

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

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

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

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

初始化

1
2
3
4
5
void CircularInit(CircularQueue * Q)
{
Q->front = 0;
Q->rear = 0;
}

判断队列是否为空

1
2
3
4
5
6
7
bool CircularIsEmpty(CircularQueue * Q)
{
if (Q->front == Q->rear)
return TRUE;
else
return FALSE;
}

入队

1
2
3
4
5
6
7
8
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;
}

出队

1
2
3
4
5
6
7
8
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;
}

完整代码