队列（循环队列，数组实现）

队列（Queue）是一种线性数据结构，核心规则是 “先进先出”（First In, First Out，简称 FIFO），就像日常生活中的：排队买东西：第一个排队的人最先买到，最后来的人最后买；

队列只允许在一端（队尾，Rear） 添加元素（入队），在另一端（队头，Front） 删除元素（出队），中间的元素无法直接操作

循环队列（CirQueue）

front rear 是队列里的重点，用来表示队头队尾，在静态数组中是可以认为是下标。

最大容量是 MaxSize-1 个元素。

原因是：为了区分 “队列满” 和 “队列空” 这两种状态 —— 如果不预留这个空间，front == rear 这个条件会同时表示 “空” 和 “满”，导致无法判断队列的真实状态。

一、假设数组最大容量 MaxSize=5 ，不预留空间时：

• 入队 3 个元素： 3→4→5，此时 front=0， rear=3（正常）；
• 继续入队 2 个元素： 6→7 ，此时 rear 从 3→4→0（循环取模），最终front=0，rear=0；
• 此时 front == rear，但队列是满的（5 个元素都存满了），和“空队列”的条件完全一样！

无法通过front == rear判断：到底是队列空，还是队列满？

二、预留一个空间时
为了区分“空”和“满”，循环队列的设计规则改为：故意预留一个空间不存储元素，把“队列满”的条件从 front == rear 改为 (rear + 1) % MaxSize == front。用同一个 MaxSize=5 的例子（实际最多存 4 个元素）：

• 初始化空队列：front=0，rear=0 （ front == rear → 空）；
• 入队 4 个元素：3→4→5→6，此时 rear 从 0→1→2→3→4；
• 检查满条件：(rear+1)%5 = (4+1)%5 = 0，恰好等于 front=0 → 判定为 “满”；

此时队列实际只存了 4 个元素，下标 0、1、2、3 有值，下标 4 是空的（预留空间）。

空队列的判断条件: front 和 rear 指向同一个位置时。

• front == rear（唯一判定条件）

满队列的判断条件

• (rear + 1) % MaxSize == front（唯一判定条件）

#define MaxSize 5
typedef int ElemType;

typedef struct {
    ElemType data[MaxSize]; //数组，存MaxSize-1个元素
    int front,rear; //队列头，队列尾
}CirQueue;

初始化循环队列
void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0; //初始化循环队列，就是让头和尾都指向零号位置
}

判空
bool IsEmpty(SqQueue Q){
    return Q.front==Q.rear;
}

*入队 :入队前检查队列是否已满

入队
bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front){ //判断循环队列是否满了，满了就不能入队了
        return false;
    }
    Q.data[Q.rear]=x; //入队
    Q.rear=(Q.rear+1)%MaxSize; //rear要加1，指向下一个位置，如果大于数组最大下标，回到开头
    return true;
}

*出队 :出队前检查队列是否为空

出队
bool DeQueue(SqQueue &Q,ElemType &x){
    if(IsEmpty(Q)){ //判断队列是否为空
        return false;
    }
    x=Q.data[Q.front]; //出队
    Q.front=(Q.front+1)%MaxSize; //
    return true;
}

循环队列的代码实战
int main() {
    SqQueue Q;
    InitQueue(Q);

    bool ret;
    ret=IsEmpty(Q);
    if(ret){
        printf("SqQueue is Empty\n");
    }

    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    ret= EnQueue(Q,6);
    ret= EnQueue(Q,7);
    ret= EnQueue(Q,8);
    if(ret){
        printf("EnQueue success\n");
    } else{
        printf("EnQueue failed\n");
    }

    ElemType element; //存储出队元素
    ret=DeQueue(Q,element);
    if(ret){
        printf("DeQueue success\n");
    } else{
        printf("DeQueue failed\n");
    }

    ret= EnQueue(Q,8);
    if(ret){
        printf("EnQueue success\n");
    } else{
        printf("EnQueue failed\n");
    }
    return 0;
}