数据结构（9）队列之链队列

前言

队列同栈一样，本质都是操作受限的线性表。与栈不同的是，队列只允许在一端进行插入操作，在另一端进行删除操作，允许插入的一端称为队尾，允许删除的一端称为队头。从线性表的角度来看，也就是说队列只支持头部删除和尾部插入操作。它的特性就是先进先出，同生活中的排队现象类似。

链队列的初始化

只要认识到队列的本质是线性表，那么队列的链式存储和线性表的链式存储都是一致的，都需要考虑头结点的问题。如果设置了头结点，那么在初始化链队列时就需要生成一个头结点并为它赋初值；如果不设头结点则直接将队列赋空即可。为了方便操作，此处是设了头结点的。

其他操作同单链表基本一致，就不写了

源代码

LinkQueue.h

#ifndef LinkQueue_h
#define LinkQueue_h

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

#define ElemType int

typedef struct QueueNode{
    ElemType data;
    struct QueueNode *next;
}QueueNode;

typedef struct LinkQueue{
    QueueNode *fount;
    QueueNode *tail;
}LinkQueue;

//初始化
void InitQueue(LinkQueue *Q);

//入队
void EnQueue(LinkQueue *Q,ElemType x);
//出队
void DeQueue(LinkQueue *Q);
//展示
void ShowQueue(LinkQueue *Q);
//获取队首元素
void GetHead(LinkQueue *Q,ElemType *x);
//获取队列长度
void GetLength(LinkQueue *Q);
//清除
void ClearQueue(LinkQueue *Q);
//摧毁
void DestoryQueue(LinkQueue *Q);
#endif /* LinkQueue_h */

LinkQueue.c

#include "LinkQueue.h"

//初始化
void InitQueue(LinkQueue *Q){
    //申请头结点的空间
    QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
    assert(s != NULL);
    
    //初始化值
    Q->fount = Q->tail = s;
    Q->tail->next = NULL;
}
//入队->实际上就是尾部插入
void EnQueue(LinkQueue *Q,ElemType x){
    //申请新结点的空间并赋值
    QueueNode *s = (QueueNode *)malloc(sizeof(QueueNode));
    assert(s != NULL);
    s->data = x;
    s->next = NULL;
    
    //添加到队列尾部
    Q->tail->next = s;
    //重新设置队尾指针
    Q->tail = s;
}

//出队->实际上就是头部删除
void DeQueue(LinkQueue *Q){
    //取出首元结点
    QueueNode *s = Q->fount->next;
    //判断是否已空
    if (s != NULL) {
        Q->fount->next = s->next;
        free(s);
    }
    
    //判断删除的是否是最后一个结点
    if (Q->fount->next == NULL) {
        Q->tail = Q->fount;
        Q->tail->next = NULL;
    }
}

//展示
void ShowQueue(LinkQueue *Q){
    QueueNode *s = Q->fount->next;
    
    while (s != NULL) {
        printf("%4d",s->data);
        s = s->next;
    }
    printf("\n");
}

//获取队首元素
void GetHead(LinkQueue *Q,ElemType *x){
    if (Q->fount == Q->tail) {
        //队列为空，无法获取
        printf("队列已空\n");
        return;
    }
    
    QueueNode *s = Q->fount->next;
    *x = s->data;
}

//获取队列长度
void GetLength(LinkQueue *Q){
    int length = 0;
    QueueNode *s = Q->fount->next;
    while (s != NULL) {
        length ++;
        s = s->next;
    }
    printf("长度为:%d\n",length);
}

//清除
void ClearQueue(LinkQueue *Q){
    QueueNode *s = Q->fount->next;
    while (s != NULL) {
        Q->fount->next = s->next;
        free(s);
        s = Q->fount->next;
    }
    Q->tail = Q->fount;
    Q->tail->next = NULL;
}
//摧毁
void DestoryQueue(LinkQueue *Q){
    ClearQueue(Q);
    free(Q->fount);
    Q->fount = Q->tail = NULL;
}

Main.c

#include "LinkQueue.h"

int main(int argc, const char * argv[]) {
    
    LinkQueue Q;
    InitQueue(&Q);
    
    //入队
    for (int i = 0; i < 5; i ++) {
        EnQueue(&Q, i);
    }
    
    //展示
    ShowQueue(&Q);
    //出队
    DeQueue(&Q);
    ShowQueue(&Q);
    //求长度
    GetLength(&Q);
    //清除
    ClearQueue(&Q);
    GetLength(&Q);
    return 0;
}