做招聘网站如何宣传,北京环球影城风险等级,ppt模板免费下载 素材小清新,发稿是什么意思创作不易#xff0c;友友们来个三连支持吧#xff01;
一、队列的概念
队列#xff1a;是只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出FIFO(First In First Out)的特点。
入队列#xff1a;进行插入操作… 创作不易友友们来个三连支持吧
一、队列的概念
队列是只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)的特点。
入队列进行插入操作的一端称为队尾
出队列进行删除操作的一端称为队头 二、单链表实现队列 队列可以用数组实现也可以用链表实现但是链表会稍微优势一点因为涉及到出队列的时候是在队列头出的如果是数组实现的话需要把后面所有数据都往前挪一位效率会相对低一点所以以下博主会优先讲解单链表实现队列数组实现队列会在下一篇博客中进行讲解。
2.1 相关结构体的创建 因为使用单链表的方式去实现队列所以我们应该构造一个节点指针结构体
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{QDatatype data;//存储数据struct QueueNode* next;
}QNode; 但是这远远不够因为我们只是使用单链表的方式去实现队列并不代表可以完全照抄单链表的模式由于队列队头出数据和队尾入数据的特性我们需要构造两个节点结构体指针一个指向队列头一个指向队列尾这样我们可以再封装一个队列结构体。
typedef struct Queue
{QNode* phead;//指向队头用于出队头删QNode* ptail;//指向队尾用于入队尾插int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
2.1.1 为什么这里要构造两个结构体构造一个不行吗
写一个其实也是可以的比如
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{QDatatype data;//存储数据struct QueueNode* next*phead*ptailint size
}QNode;
这种写法不仅在使用上有很大的劣势而且不易和单链表区分开来原因如下
1、队列的管理更加严格单链表的管理更加松散。 单链表可以实现尾插、头插、指定位置插入、尾删、头删、指定位置删除……管理上很松散而队列由于其一端进一端出的特点不能随意的去遍历所以我们才会需要存储队列头和队列尾的结构体节点指针方便我们进行入队和出队的操作同时我们需要队列头和队列尾能对所有节点起到一个管理作用即操作队列需要经过队列头或者队列尾的同意严格管理而构造两个结构体就能体现出这种作用相当于用第二个结构体中的phead和ptail去管理第一个结构体中的next和data。在写代码的时候可以体现出来 也就是说pq想指向链表的元素只能通过phead和ptail去指向不能越级一越级就会报错总来来说就像是一级一级去管理链队pq管理phead和ptail而phead和ptail管理data和next
2、方便参数的传递。 调用函数会方便很多比如不构造两个结构体的话那么调用函数就需要传两个参数即phead和ptail但如果有一个结构体Queue将phead和ptail指针封装起来了那么只要传一个参数就可以了通过访问这个参数的成员就可以找到这两个指针了。
3、不需要使用二级指针了 以往我们在单链表的实现中使用的是二级指针因为单链表中的phead就是结构体指针类型而单链表的头删以及头插都需要改变phead所以我们需要传的是该结构体指针的地址也就是需要用二级指针来接受但是在这里我们实现队列时又多封装了一个Queue的结构体虽然我们有些时候也需要改变phead和ptail但是这两个结构体指针都是Quene的成员所以我们只需要取Quene结构体的地址即可只需要一级指针就可以接受了
2、为什么我要在队列结构体里设置一个size不设置可以吗 其实不设置size也是可以的有些书上也没有设置size我设置size也是考虑到2个原因
1、栈有结构体成员top而队列没有
栈中的top其实跟顺序表中的有效数据个数基本上差异不大虽然名字是不一样的但是通过top是可以得到栈的有效数据个数的而队列是没有的。
2、队列管理较为严格不能随便遍历 首先队列并不具备栈那样和size类似的成员并且由于队列只能队头出列队尾入列不能随意去遍历如果要遍历需要边出队列才能边遍历代价比较大所以我们给了一个size帮助我们在入队列和出队列的时候及时修改存储的size成员这样可以方便我们获得队列中有效数据的个数
2.2 初始化队列
void QueueInit(Queue* pq)
{assert(pq);//判断传的是不是空指针pq-phead pq-ptail NULL;pq-size 0;//因为队列不像栈一样有一个top表示栈顶元素的下标//所以如果我们想知道这个队列的有效数据个数就必须遍历队列//由于其先进先出的特性我们默认只能访问到头元素和尾元素//所以必须访问一个头元素就出队列一次这样才能实现遍历//但是这样的代价太大了为了方便我们直接用size
}
2.3 队尾入队列
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);//入队必须从队尾入QNode* newnode (QNode*)malloc(sizeof(QNode));//创建一个新节点if (newnodeNULL)//如果新节点申请失败退出程序{perror(malloc fail);}//新节点创建成功给新节点初始化一下newnode-data x;newnode-next NULL;//开始入队//如果直接尾插的话由于会用到ptail-next,所以得考虑队列为空的情况if (pq-ptail NULL)//如果为空直接把让新节点成为phead和ptail{//按道理来说如果ptail为空phead也应该为空// 但是有可能会因为我们的误操作使得phead不为空这个时候一般是我们写错的问题//所以使用assert来判断一下有问题的话会及时返回错误信息assert(pq-phead NULL);pq-phead pq-ptail newnode;}else//尾插{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
2.3.1 为什么不单独封装一个扩容函数 因为队列并不像链表一样链表的头插、尾插、指定位置插入都需要创建新节点如果设置一个扩容函数的话复用性很高而队列只有在队尾入数据需要创建新节点只会用到一次所以没有必要去封装一个这样的函数。
2.3.2 如何思考边界情况 进行尾插的时候我们先不考虑边界情况去做一遍比如上述代码的else部分就是实现尾插而我们观察发现尾插的过程中需要用到ptail的成员next的指针所以ptail必须不能是NULL因此要分开讨论ptail为NULL的情况
2.3.3 为什么assert(pq-phead NULL) 因为我们考虑ptail为空的时候不能用成员next但是因为按道理来说一般情况下ptail如果是NULLphead肯定也是NULL没必要单独搞这一出但是这里也有可能我们前面操作有失误phead不是NULL这边的assert就是为了避免我们代码写错的情况万一写错了可以帮我们更快找出bug
2.4 队头出队列
void QueuePop(Queue* pq)
{assert(pq);//如果队列为空没有删除的必要assert(!QueueEmpty(pq));//队列中的出队列相当于链表的头删//如果直接头删那么如果队列只有一个有效数据的话那么我们将phead的空间释放掉但是没有将ptail给置空//这样会导致ptail成为一个野指针所以我们需要考虑只有一个节点多个节点的情况if (pq-phead-next NULL)//一个节点的情况,直接将这个节点释放并置空即可{free(pq-phead);pq-phead pq-ptail NULL;//置空防止野指针}else//多个节点的情况直接头删{QNode* next pq-phead-next;//临时指针记住下一个节点free(pq-phead);pq-phead next;//让下一个节点成为新的头}pq-size--;
}2.4.1 如何思考边界情况 进行头删的时候我们先不考虑边界情况去做一遍比如上述代码的else部分就是实现头删其实一开始发现不了什么问题因为我们assert已经判断了此时链表肯定不是空而有一个节点的时候phead的next指向NULL也很合理不会有问题但是我们要考虑到虽然我们释放了phead的空间但是我们只给phead置NULL而没有给ptail置NULL这样ptail就变成一个野指针了
2.5 获取队列头部元素
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队列如果为空则不可能找得到队列头元素//队列不为空的时候直接返回phead指向的数据return pq-phead-data;
}
2.6 获取队列队尾元素
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队列如果为空则不可能找得到队尾元素//队列不为空的时候直接返回ptail指向的数据return pq-ptail-data;
}
2.7 获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
} 在这个函数可以充分体现处我们构造一个size成员的好处代码量很小如果我们用size成员的话那么需要遍历队列会很麻烦。
2.8 检测队列是否为空
bool QueueEmpty(Queue* pq)//链表为空的情况可以根据容量也可以根据ptailNULLpheadNULL
{assert(pq);return pq-ptail NULL pq-phead NULL;//也可以pq-size0
} 因为我们设置了一个size成员其实用size成员也是可以的通过判断是否等于0的返回值真假来决定是否是空这边两张写法没啥区别只要前面的没有出错就行。
2.9 销毁队列
void QueueDestory(Queue* pq)
{assert(pq);//判断传的是不是空指针//要逐个节点释放QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
} 和单链表差不多逐个节点释放就行。
2.10 遍历打印队列
其实严格意义来说队列是不适合被打印的因为打印需要遍历队列而由于队列一端进一端出的特点要遍历里面的元素就需要一边在队列头获取元素一般在队列头出队列知道队列为空才能访问完所有数据而且这样做会导致队列的数据丢失没有复用性因此也不适合封装这个函数这里只是告诉大家别忘记了队列访问的特点不要跟单链表一样队列的管理是很严格的。一般我们只会在main函数中测试一下
#includeQueue.h
int main()
{Queue q;QueueInit(q);//初始化QueuePush(q, 1);//入队列QueuePush(q, 2);//入队列QueuePush(q, 3);//入队列QueuePush(q, 4);//入队列while (!QueueEmpty(q))//遍历打印队列{printf(%d , QueueFront(q));QueuePop(q);}
}
三、链队列实现的全部代码
3.1 Queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{QDatatype data;//存储数据struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;//指向队头用于出队头删QNode* ptail;//指向队尾用于入队尾插int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
void QueueInit(Queue* pq);//队列的初始化
void QueuePush(Queue* pq, QDatatype x);//队列的入队尾插
void QueuePop(Queue* pq);//队列的出队(头删)
QDatatype QueueFront(Queue* pq);//获取队列头部元素
QDatatype QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueDestory(Queue* pq);//队列的销毁
3.2 Queue.c
#includeQueue.hvoid QueueInit(Queue* pq)
{assert(pq);//判断传的是不是空指针pq-phead pq-ptail NULL;pq-size 0;//因为队列不像栈一样有一个top表示栈顶元素的下标//所以如果我们想知道这个队列的有效数据个数就必须遍历队列//由于其先进先出的特性我们默认只能访问到头元素和尾元素//所以必须访问一个头元素就出队列一次这样才能实现遍历//但是这样的代价太大了为了方便我们直接用size
}
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);//入队必须从队尾入QNode* newnode (QNode*)malloc(sizeof(QNode));//创建一个新节点if (newnodeNULL)//如果新节点申请失败退出程序{perror(malloc fail);}//新节点创建成功给新节点初始化一下newnode-data x;newnode-next NULL;//开始入队//如果直接尾插的话由于会用到ptail-next,所以得考虑队列为空的情况if (pq-ptail NULL)//如果为空直接把让新节点成为phead和ptail{//按道理来说如果ptail为空phead也应该为空// 但是有可能会因为我们的误操作使得phead不为空这个时候一般是我们写错的问题//所以使用assert来判断一下有问题的话会及时返回错误信息assert(pq-phead NULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);//如果队列为空没有删除的必要assert(!QueueEmpty(pq));//队列中的出队列相当于链表的头删//如果直接头删那么如果队列只有一个有效数据的话那么我们将phead的空间释放掉但是没有将ptail给置空//这样会导致ptail成为一个野指针所以我们需要考虑只有一个节点多个节点的情况if (pq-phead-next NULL)//一个节点的情况,直接将这个节点释放并置空即可{free(pq-phead);pq-phead pq-ptail NULL;//置空防止野指针}else//多个节点的情况直接头删{QNode* next pq-phead-next;//临时指针记住下一个节点free(pq-phead);pq-phead next;//让下一个节点成为新的头}pq-size--;
}QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队列如果为空则不可能找得到队列头元素//队列不为空的时候直接返回phead指向的数据return pq-phead-data;
}QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队列如果为空则不可能找得到队尾元素//队列不为空的时候直接返回ptail指向的数据return pq-ptail-data;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)//链表为空的情况可以根据容量也可以根据ptailNULLpheadNULL
{assert(pq);return pq-ptail NULL pq-phead NULL;
}void QueueDestory(Queue* pq)
{assert(pq);//判断传的是不是空指针//要逐个节点释放QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
}3.3 test.c (测试)
#includeQueue.h
int main()
{Queue q;QueueInit(q);//初始化QueuePush(q, 1);//入队列QueuePush(q, 2);//入队列QueuePush(q, 3);//入队列QueuePush(q, 4);//入队列while (!QueueEmpty(q))//遍历打印队列{printf(%d , QueueFront(q));QueuePop(q);}
}
四、队列在实际生活中的作用举例——抽号机 在生活中我们经常需要排队比如在饭堂打饭时排在前面的因为来得早可以先打到饭而排在后面的因为来得晚就得后打到饭这符合我们追求公平的原则先到先得这本身也是维持秩序的一种方式。 排队和队列是一样的原则先到先得对应的就是队列的先进先出但是哪怕大家知道这样的原则但也有可能有人去钻空子比如
1、打饭的时候帮室友打饭或者帮室友女朋友占位置。
2、趁着人多的时候找一个地方偷偷插队
3、或者一些比较恶霸型的可能直接插队也没人敢说
4、再或者你并不是有意插队只不过由于顾客太多商家忘记了顺序误把你排在了别人前面
所以商家为了控制这个局面使用了抽号机
比如说第一个同学来了通过抽号机拿到了1号那么领取物品的时候商家就按照这个序号的优先级来给予服务避免了一些人钻空子的可能同时为了避免有的人帮别人占位置强制要求刷脸抽号。
抽号机的本质就是队列比如来了一个顾客抽号机内部就入队列一次服务完了这个顾客抽号机内部就出队列一次而如果我们还想让顾客知道自己前面有多少人就需要有一个size来统计目前有效数据的个数。
当我们有多个窗口去服务的时候我们也可以通过抽号机这个平台来叫号避免现场混乱比如说目前下一个轮到3号顾客了那么A窗口一旦空出来就会让3号顾客过去而如果B窗口接着空出来了就喊4号顾客过去这使得本来混乱的排队场面变得有序了顾客不需要排在拥挤的收货台前抽完号码等着叫号就行了如果你觉得你前面的人有点多也可以自己转身就走。
