#ifndef LINKQUEUE_H

#define LINKQUEUE_H

#include <stdio.h>

#include <malloc.h>

typedef enum

{

    OK=, //正确

    ERROR=,   //出错

    TRUE=,  //为真

    FALSE=   //为假

}status;

typedef int ElemType;   //宏定义队列的数据类型

/* 链式队列：是指采用链式存储结构的队列，队列中每一个元素对应链表中的结点。

 * 和链式栈类似，一般采用单链表来实现链式队列。

 *************************************************************/

// 链式队列结点结构

typedef struct Node

{

    ElemType data;    //结点数据

    //【负责建立队列各结点之间的联系，前一个结点的next指向后一个结点，形成链式队列】

    struct Node *next;  //后继结点

}LQNode;

// 链式队列结构

typedef struct

{

    LQNode *front;      //链式队列的队头指针，总是指向队列的头结点(出队一次，第二个结点变为头结点)

    LQNode *rear;       //链式队列的队尾指针，入队时指向新插入结点(总是指向队列的最后一个结点)

}LinkQueue;

//创建空队列

status initQueue(LinkQueue *pQHead);

//销毁队列

void destroyQueue(LinkQueue *pQHead);

//清空队列

void clearQueue(LinkQueue *pQHead);

//判断队列是否为空

status isEmpityQueue(LinkQueue *pQHead);

//获得队列长度

int getQueueLen(LinkQueue *pQHead);

//新元素入队 [先进先出原则：在队尾的位置插入] element-要插入元素

status enQueue(LinkQueue *pQHead,ElemType element);

//新元素出队,同时保存出队的元素 [先进先出原则：在队头的位置删除]

status deQueue(LinkQueue *pQHead,ElemType *pElement);

//遍历队列

void queueTraverse(LinkQueue *pQHead);

#endif // LINKQUEUE_H

#include "linkqueue.h"

/*********************************************************************

 * 刚开始创建空队列时，队列的队头和队尾指针相等都指向头结点，头结点的数据域不存放数据

 * 第一次入队，创建新结点，其数据域保存新插入元素，头结点的next指向新结点,

 * 并且队列的队尾指针指向新结点,队列的队头指针仍然指向头结点,依次类推

 * 第一次出队，则队列的队头指针指向头结点的next,依次类推

 *********************************************************************/

//创建空队列： pQHead即为队列头结点

status initQueue(LinkQueue *pQHead)

{

    //队列头结点的队头和队尾指针申请内存

    pQHead->front = pQHead->rear = (LQNode*)malloc(sizeof(LQNode));

    if(!pQHead->front) //检测是否申请失败

    {

        printf("pQHead->front malloc error!\n");

        return ERROR;

    }

    //设置头结点指针域为空

    pQHead->front->next = NULL;

    return OK;

}

//销毁队列

void destroyQueue(LinkQueue *pQHead)

{

    free(pQHead->front);

    free(pQHead->rear);

    pQHead->front = pQHead->rear = NULL;

}

//清空队列

void clearQueue(LinkQueue *pQHead)

{

    pQHead->front = pQHead->rear;

}

//判断队列是否为空

status isEmpityQueue(LinkQueue *pQHead)

{

    //队头指针与队尾指针相等，说明队列为空

    if(pQHead->front == pQHead->rear)

        return TRUE;

    return FALSE;

}

//获得队列长度

int getQueueLen(LinkQueue *pQHead)

{

    LQNode *temp = pQHead->front;

    int length = ;

    while(temp != pQHead->rear)

    {

        ++length;

        temp = temp->next;

    }

    return length;

}

//新元素入队:即链式队列的尾结点指针，指向存放新元素的新结点

status enQueue(LinkQueue *pQHead, ElemType element)

{

    //创建新结点,并申请内存

    LQNode  *temp = (LQNode*)malloc(sizeof(LQNode));

    if(!temp)

    {

        printf("temp malloc error!\n");

        return ERROR;

    }

    temp->data = element; //将要插入元素存入新结点的数据域内

    temp->next = NULL; //队列只能从队尾插入所以下一个结点初始化为NULL

    //链式队列元素为结点(LQNode)

    //pQHead->rear为队列的最后一个结点，当插入新结点temp时,pQHead->rear->next = temp

    //使前一个结点的next指向新结点，建立队列各结点之间的联系

    pQHead->rear->next = temp; //将队尾结点的后继指针指向新结点,如果第一次入队，

                      //则pQueue->rear->next相当于pQueue->front->next

    // pQHead->rear总是指向队列的最后一个结点

    pQHead->rear = temp;    //将队尾结点的指针指向新结点temp,temp变为最后一个结点

    return OK;

}

status deQueue(LinkQueue *pQHead,ElemType *pElement)

{

    //如果队列为空,则返回ERRIR

    if(isEmpityQueue(pQHead)==TRUE)

    {

        printf("queue is NULL!\n");

        return ERROR;

    }

    //值入队一次后就出队，则pQueue->front->next==pQHead->rear->next,为第一个插入的结点

    LQNode *temp = pQHead->front->next; //初始化temp为要出队的结点的指针

    //如果要出队的结点为最后一个结点,使q->rear指向头结点防止出现悬空的指针

    if(pQHead->front->next == pQHead->rear)

        pQHead->rear = pQHead->front;

    *pElement = temp->data; //将出队的数据元素存入*e

    pQHead->front->next = temp->next; //使下一个结点成为队头,如果没有下一个结点则为NULL

    free(temp); //删除要出队的结点

    temp = NULL;

    return OK;

}

//遍历队列

void queueTraverse(LinkQueue *pQHead)

{

    //如果队列为空

    if(isEmpityQueue(pQHead)==TRUE)

    {

        printf("\nqueue is NULL!\n");

    }

    LQNode *temp = pQHead->front;

    printf("将队列中的所有元素出队:\n");

    while(temp != pQHead->rear)

    {

        temp = temp->next;

        printf("%d  ", temp->data);

    }

    printf("\n");

}

/*********************************************

 * C实现链式队列   2017/10/26   by nieXianFeng

 *********************************************/

#include <stdio.h>

#include "linkqueue.h"

int main()

{

    int value;          //用于保存出队的元素

    //给头结点申请内存

    LinkQueue *pQHead= (LinkQueue*)malloc(sizeof(LinkQueue));

    if(!pQHead) //检测是否申请失败

    {

        printf("pQHead malloc error!\n");

        return ERROR;

    }

    //调用初始化队列的函数

    initQueue(pQHead);

    //调用出队函数

    enQueue(pQHead, );

    enQueue(pQHead, );

    enQueue(pQHead, );

    enQueue(pQHead, );

    enQueue(pQHead, );

    enQueue(pQHead, );

    enQueue(pQHead, );

    enQueue(pQHead, );

    //调用遍历队列的函数

    queueTraverse(pQHead);

    //调用出队函数

    if(deQueue(pQHead, &value)==OK)

    {

        printf("出队一次，元素为：%d\n", value);

    }

    queueTraverse(pQHead);

    if(deQueue(pQHead, &value)==OK)

    {

        printf("出队一次，元素为：%d\n", value);

    }

    queueTraverse(pQHead);

    printf("队列长度是%d\n",getQueueLen(pQHead));

    clearQueue(pQHead);   //清空队列

    queueTraverse(pQHead);

    free(pQHead);

    pQHead = NULL;

    return ;

}