目录

一、链式队列的基本概念和结构

1.1 链式队列的基本概念

1.2 链式队列的优点

1.3 链式队列的实现方式及结构

二、链式队列的接口函数实现

2.1 链式队列的接口函数 

2.2 链式队列的设计（结构体）

2.3 链式队列的初始化

2.4 入队

2.5  出队

2.6 获取队头元素值

2.7 获取有效元素个数

2.8  判空

2.9 打印

2.10 清空

2.11 销毁

三、测试

四、总结

---

一、链式队列的基本概念和结构

1.1 链式队列的基本概念

       链式队列是队列基于单链表的一种存储表示。在单链表的每一个结点中有两个域:data存放队列元素的值，指针域存放单链表下一个结点的地址.队列的队头指针指向单链表的第一个结点,队尾指针指向单链表的最后一个结点。

1.2 链式队列的优点

        链式队列的优点是可以动态地分配内存空间，因此在入队和出队操作时不会有固定大小的限制，而且可以很灵活地处理数据的插入和删除。另外，链式队列相比于数组实现的队列，不会出现队列满的情况，因此不需要进行元素的搬移操作。然而，链式队列也有一些缺点，其中最主要的是由于使用了指针，因此在访问队列中的元素时需要额外的指针操作，这会增加一定的时间开销。另外，链式队列的空间开销相对于数组实现的队列会更大，因为每个节点都需要额外的指针空间来存储指向下一个节点的地址。

1.3 链式队列的实现方式及结构

       在设计顺序栈时，入栈和出栈的操作，数据都是通过尾插或者尾删进行的，很明显它的入栈和出栈时间复杂度都是O(1)，在设计链式栈时，入栈和出栈的操作，数据都是通过单链表的头插和头删进行的，很明显它的入栈和出栈的时间复杂度也都是O(1)，在设计循环队列时，让数据不动，让数组元素的下标动，设置队头队尾两个指针front和rear，分别指示队列头元素及队尾元素的位置。这样每次插入和删除便不需要挪动数据，达到O(1)的时间复杂度要求。那么我们如何设计链式队列，让队列也能达到O(1)的时间复杂度呢？

 

 

        对上面进行分析，队列的原则是一端入，一端出，那么我们应该如何设计哪一端入和出，从而保证时间复杂度达到O(1)呢？我们知道带头结点的单链表，头的操作（头插和头删）的时间复杂度都可以达到O(1)，那么，我们就会有两种设计方式：第一种：队头入队尾出，第二种：队头出队尾入，我们进行分析：第一种，队尾出，也就是尾删，我们知道尾删必须要找到待删除节点的上一个节点，对于单链表，必须从头开始遍历，找到待删节点的上一个节点，因此它的队尾出的时间复杂度为O(n)，不符合要求，对于第二种，队尾入，是可以达到O(1)的时间复杂度的，因为头结点此时的设计与有效节点不同，它存在一个队尾指针，直接指向最后一个有效节点，因此，尾插（队尾入）此时便可以直接插入，不用通过遍历找到合适的插入位置！因此，我们选择队尾入队头出，这与队列的概念刚好吻合。

二、链式队列的接口函数实现

2.1 链式队列的接口函数 

     链式队列与循环队列相同，基本操作有：初始化，入队，出队，判空，获取队头元素值，获取有效值个数，清空，销毁，打印。这里详细展示这些基本操作的实现思想和画图分析以及代码实现和算法效率分析，

      注意：链式队列由于它是按需索取，因此，不需要进行判满和扩容操作；

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "queue_list.h"
#include <vld.h>//初始化
void Init_QueueList(struct QueueList *ql);//入队
bool Push(struct QueueList *ql, ELEM_TYPE val);//出队
bool Pop(struct QueueList *ql);//判空
bool IsEmpty(struct QueueList *ql);//获取队头元素值
ELEM_TYPE Front(struct QueueList *ql);//有效数据节点个数
int Get_length(struct QueueList *ql);//清空
void Clear(struct QueueList *ql);//销毁
void Destroy(struct QueueList *ql);//打印
void Show(struct QueueList *ql);

2.2 链式队列的设计（结构体）

      通过第一小节的分析：我们可以知道，链式队列的有效数据节点的结构体设计和头节点结构体设计是不相同的，头节点的不使用数据域，因此，就直接不设计数据域，直接设计成两个指针域，一个队头指针，另一个是队尾指针；有效数据节点和单链表的有效数据节点设计相同，包括数据域和指针域。

typedef int ELEM_TYPE;//有效数据结点结构体设计
struct QNode
{ELEM_TYPE data;//数据域struct QNode* next;//指针域
};//链式队列头结点结构体设计
//这里只能队尾指针处入队 在队头指针处出队
typedef struct QueueList
{struct QNode *front;//队头指针struct QNode *rear;//队尾指针
}QueueList, *PQueueList;

2.3 链式队列的初始化

 初始化主要是对其指针域赋值， 此时，链式队列为空链表，两个指针域均为NULL！

//初始化
void Init_QueueList(struct QueueList *ql)
{//0.传入的指针参数断言assert(ql!=NULL);//此时，链式队列为空链表，两个指针域均为NULLql->front = NULL;ql->rear = NULL;
}

