上一章我们讨论了队列的顺序存储的实现，这一章我们换一种方式来实现队列

链式队列实现

我们再次强调，队列只是一种逻辑结构，是一种“先进先出”的线性表，所以和线性表一样，我们可以采用：
-顺序存储
-链式存储
的方式来实现队列。
这一章我们重点讲解如何使用链式存储的方式实现一个队列，如果对顺序存储方式实现不清楚的可以查看一下这篇文章 队列的顺序实现;

一些提前定义的变量和结构体：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int Element; /* Element类型根据实际情况而定，这里假设为int */

//定义节点
typedef struct SqNode
{
    Element data;
    struct SqNode * next;
} SqNode;
//定义队列，实际我们只需要使用定义队头和队尾指针
typedef struct
{
    SqNode *front, *rear;
}SqQueue;

创建队列，我们这里使用一个头节点来标记队列的队头，头节点不存储数据，只是为了方面后续的操作

/// 初始化队列，创建队列中链表的头节点
Status InitQueue(SqQueue * Q)
{
    Q->front = Q->rear = (SqNode *)malloc(sizeof(SqNode));
    
    if (Q->front == NULL) {
        return ERROR;
    }
    
    Q->front->next = NULL;
    
    return OK;
}

///销毁队列，头节点也需要销毁
Status destroyQueue(SqQueue * Q)
{
    //已经在销毁队列了，所以认为Q->rear已经失去了存在的意义，所以这里用Q->rear来标记Q->front的下一个节点
    while (Q->front) {
        
        Q->rear = Q->front->next;
        Q->front->next = NULL;
        free(Q->front);
        Q->front = Q->rear;
    }
    
    return OK;
}

/// 清空队列，保留头节点
Status clearQueue(SqQueue *Q)
{
    if(Q->front == Q->rear) return OK;
    
    SqNode *p,*k;
    
    p = Q->front->next;
    Q->rear = Q->front;
    Q->front->next = NULL;
    
    while (p) {
        
        k = p->next;
        free(p);
        p = k;
    }
    
    return OK;
}

/// 队列是否为空，如果队头和队尾指针指向了同一个元素，则表示该队列为空队列
Status isQueueEmpty(SqQueue Q)
{
    return Q.front == Q.rear;
}

///队列的长度
Status queueLength(SqQueue Q)
{
    int i = 0;
    SqNode *p = Q.front->next;
    while (p) {
        i++;
        p = p->next;
    }
    
    return i;
}

/// 元素入队，
Status inQueue(SqQueue *Q,Element e)
{
    if(Q->front == NULL) return ERROR;
    
    SqNode * node = (SqNode *)malloc(sizeof(SqNode));
    if(node == NULL) return ERROR;
    node->data = e;
    node->next = NULL;
    
    //将新元素添加到队尾
    Q->rear->next = node;
    //将队尾指针指向最后一个位置
    Q->rear = node;
    
    return OK;
}

/// 出队
Status outQueue(SqQueue *Q, Element *e)
{
    //判断队列是否y为空
    if(Q->rear == Q->front) return ERROR;
    
    SqNode * s = Q->front->next;
    Q->front->next = s->next;
    *e = s->data;
    s->next = NULL;
    //判断弹出的元素是不是在队尾，如果是，则需要将队尾指针指向对头，否则释放后，Q->rear将是野指针
    if(Q->rear == s) Q->rear = Q->front;
    free(s);
    
    return OK;
}

/// 获取对头元素
Status getHead(SqQueue Q,Element *e)
{
    //判断队列是否为空
    if(Q.rear == Q.front) return ERROR;
    
    *e = Q.front->next->data;
    return OK;
}

///打印队列元素
void printQueue(SqQueue Q)
{
    if(Q.front == Q.rear) return;
    
    SqNode * p = Q.front->next;
    printf("队列元素:");
    while (p) {
        
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

测试

int main(int argc, const char * argv[]) {
    // insert code here...
    
    Status iStatus;
    Element d;
    SqQueue q;
    
    //1.初始化队列q
    iStatus = InitQueue(&q);
    
    //2. 判断是否创建成
    if (iStatus) {
        printf("成功地构造了一个空队列\n");
    }
    
    //3.判断队列是否为空
    printf("是否为空队列?%d (1:是 0:否)\n",isQueueEmpty(q));
    
    //4.获取队列的长度
    printf("队列的长度为%d\n",queueLength(q));
    
    //5.插入元素到队列中
    inQueue(&q, -3);
    inQueue(&q, 6);
    inQueue(&q, 12);
    
    printf("队列的长度为%d\n",queueLength(q));
    printf("是否为空队列?%d (1:是 0:否)\n",isQueueEmpty(q));
    
    //6.遍历队列
    printQueue(q);

    //7.获取队列头元素
    iStatus = getHead(q, &d);
    if (iStatus == OK) {
        printf("队头元素是:%d\n",d);
    }
    
    //8.删除队头元素
    iStatus =outQueue(&q, &d);
    if (iStatus == OK) {
        printf("删除了的队头元素为:%d\n",d);
    }
    
    //9.获取队头元素
    iStatus = getHead(q, &d);
    if (iStatus == OK) {
        printf("新的队头元素为:%d\n",d);
    }
    
    //10.清空队列
    clearQueue(&q);
    
    //11.销毁队列
    destroyQueue(&q);
    
    
    return 0;
}

结果输出：

测试结果