队列（链式队列，链表实现）

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

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

链式队列（LinkQueue）

结构体定义
typedef int ElemType;
typedef struct LinkNode{
    ElemType data; //数据域,存储队列元素
    struct LinkNode *next; //指针域,指向下一个结点的指针
}LinkNode;

front rear 是队列里的重点，用来表示队头队尾，在链表中是指针
带头结点的结构中 front 永远不变，指向头结点

链式队列的控制结构（记录队头/队尾指针）
typedef struct {
    LinkNode *front,*rear; //链表头，链表尾，也可以称为队头，队尾
    //front永远不变，指向头结点
}LinkQueue; 

初始化队列

Q.front 和 Q.rear 相等，是队列判空的条件 ，是初始化必须做的事。

队列的初始化，使用带头结点的链表来实现
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

队列的操作

*入队 ：根据先进先出的原则,要从尾部 rear 插入

入队
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *pnew=(LinkNode*)malloc(sizeof(LinkNode));
    pnew->data=x;
    pnew->next=NULL;
    Q.rear->next=pnew; //尾指针的next指向pnew，因为从尾部入队
    Q.rear=pnew; //尾指针向后移动
    // 等价于
    // Q.rear=Q.rear->next;
}

*出队 ：根据先进先出的原则,要从头部 front 插入，出队时还需要判断 队列是否为空

链表只剩一个结点 时，被删除后，要改变 rear ,一起和 front 指向头结点，否则会成为 野指针

出队
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.rear==Q.front){ //队列为空
        return false;
    }

    LinkNode *q=Q.front->next; //拿到第一个结点，存入q
    x=q->data;
    Q.front->next=q->next; //头结点指向第一个结点的next，让第一个结点断链

    if(Q.rear==q){ //链表只剩一个结点时，被删除后，要改变rear
        Q.rear=Q.front;
    }
    free(q);
    return true;
}

测试看看

通过链表来实现队列
int main() {
    LinkQueue Q;
    InitQueue(Q);

    EnQueue(Q,3);
    EnQueue(Q,4);
    EnQueue(Q,5);
    EnQueue(Q,6);
    EnQueue(Q,7);

    bool ret;
    ElemType element;
    ret=DeQueue(Q,element);
    if(ret){
        printf("DeQueue success element=%d\n",element);
    } else{
        printf("DeQueue failed\n");
    }
    return 0;
}