2.4 入队

    头插的基本思路如下：

    第0步：assert对传入的指针检测；

    第1步：购买新节点（购买好节点之后，记得将val值赋值进去）；

    第2步：找到合适的插入位置；

    第3步：插入，注意核心代码，先牵右手，再牵左手！！！否则会发生内存泄漏。

这里需要注意的是特殊情况：当链表为空时，也是修改三个指针的指向，但是，是另外的三个指针的指向！因此需要分情况讨论，对特殊情况处理。

 

//入队
bool Push(struct QueueList *ql, ELEM_TYPE val)
{//0.传入的指针参数断言assert(ql!=NULL);//1.购买新节点struct QNode * pnewnode = (struct QNode *)malloc(1 * sizeof(struct QNode));pnewnode->data = val;//1.5 要区分，到底是空队列 还是 非空队列//2.找到合适的插入位置if(IsEmpty(ql)){//链表为空pnewnode->next = NULL;ql->front = ql->rear = pnewnode;return true;}//3.链表不为空，正常插入 struct QNode *p = ql->rear;pnewnode->next = p->next;// == pnewnode->next = ql->rear->next;p->next = pnewnode;ql->rear = pnewnode;return true;
}

 

2.5  出队

对于删除操作，则需要对链表进行判空操作！并且删除操作遵循基本同样的4个步骤，需要理解加记忆。删除操作的基本思路如下：

①:用指针q指向待删除节点；
②:用指针p指向待删除节点的前驱节点；(头删的话，这里p可以被plist代替)
③:跨越指向；
④:释放待删除节点。

需要注意的是：当链式队列只有一个有效节点时，需要修改两个指针指向！

 

//出队
bool Pop(struct QueueList *ql)
{//0.传入的指针参数断言assert(ql!=NULL);//1.判空if(IsEmpty(ql)){return false;}//2.指针q指向待删除结点 指针p指向待删除结点的上一个结点struct QNode *q = ql->front;//p可以用ql代替//2.5 判断是否仅有唯一一个有效结点，单独处理if(ql->front->next == NULL){//存在唯一的节点ql->front = ql->rear = NULL;free(q);return true;}//3.不是唯一的节点，正常的删除，跨越指向+释放ql->front = q->next;free(q);return true;
}

 

2.6 获取队头元素值

   直接返回第一个有效节点的数据域即可！

//获取队头元素值
ELEM_TYPE Front(struct QueueList *ql)
{//0.传入的指针参数断言assert(ql!=NULL);if(IsEmpty(ql)){exit(1);}return ql->front->data;
}

 

2.7 获取有效元素个数

遍历链表，计数器自增即可，返回计数器的值

//有效数据节点个数
int Get_length(struct QueueList *ql)
{//0.传入的指针参数断言assert(ql!=NULL);struct QNode * p = ql->front;int count = 0;for(; p!=NULL; p=p->next){count++;}return count;
}

2.8  判空

空链表/空的循环队列，它的头结点的两个指针域均为NULL，用其中一个作为判断条件即可！

//判空
bool IsEmpty(struct QueueList *ql)
{//0.传入的指针参数断言assert(ql!=NULL);return ql->front == NULL;//return ql->rear == NULL;}

 

2.9 打印

只需要定义一个临时结点类型指针变量，让它从第一个有效节点开始遍历，只要结点存在就往后遍历，同时打印结构体节点的数据域成员。

//打印
void Show(struct QueueList *ql)
{//0.传入的指针参数断言assert(ql!=NULL);struct QNode * p = ql->front;for(; p!=NULL; p=p->next){printf("%d ", p->data);}printf("\n");}

 

2.10 清空

单链表的清空和销毁是一回事；

//清空
void Clear(struct QueueList *ql)
{//0.传入的指针参数断言assert(ql!=NULL);Destroy(ql);
}

 

2.11 销毁

第二种：不借助头结点，但是需要两个指针变量p和q(双指针思想)。

//销毁
void Destroy(struct QueueList *ql)
{//0.传入的指针参数断言assert(ql!=NULL);struct QNode *p = ql->front;struct QNode *q = NULL;ql->front = ql->rear = NULL;while(p != NULL){q = p->next;free(p);p = q;}
}

 

三、测试

int main()
{struct QueueList head;Init_QueueList(&head);Push(&head, 12);Push(&head, 23);Push(&head, 34);Show(&head);Pop(&head);Pop(&head);Show(&head);Push(&head, 100);Push(&head, 200);Push(&head, 300);Show(&head);printf("length = %d\n", Get_length(&head));int tmp = Front(&head);printf("Front = %d\n", tmp);Destroy(&head);
}

四、总结

      现在，我们可以知道，其实从本质上来讲，链式队列就是重新设计头节点的单链表结构，并且只允许头删和尾插（队尾入队头出）；对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。
       总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

       以上便是我为大家带来的循环队列设计内容，若有不足，望各位大佬在评论区指出，谢谢大家！下一节继续进行链式队列的内容，感兴趣的你可以留下你们的点赞、收藏和关注，这是对我极大的鼓励，我也会更加努力创作更优质的作品。再次感谢大家！