//链队列
#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
typedef int ElemType;
typedef struct Node
{   
    ElemType data;
    struct Node *next;
}QNode, *PQNode;

typedef struct 
{
    PQNode front;
    PQNode rear;
}LQueue, *PLQueue;

void initLinkQueue(PLQueue Q)//初始化队列
{
    Q->front = Q->rear = (PQNode)malloc(sizeof(QNode));
    if(!Q->front)
        return;
    Q->front->next = NULL;
}
void ClearQueue(PLQueue Q)//清空队列
{
    PQNode p;
    while(Q->front->next != NULL)
    {
        p = Q->front->next;
        Q->front->next = p->next;
        free(p);
    }
    Q->rear = Q->front;
    Q->rear->next = NULL;
}

void DestroyQueue(PLQueue Q)
{
    ClearQueue(Q);
    free(Q->rear);
    Q->front = Q->rear = NULL;
}

int QueueLength(LQueue Q)//链表里获取头节点长度进行遍历时同样注意不要修改指针，也可以在头节点声明一个计数器，入队出队时计数器做加减
{
    PQNode p = Q.front->next;
    int len = 0;
    while(p != NULL)
    {
        len++;
        p = p->next; 
    }
    return len;
}

bool QueueEmpty(LQueue Q)
{
    if(Q.front == Q.rear)
        return 1;
    else 
        return 0;
}

void GetHead(LQueue Q, ElemType *e)//获取头节点值并赋值给e
{
    if(Q.rear == Q.front)
        return;
    *e = Q.front->next->data;
}

void DeQueue(PLQueue Q, ElemType *e)//出队，将队头节点赋值给e
{
    if(Q->front == Q->rear)//判断队列是否为空
        return;
    PQNode p = Q->front->next;//p指向队头节点
    *e = p->data;//赋值
    Q->front->next = p->next;//front指针指向下一个节点
    if(Q->rear == p)
        Q->rear = Q->front;//注意判断出队的是不是最后一个节点，重定向rear指针回头节点
    free(p);//释放p指向节点
}

void EnQueue(PLQueue Q, ElemType e)//入队
{
    PQNode p = (PQNode)malloc(sizeof(QNode));
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}

void Traverse(LQueue Q)//链表遍历一定要注意不能修改节点里的指针，可声明一个指针进行遍历
{
    PQNode p = Q.front->next;
    while(p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main()//测试
{
    ElemType e;
    LQueue Q;
    initLinkQueue(&Q);
    EnQueue(&Q, 12);
    EnQueue(&Q, 15);
    EnQueue(&Q, 18);
    GetHead(Q, &e);
    printf("头节点为 %d", e);
    printf("队列Q为：");
    Traverse(Q);
    printf("len = %d\n", QueueLength(Q));
    DeQueue(&Q, &e);
    printf("e = %d\n", e);
    printf("len = %d\n", QueueLength(Q));
    printf("队列Q为：");
    Traverse(Q);
}