目录1.前言2.栈和队列的数据的对比3.队列的实现方法4.队列的相关接口的实现4.1队列结构的定义4.2队列的初始化4.3队列的插入数据入队列4.4队列的删除数据出队列4.5队列的判空4.6队列的队头数据4.7队列的尾数据4.8队列的销毁4.9队列的数据个数1.前言队列是什么跟我们之前的栈又有什么关系呢我们前面所学的栈的数据特点是后进先出而今天我们学的队列的元素是先进先出。我们可以看一个图队列的特点只允许在一段进行数据的插入在另一端进行数据的删除的特殊线性表队列具有先进先出。入队列其中数据的插入叫做队尾出队列数据的删除的一段叫做队头。2.栈和队列的数据的对比对于一组数据1 2 3 4栈进栈1 2 3 4出栈4 3 2 1 (后进先出)队列进队列1 2 3 4 出队列1 2 3 4 先进先出3.队列的实现方法我们在前面的栈实现的方法运用了顺序表的结构是因为它在数据的插入和删除只在一段进行所以用顺序表是最好的办法但是我们在实现队列时我们最好选链表实现因为如果也选了顺序表由于元素一头进一头出数据也会跟着移动会很复杂所以选用链表是比较好的选择。4.队列的相关接口的实现4.1队列结构的定义在这里我需要澄清的是队列只是一个称呼就相当于一个盒子里面放的是由一个一个节点连接在一起的结构但是队列它有头指针和尾指针来指向队列的头和尾。又因为在这里我们对函数的参数需要用到二级指针但是为了避免二级指针的混淆和困扰我们在这里可以将队列的头指针和尾指针用一个结构体包装起来这样我们在函数传参时只需要传队列的地址就可以了。下面我们来定义一下最后的我还是想说前面的二级指针用结构体包装起来的本质是为了好管理、好传参、少出错、下面的代码是在Queue.h头文件中所写#pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h //定义链表的结构 typedef int SLtypedata; typedef struct Queuenode { SLtypedata val; struct Queuenode* next; }Qnode; //这里我们将队列的头指针和尾指针放在一个结构体里面后面我们对函数传参时就变成一级指针 typedef struct Queue { Qnode* phead; Qnode* ptail; int size;//这里我们可以多写一个变量用来后续计算队列中的元素个数 }Queue;相信到这里还有很多读者有所困惑为什么要创建一个结构体存放队列的头指针和尾指针不是说必须用这个办法如果不用这个办法按照以往的写法我们在写函数的参数类型时会是下面的写法void Queuepush(Qnode**pt,SLtypedata x);这里的类型是二级指针类型当传入参数时容易搞混所以我们就用结构体包装具体的用法我们在下面的代码实现进行讲解4.2队列的初始化这个是队列的测试函数test.c文件中这个就是初始化的实现过程我们将队列的头尾指针置为NULLsize的有效个数变成04.3队列的插入数据入队列插入数据是从队尾开始插入在这里我们要分两种情况1、如果队列为NULL直接插入数据2、如果队列有数据直接接在下一个节点代码如下//队列的插入数据 void Queuepush(Queue* pqSLtypedata x);//队列的插入数据 void Queuepush(Queue* pq,SLtypedata x) { assert(pq);//首先保证指向队列的指针不为null保证指向的地址有效 // 插入数据需要申请节点 Qnode * newnode (Queue*)malloc(sizeof(Qnode)); //这里需要的申请的空间进行判断是否成功 if (newnode NULL) { perror(malloc fail); return; } newnode-next NULL; newnode-val x; //对队列的插入数据进行分两种情况 //队列中没有数据 if (pq-size 0) { pq-phead pq-ptail newnode; } //队列中有数据 else { pq-ptail-next newnode; pq-ptail newnode;//将尾指针后移动 } pq-size;//插入数据需要将有效个数 }4.4队列的删除数据出队列出队列就相当于在头指针进行删除我们在这里想一下删除头指针的节点是不是直接让指针往后移动一个单位就可以了void Queuepop(Queue* pq) { assert(pq); //我们要删除数据是不是必须保证队列里面得有数据 assert(pq-size); //我们删除这个数据是不是要将指针指向下一个节点我们先创建一个指针存放下一个节点的地址 Qnode* next pq-phead-next; free(pq-phead); pq-phead next; pq-size--; }我们正常写代码的思维肯定是这样的但是我们再来想一下啊如果这个队列只有一个节点的时候这个代码适用吗此时next指向的是NULL针对于phead这个指针没毛病但是还有ptail这个指针呢此时它会变成一个野指针所以我们要再写一种情况void Queuepop(Queue* pq) { assert(pq); //我们要删除数据是不是必须保证队列里面得有数据 assert(pq-size); if (pq-phead-nextNULL)//一个节点 { free(pq-phead); pq-phead pq-ptail NULL; } else//多个节点 { //我们删除这个数据是不是要将指针指向下一个节点我们先创建一个指针存放下一个节点的地址 Qnode* next pq-phead-next; free(pq-phead); pq-phead next; } pq-size--; }4.5队列的判空队列的判空我们需要借助bool函数布尔如果为空就返回true错误返回false//队列的判空 bool QueueEmpty(Queue* pq);bool QueueEmpty(Queue* pq) { return pq-size 0;//这里的意思是如果这个等式成立返回true错误返回false }4.6队列的队头数据当我们想取出队头的数据还要保证队列里面有数据//队列的队头数据 SLtypedata QueueFront(Queue* pq);//队列的队头数据 SLtypedata QueueFront(Queue* pq) { assert(pq); assert(pq-size); return pq-phead-val;//因为phead指针一直指向队列的第一个数据所以直接返回指针指向的值就可以 }4.7队列的尾数据//队列的队尾数据 SLtypedata Queueback(Queue* pq);//队列的队尾数据 SLtypedata Queueback(Queue* pq) { assert(pq); assert(pq-size); return pq-ptail-val; }4.8队列的销毁由于队列的数据特点是先进先出所以我们每当删除一个数据就让phead指针我们也可以定义一个指针pcur指向phead,这样phead指针不用变用pcur指针操控队列就行//队列的销毁 void Queuedestory(Queue* pq);//队列的销毁 void Queuedestory(Queue* pq) { assert(pq); //定义一个指针指向phead Qnode* pcur pq-phead; while (pcur) { Qnode* next pcur-next; free(pcur); pcur next; } //等所有节点都释放完成之后将队列置空和数据个数置为0 pq-phead pq-ptail NULL; pq-size 0; }4.9队列的数据个数//队列的数据个数 int Queuesize(Queue* pq);//队列的数据个数 int Queuesize(Queue* pq) { assert(pq); return pq-size; }