一、循环队列
环形队列，有两个指针：头指针和尾指针。在队尾写入，移动尾指针；从队列头部读取，移动头指针。环形队列，其特殊性在于"环形", 内存空间可以不断重复使用，无需频繁分配和释放内存。通常，我们用一个固定长度的数组来实现循环队列。
示意图：
- 1.初始化循环队列
初始化：创建一个空的顺序队列，需要设定队首指针和队尾指针都指向同一个位置，一般初始都设置为0，即队列为空。head = tail =0；
// 初始化环形队列
void CirQueueInit(Queue *queue)
{
queue->head = 0;
queue->tail = 0; // head等于tail表示循环队列为空
}
-
2.判空和判满
-
牺牲一个元素空间，来区别队空或队满。
判断是否为空：通过检查队首指针和队尾指针是否相等来判断队列是否为空，head==tail队列为空。
判断是否为满：当队尾指针指向数组的最后一个位置时，下一个要插入的位置就是队头指针,即(tail + 1) % SIZE == head时，队满。
// 判空 返回1队列空
int IsEmpty(Queue *queue)
{
return (queue->head == queue->tail);
}
// 判满 返回1队列满
int IsFull(Queue *queue)
{
return (queue->tail + 1) % SIZE == queue->head;
}
- 3.入队
元素入队：也被称为插入操作，是将一个新元素添加到队列尾部的操作。
入队时，tail指针变化：tail＝ （tail＋1）％SIZE；，queue[tail] = val；。
// 入队 val入队元素
int CirQueuePush(Queue *queue, int val)
{
// 如果队满，不能入队
if(IsFull(queue))
{
printf("队满，无法入队\n");
return 1; // 入队失败
}
queue->tail = (queue->tail +1) % SIZE;
queue->buf[queue->tail] = val;
return 0;
}
- 4.出队
元素出队：也被称为删除操作，是将队列头部的元素移除的操作。
出队时，head指针变化：head＝（ head ＋1）％SIZE，temp = queue[head]；。
// 出队 返回出队元素
int CirQueuePop(Queue *queue)
{
// 如果队空，不能出队
if(IsEmpty(queue))
{
printf("队空，不能出队\n");
return 1; // 出队失败
}
queue->head = (head + 1) % SIZE;
int temp = queue->buf[queue->head];
return temp;
}
- 5.取队头
头元素就是队列中的第一个元素，可以通过返回队首指针的值来获取。
// 获取队头元素
int GetCirQueueHead(Queue *queue)
{
if(IsEmpty(queue))
{
printf("队空，无元素\n");
return 1; // 出队失败
}
int temp = queue->head + 1;
return queue->buf[temp];
}
- 6.取队尾
队列中的最后一个元素，可以通过返回队尾指针的值来获取。
// 获取队尾元素
int GetCirQueueTail(Queue *queue)
{
if(IsEmpty(queue))
{
printf("队空，无元素\n");
return 1; // 出队失败
}
return queue->buf[queue->tail];
}
- 7.获取循环队列长度
（tial - head + SIZE）%SIZE
// 获取队列长度
int GetCirQueueLen(Queue *queue)
{
return (queue->tial - queue->head + SIZE)%SIZE;
}