写在前面：

本系列文章是本人在复习《数据结构》的过程中整理的学习笔记，内容比较简短，形式比较单一。目的不在于获得多少阅读、点赞和收藏，只为记录本人的学习过程。

若有幸被您看到，希望能对您有所帮助，若您发现本文中有出错的地方，望不吝赐教，我定会虚心改进。希望看到此篇文章的您，前进路上不迷茫，未来一片光明。

目录

一、队列的基本概念

1、定义

2、重要术语

3.链式队列

二、链式队列的表示

三、链式队列的基本操作

 1.链式队列的创建和初始化

 2.判断队列是否为空

 3.链式队列的入队操作

4.链式队列的出队操作

 5.取队头元素

一、队列的基本概念

1、定义

队列(Queue)是只允许在一端插入（入队），在另一端删除（出队）的线性表

2、重要术语

❤队头：允许进行删除的一端
❤队尾：允许进行插入的一端
❤空队列：队列中没有任何元素
❤队列的特性：先进先出（First In First Out,FIFO) 

3.链式队列

队列的链式表示为链队列，它实际上是一个同时带有队头指针和队尾指针指针的单链表。
表头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点 

二、链式队列的表示

#include typedef int ElemType;struct Node{ElemType data;      //数据域struct Node* next;  //指针域};typedef struct Node PNode; //定义结点类型struct LinkQoeue{PNode* front;//队头指针PNode* rear; //队尾指针};typedef struct LinkQueue PLinkQueue; //定义链式队列类型

三、链式队列的基本操作

 1.链式队列的创建和初始化

动态申请一个空间，让队头指针和队尾指针指向空，表示队列为空。

PLinkQueue* CreateEmptyQueue(){PLinkQueue* plqu = (PLinkQueue*)malloc(sizeof(PLinkQueue));    if (plqu == NULL)    //结点空间申请失败    {    return NULL;}plqu->front = NULL;  //队头指针指向空plqu->rear = NULL;   //队尾指针指向空return plqu;  //返回创建的队列}

 2.判断队列是否为空

链式队列为空条件：队头指针和队尾指针指向空，也可以说队头指针等于队尾指针。

bool EmptyQueue(PLinkQueue* plqu){   //当队头指针等于队尾指针时，队列为空if (plqu->front == plqu->rear){return true;}return false;}

 3.链式队列的入队操作

首先说明：链式的队列不需要判断队列是否已满，只要条件允许，链式队列可以一直进行入队操作，这也是链式存储的一大优点。

操作过程：

❤首先申请一个新的结点空间，将要入队的元素存储在新结点的数据域；

❤然后将结点的指针域指向空；

❤再将先创建的结点链接到队尾；

❤最后修改队尾指针。

bool Enqueue(PLinkQueue* plqu, ElemType e){PNode* s = (PNode*)malloc(sizeof(PNode);  //动态申请一个新的结点空间if (s == NULL)    //新结点空间申请失败{return false;}s->data = e;      //先结点空间存储入队元素s->next = NULL;   //新结点的指针域指向空 palu->rear->next = s;    //将新结点链接到队尾，即链表尾部plqu->rear = s;   //修改队尾指针return true;}

4.链式队列的出队操作

操作过程：

❤判断队列是否为空，若为空，则报错

❤新建一个结点指向队头

❤用e存储队头结点元素

❤判断队尾是否在队头的下一个结点，即队列是否只有一个元素，若是，将队列设置为空队列

❤修改队头指针

❤释放新建结点

bool DeQueue(PLinkQueue* plqu, ElemType* e){if (plqu->front == plqu->rear)   //判断队列是否为空{return false;}PNode* p = plqu->front;   //创建新结点指向队头*e = p->data;      //用e存储队头元素if (plqu->rear == p)      //判断队列是否只有一个结点{plqu->rear = plqu->front;    //将队列设置为空队列}plqu->front = p->next;    //修改队头指针free(p);    //释放指向队头的指针return true;}

 5.取队头元素

其基本操作与出队操作大致相同，只是不用修改队头指针。

bool GetHeadElem(PLinkQueue* plqu, ElemType* e){if (plqu->front == plqu->rear){return false;}*e = plqu->next->data;return true;}

 Man is the master of life.

Only through the prism of career can one find the value of  self_survival.

下篇预告：《C语言实现循环队列》 

女主播