//------ 单链队列

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>

typedef struct Node
{
    int data;               //节点数据域
    struct Node * next; //节点指向下一个元素的指针域
}Node,* pNode;

typedef struct LinkQueue
{
    pNode front;  //队头指针
    pNode rear;   //队尾指针
}LinkQueue, * pLinkQueue;

//初始化队列
void init(pLinkQueue Q);
//销毁队列
void DestroyQueue(pLinkQueue Q);
//判断队列是否为空
bool is_empty(pLinkQueue Q);
//入列
void en_queue(pLinkQueue Q,int val);
//出列
bool de_queue(pLinkQueue Q,int * pVal);
//遍历输出队列元素
void treaverse(pLinkQueue Q);

int main(void)
{
    LinkQueue Q;

    init(&Q);
    en_queue(&Q,1);
    en_queue(&Q,2);
    en_queue(&Q,3);
    en_queue(&Q,4);

    treaverse(&Q);

    int val;

    if(de_queue(&Q,&val)){
        printf("出列成功，出列的值：%d \n",val);
    }

    treaverse(&Q);

    return 0;
}

void init(pLinkQueue Q)
{
    //构造一个空队列Q，只有一个头节点
    Q->front = Q->rear = (pNode)malloc(sizeof(Node));
    if(Q->front == NULL){
        printf("内存分配失败！");
        exit(-1);
    }

    Q->front->next = NULL;      //创建一个头节点，头节点的指针域没有指向下一个
}

void en_queue(pLinkQueue Q, int val)
{   
    //入队，从队列尾部开始
    //创建一个节点
    pNode pNew = (pNode)malloc(sizeof(Node));
    if(pNew == NULL)
    {   
        printf("开辟内存空间失败");
        exit(-1);
    }else{
        pNew->data = val;        //赋值
        pNew->next = NULL; 

        Q->rear->next = pNew;
        Q->rear = pNew;
    }
}

bool is_empty(pLinkQueue Q)
{
    if(Q->front == Q->rear) //队列头无指向就为空 || 或者队列头尾相等，说明是初始化时状态
        return true;
    else 
        return false;
}

bool de_queue(pLinkQueue Q,int *pVal)
{
    //出列
    if(is_empty(Q))
    {
        return false;
    }else{
        pNode p = Q->front;     //出列从头节点开始
        *pVal = p->next->data;
        Q->front = Q->front->next;      //摘下头节点
        if(Q->rear == p)        //如果出列到最后一个了，如果不互相等，那么队列尾就消失了 
        { 
            Q->rear = Q->front;
        }
        free(p);                //释放节点空间
        return true;
    }
}

void treaverse(pLinkQueue Q)
{
    pNode p = Q->front->next;

    while(p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }           

    printf("\n");
}