1. 队列

1. 队列：在一端插入，在另一端删除就是队列， 插入的一端叫做队尾， 删除的一端叫做队头。

2. 队列分为顺序队列和链式队列，本文主要介绍链式队列的使用，想了解顺序队列的同学欢迎浏览上期内容！

​3. 队列的特点: 先进先出。顺序队列占用一片连续存储空间进行操作，链式队列则是分散存储。

4. 我们依旧准备三个文件：linkqueue.c、linkqueue.h、main.c。

5. 请大家多看注释可帮助理解运用！

2. 链式队列的创建

队列的功能函数中不仅有 “ 出队入队 ” 还有一系列辅助实现功能的函数——判空、判满、清空、回收、显示队列元素函数。

（1）linkqueue.h

在头文件中，定义链式队列结构体、头尾指针结构体、做函数声明等操作。

#ifndef _linkqueue_h_
#define _linkqueue_h_

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

typedef int data_t;
//节点结构体
typedef struct node{
    data_t data;
    struct node *next;
}node;
//包含队列的队头队尾指针的结构体（方便出入队列）
typedef struct {
    node *front; //队头指针：链队列的头节点
    node *rear;  //队尾指针：链队列最后一个有效节点，空队则也指向头节点
}linkqueue;

//创建队列
linkqueue *linkqueue_create();
//判空
int linkqueue_empty(linkqueue *head);
//判满
int linkqueue_full(linkqueue *head);
//清空
void linkqueue_clear(linkqueue *head);
//回收
void linkqueue_destroy(linkqueue **head);
//显示
void linkqueue_display(linkqueue *head);

#endif

（2）linkqueue.c

1. 链式队列的特点是：

        拥有队头指针front -> 链队列的头节点；
        队尾指针 rear-> 链队列最后一个有效节点，空队则也指向头节点。

2. 理解代码时一定要特别关注这两个指针的指向！

3.创建队列时，注意不仅要创建头节点，还要创建队头，且初始化时队头队尾指针都指向头节点。同样回收队列时也需要一起释放头节点和队头。

#include "linkqueue.h"

//创建队列
linkqueue *linkqueue_create()
{
    //创建头节点
    node *headnode = (node *)malloc(sizeof(node));
    if(NULL == headnode)
    {
        printf("malloc failed!\n");
        return NULL;
    }
    memset(headnode, 0, sizeof(node));
    //头节点指针域置空
    headnode->next = NULL;
    //创建队头
    linkqueue *head = (linkqueue *)malloc(sizeof(linkqueue));
    if (NULL == head)
    {
        printf("malloc failed!\n");
        return NULL;
    }
    memset(head, 0, sizeof(linkqueue));
    //队头队尾指针都指向头节点
    head->front = headnode;
    head->rear = headnode;
    //返回队头
    return head;
}

//判空
int linkqueue_empty(linkqueue *head)
{
    return (head->front == head->rear);
}

//判满（永远不满）
int linkqueue_full(linkqueue *head)
{
    return 0;
}

//清空
void linkqueue_clear(linkqueue *head)
{
    node *p = head->front->next; //第一个有效节点 
    node *q = NULL;
    while (p)
    {
        q = p->next;
        free(p);
        p = q;
    }
    head->front->next = NULL; //把头节点指针域置空
    head->rear = head->front; //让头尾指针都指向头节点
}
//回收
void linkqueue_destroy(linkqueue **head)
{
    //先回收所有效节点
    linkqueue_clear(*head);
    //再回收头节点
    free((*head)->front);
    //最后回收队头
    free(*head);
    *head = NULL;
}

//显示
void linkqueue_display(linkqueue *head)
{
    node *p = head->front->next;
    while(p)
    {
        printf("%-3d",p->data);
        p = p->next;
    }
    puts("");
}

3. 出队、入队

（1）linkqueue.h

在头文件中加入出队、入队的函数声明。

//入队
int linkqueue_in(linkqueue *head, data_t data);
//出队
data_t linkqueue_out(linkqueue *head);

（2）linkqueue.c

1. 封装出队、入队的函数功能。

2. 注意插入数据是在尾指针处插入，删除数据是在头指针处删除。因为进行删除操作时，需要找到目标元素的前一个元素才能进行删除，而如果在尾指针处删除的话，需要找到尾指针指向元素的前一个元素，要找前一个元素就需要遍历队列了，这样效率较低。

//入队
int linkqueue_in(linkqueue *head, data_t data)
{
    //封装一个新节点
    node *p = (node *)malloc(sizeof(node));
    p->next = NULL;
    p->data = data;
    //入队
    head->rear->next = p;
    //尾指针加1
    head->rear = p;

    return 0;
}

//出队
data_t linkqueue_out(linkqueue *head)
{
    //判空
    if(linkqueue_empty(head))
    {
        printf("Linkqueue is empty!\n");
        return (data_t)-1;
    }
    //队头元素（要删除的元素）
    node *p = head->front->next;
    //记录出队元素数据域
    data_t data = p->data;
    //判断是否只有一个有效节点
    if(p == head->rear)
    {
        head->front->next = NULL;
        free(p);
        //此时队列为空
        head->rear = head->front;//尾指针指向头节点
    }
    else
    {
        head->front->next = p->next;
        free(p);
    }
    
    return data;
}

4. 在主函数中验证队列的功能

（1）main.c

#include "linkqueue.h"

int main(int argc, char *argv[])
{ 
    //创建队列
    linkqueue *head = linkqueue_create();
    if(NULL == head)
    {
        printf("malloc failed!\n");
        return -1;
    }
    linkqueue_display(head);

    //入队10个数
    printf("入队十个数：\n");
    int i = 0;
    while(i++ < 10)
    {
        linkqueue_in(head, i);
    }
    linkqueue_display(head);

    //出队
    printf("出队一个数为：%d\n",linkqueue_out(head));
    linkqueue_display(head);

    //回收队列
    linkqueue_destroy(&head);

    return 0;
} 

注：有些同学很爱忽略回收这一步，但记得malloc手动开辟的空间一定要及时free，否则会造成内存泄漏。

（2）运行结果展示

入队十个数：
1  2  3  4  5  6  7  8  9  10 
出队一个数为：1
2  3  4  5  6  7  8  9  10 

运行结果完美诠释了队列先进先出的特点。

5. 总结

1. 队列的先进先出是它独有的特点，在很多地方都有队列思想的实践，例如平时我们排队，也比如实现计算机中先来先处理的需求时，都有队列的身影。

2. 队列也是线性数据结构的一种，另外线性数据结构还包括线性表（顺序表、链表）、栈，它们各有各的特色，如想了解其他线性结构的使用，欢迎浏览主页相关文章！

3. 除了线性结构，还有非线性结构，比如树、图等，那非线性结构又是怎样来实现的呢？

敬请期待下集：C语言二叉树的实现（Binary tree）

感谢观看！如有疑问欢迎提出！

  ----香菜小猫祝这位uu天天开心----