什么叫阻塞队列（阻塞队列设置的长度）



队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) (一端入一端出)

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

队列的入队顺序和出队顺序是否和栈一样存在一对多的关系？
因为栈是后进先出,假设我们入栈一个数据A，在A入栈后不继续加入其他的数据B C D,那么如果我们进行出栈的话，数据A就会第一个出来



所以栈的入栈顺序和出栈顺序是一对多的情况，举个例子
栈的入栈顺序为A B C D E
则出栈顺序可能为 E D C B A，或者 A B C D E
对于E D C B A这种情况就是当数据全部入栈后，我们按照后进先出的规则，进行出栈，也就是E最后入栈，所以第一个出栈，D是倒数第二个入栈，所以出栈的时候就是第二个…

对于A B C D E这种情况就是当A刚入栈后，我们就让A直接出栈，因为其他的数据B C D E都还没有入栈，所以我们只能让A先出栈，之后再将B入栈，然后B再出栈…
出栈的顺序不止这两种，所以就不一一举例了，总之栈的出栈顺序和入栈顺序是一对多的关系

对于队列而言，因为是先进先出的顺序，所以入和出都只有一种情况，没有一对多的关系

队列也可以数组和链表的结构实现

如果用数组实现的就比较麻烦，因为队列是队尾入，对头出，那么如果用数组去实现队列，我们就要让数组头删，头删的复杂度为O（N）

如果用单链表的话，就很方便，因为是队尾入，队头出，删除数据不像栈一样要尾删，队列只需要让队头的数据删除就可以了，单链表的头删时间复杂度为O（1），并且实现起来要比双向链表要容易些，所以选择用单链表实现队列

单链表实现队列我们可以用带哨兵位的方式，也可以选择不用，带哨兵位需要malloc，最后还需要free掉哨兵位，并且哨兵位在这里的作用不是很大，所以队列的实现我们选择不带哨兵位的方式

实际中我们有时还会使用一种队列叫循环队列，环形队列可以使用数组实现，也可以使用循环链表实现

代码

队列的尾插void QueuePush(Queue*pq, QDataType x);

队列尾插函数如果只传两个参数参数头节点的地址,还有需要插入的数据x,(void QueuePush(QNode* * phead, QDataType x)),那么尾插的时间复杂度就为O（N），这样好像单链表就没什么优势了
如果我们传入三个参数void QueuePush(QNode* * phead, QNode* * ptail, QDataType x)，其中ptail为指向尾节点的地址，虽然这样可以解决问题，但是我们要注意这里的指针全是二级指针，phead是plist指针传入的参数，因为plist是一个一级指针，要更改一级指针我们就需要将传参类型变成二级指针，ptail也是，非常麻烦

结构体封装指针typedef struct Queue

所以我们要创建一个结构体，将两个指针封装起来， 这样我们传入的参数就不用二级指针，只需要修改结构体成员就可以了

总结

如果遇到函数参数需要传入多个二级指针，那么我们可以用结构体将他们封装起来，结构体封装的成员就是二级指针的值，然后通过结构体访问成员将他们修改，并且在传参时我们只需要传入结构体的地址即可

代码

当ptail=NULL的时候就说明没有尾节点，只要队列有一个节点，那么尾节点都不可能为空，尾节点为空说明队列是空的，那么尾插就直接让尾节点=头节点=插入的newnode
如果尾节点不为空，那就直接让尾节点的next=newnode，然后插入newnode后newnode又是新的尾节点，所以让ptail=newnode
最后不要忘记size++

队列的头删void QueuePop(Queue* pq)

头删一般都得考虑两种情况，一种是只有一个节点，另一种就是没有节点

当没有节点时，我们assert断言就可以了

只有一个节点时，在头删后要小心ptail变成野指针，当phead走到下一个节点，发现是空后，如果直接把之前的头节点删除，我们会发现ptail还指向原来头节点的位置，free掉头节点后，ptail就成了野指针


所以需要判断如果phead走到下一个节点为空后，要让ptail赋值成NULL

代码

队列的初始化void QueueInit(Queue* pq)

代码

队列的销毁void QueueDestroy(Queue* pq, QDataType x)

代码

取队尾数据QDataType QueueBack(Queue* pq)

代码

取队头数据QDataType QueueFront(Queue* pq)

代码

判断队列是否为空bool QueueEmpty(Queue* pq)

代码

获得队列的长度int QueueSize(Queue* pq)

代码

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/72568.html