循环队列

队列定义

只能在表的一段插入(入队/进队)，在表的另一端删除(出队/离队)。即FIFO。

逻辑表现

算法上表现为将数组元素围成圈，rear和front在同一个起点表示队空，rear移动后插入数据，删除数据后front向前走。
为了判断队满还是队空（因为满了后rear会走一步而和front在一起，因为设计上将在一起看作队空，所以此时满了走一步又在一起会导致无法判断队满队空），会牺牲一个储存单元，即循环队列中的data[MaxSize]和栈等算法相比较会少一个存储单元。
判断队满时只要让rear多走一步，若到front的位置即表明当前已队满。例:(Q.rear+1)%MaxSize==Q.front
循环中参考时钟周期循环的方式使用取模进行运算，每次rear+1后取模MaxSize，取模即进行周期运算。入队同理。

队头（Front）

允许删除的一端，又称队首。

队尾（Rear）

允许插入的一端

结构体

data[MaxSize]和front（队首）,rear（队尾）,数组只能存MaxSize-1个数据，比栈等算法少存一个

循环队列代码

结构体

有队首队尾和数据，如下：

#define MaxSize 5
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

初始化

main中声明后调用初始化函数，初始化目的将队首队尾都指向0号位置：

void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;       //初始化让队首和队尾都指向0号位置
}

判断队列是否空

判断队首和队尾是否相等即可：

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

入队

判断是否队满，保存数据后判断周期，将周期运算结果保存到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;
    return true;
}

出队

判断是否队空，数据保存到x。将front+1后判断周期，并将周期结果保存到front：

bool DelQueue(SqQueue &Q,ElemType &x){
    if(IsEmpty(Q)){
        return false;
    }
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

链表实现

声明两个结构体，分别是节点和队列（FIFO），声明节点是为了实现数据间的联系，声明队列是为了实现队列定义下节点间的联系。在链表中实现联系一般由指针体现（地址间的联系）：

typedef int Elemtype;
typedef struct LNode{
    Elemtype data;
    struct LNode *next;
}LNode;
typedef struct LinkQueue{
    LNode *front,*rear;
}LinkQueue;

初始化

分配空间，next设为NULL以作队列的尾部标识：

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LNode*)malloc(sizeof(LNode));
    Q.front->next=NULL;
}

入队

调用后先声明新节点，数据保存后因尾插法需要将新节点next设NULL，后将前一个节点的next链接上新节点，再移动rear标记到新节点上表明先最后一个节点为新节点：

void EnQueue(LinkQueue &Q,Elemtype x){
    LNode *pnew=(LNode*)malloc(sizeof(LNode));
    pnew->data=x;
    pnew->next=NULL;
    Q.rear->next=pnew;
    Q.rear=pnew;
}

出队

front是头指针不动，要判断位置，如果要出队节点是最后一个元素，则让rear到front位置使其相等，满足队空条件，如下：

bool DeQueue(LinkQueue &Q,int &x){
    if(Q.rear==Q.front){
        return false;
    }
    LNode *q=Q.front->next;
    Q.front->next=q->next;
    if(Q.rear==q){
        Q.rear=Q.front;
    }
    free(q);
    return true;
}

C语言创建循环队列的两种方式