做外贸阿里巴巴有哪些网站徐州百度推广
队列的概念
队列:只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头
一端进另一端出
也就是可以做到，先进先出
队列的使用场景
队列的经典应用就是保持公平性
比如：抽号机
生产者消费者模型，先来先出去，多线程的话就可能涉及到一个锁的概念
广度优先遍历（概念）
直接好友：好友
间接好友：好友的好友
可以采取队列的方式推荐
队列如何实现
数组的无法实现的因为需要一边进一边出，所以一般是单链表实现队列
同时单链表也会更加省空间
队列的实现
创建文件
首先我们需要知道单链表实现队列的时候，我们需要有头节点和尾结点，以及链表的实际的个数，所以我们不能在结构体里面创建那麽多结构体，所以我们采取结构体的嵌套
创建栈的结构
// 链式结构：表示队列 typedef struct QListNode {QDataType _data;struct QListNode* _next; }QNode; // 队列的结构 （因为队列是先进先出，后进后出，也就是和栈是相反的，此时会尾进头出，所以我们需要更新尾部和头部节点） // (把头结点，尾结点，链表的实际的大小放里面，这样不需要每次使用的时候进行循环找尾，我们只需要每次更新尾结点就可以) typedef struct Queue {QNode* _phead;//头节点QNode* _ptail;//尾结点int size; }Queue;这段代码定义了两个结构体，
QNode和Queue，分别用于表示队列中的节点和整个队列。下面是对每个部分的详细解释：
QNode结构体：这个结构体表示队列中的单个节点。
_data：这是QNode结构体中的一个成员变量，用来存储节点中的数据。QDataType是数据类型的别名，它应该在相关的头文件中定义，代表节点存储的数据类型。_next：这是一个指向QNode类型的指针，用来指向同一队列中的下一个节点。如果_next为NULL，表示这是队列中的最后一个节点。
Queue结构体：这个结构体表示整个队列。
_phead：这是一个指向QNode类型的指针，用来指向队列的头节点。队列的头节点是最早被加入的节点，也是下一个将要被移除的节点。_ptail：这是一个指向QNode类型的指针，用来指向队列的尾节点。队列的尾节点是最后被加入的节点，它用于在添加新元素时更新队列。size：这是一个整数类型的变量，用来存储队列中当前的元素数量。在队列的链式表示中，不需要像顺序表示（使用数组）那样进行动态内存分配和缩容。链式结构自然地允许队列的动态增长和缩减，因为每个节点独立维护其后继节点的指针。
队列的基本操作包括：
- 入队（Enqueue）：在队尾添加一个新节点。
- 出队（Dequeue）：移除队头的节点，并返回其数据。
- 查看队头（Peek/Front）：返回队头节点的数据但不移除它。
- 检查队列是否为空（IsEmpty）：检查队列的头节点是否为
NULL。
初始化与销毁队列
// 初始化队列 void QueueInit(Queue* ps) {ps->_phead = NULL;ps->_ptail = NULL;ps->size = 0; } // 销毁队列 void QueueDestroy(Queue* ps) {assert(ps);QNode* cur = ps->_phead;while (cur){//存下下一个节点的地址，不会出现找空的情况QNode* next = cur->_next;free(cur);cur =next;} }
QueueInit函数：
- 这个函数接收一个指向
Queue结构体的指针ps。ps->_phead = NULL;：将队列的头节点指针设置为NULL。这表示队列初始化时是空的，没有任何元素。ps->_ptail = NULL;：将队列的尾节点指针也设置为NULL。由于队列是空的，头尾节点都不存在。ps->size = 0;：设置队列中元素的数量为0。
QueueDestroy函数：
- 这个函数同样接收一个指向
Queue结构体的指针ps。assert(ps);：使用assert宏来确保传入的ps不是NULL。如果ps是NULL，assert将触发断言失败，这有助于避免对空指针的无效操作。QNode* cur = ps->_phead;：声明一个QNode类型的指针cur并初始化为队列的头节点。while (cur)：使用while循环来遍历队列，直到cur为NULL，即队列中的所有节点都被处理完毕。QNode* next = cur->_next;：在释放当前节点之前，先保存下一个节点的地址，以便在释放当前节点后能够继续遍历队列。free(cur);：使用free函数释放当前节点cur所占用的内存。cur = next;：将cur更新为下一个节点，继续循环直到所有节点都被释放。- 循环结束后，队列中的所有节点都被释放，此时队列被销毁。
队尾入队列
// 队尾入队列 void QueuePush(Queue* ps, QDataType x) {QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QueuePush:newnode:error:");exit(1);}//把需要插入的数值插入到节点里面newnode->_next = NULL;newnode->_data = x;// ps->_phead == ps->_ptail 的结果确实是 true，这表明队列中只有一个元素（头尾相接）。// 但是，通常情况下，我们不会使用 ps->_phead == ps->_ptail // 来检查队列中是否只有一个元素。相反，我们通常会使用 ps->size == 1 或者 ps->_phead != NULL && ps->_ptail != NULL // 来检查队列中是否只有一个元素。//插入节点 第一个节点,这里的判断是不能写成ps->_phead ==ps->_ptail；因为都是空指针不能进行比较//ps->_phead == NULLif (ps->size == 0){ps->_phead = ps->_ptail = newnode;}else{//尾插节点ps->_ptail->_next = newnode;ps->_ptail= newnode;}ps->size++; }
这段代码定义了一个名为
QueuePush的函数，用于在队列的尾部添加一个新的元素。
void QueuePush(Queue* ps, QDataType x)：函数定义开始，QueuePush接收一个指向Queue结构体的指针ps和一个要入队的新数据x。
QNode* newnode = (QNode*)malloc(sizeof(QNode));：使用malloc函数为新节点分配内存。newnode是指向新分配内存的指针。
if (newnode == NULL)：检查malloc是否成功分配了内存。如果newnode是NULL，表示内存分配失败。
perror("QueuePush:newnode:error:");：如果内存分配失败，使用perror函数输出错误信息。
exit(1);：如果内存分配失败，调用exit函数以非零状态码退出程序。
newnode->_next = NULL;：将新节点的_next指针设置为NULL。这是新节点的尾部标识，表示在新节点之后没有更多的节点。
newnode->_data = x;：将新数据x存储在新节点的_data成员中。
if (ps->size == 0)：检查队列是否为空（即队列中的元素数量为0）。
ps->_phead = ps->_ptail = newnode;：如果是空队列，那么新节点同时是头节点和尾节点。因此，将头节点和尾节点指针都指向newnode。
else：如果队列不是空的，执行以下操作：
ps->_ptail->_next = newnode;：将当前尾节点的_next指针指向新节点，从而将新节点添加到队列的末尾。ps->_ptail = newnode;：更新尾节点指针，使其指向新节点。
ps->size++;：队列中元素的数量增加1。这段代码实现了队列的尾部入队操作。它首先检查队列是否为空，然后相应地将新节点添加到队列的末尾，并更新尾节点指针和队列的元素数量。如果内存分配失败，程序将输出错误信息并退出。
队头出队列
// 队头出队列 void QueuePop(Queue* ps) {assert(ps && ps->size);// 改变头结点ps->_phead = ps->_phead->_next;ps->size--; }
这段代码定义了一个名为
QueuePop的函数，其目的是从队列头部移除一个元素。
#include"Queue.h"：这行代码应该位于文件的顶部，用于引入包含Queue结构体和QNode结构体定义以及QDataType类型定义的头文件。
void QueuePop(Queue* ps)：函数定义开始，QueuePop接收一个指向Queue结构体的指针ps作为参数。
assert(ps && ps->size);：assert是一个宏，用于在运行时测试一个条件是否为真。如果条件为假，则assert将产生一个断言失败，通常会导致程序异常终止。在这里，它用于确保传入的队列指针ps不是NULL，并且队列中至少有一个元素（即ps->size大于0）。
ps->_phead = ps->_phead->_next;：这行代码将队列的头节点指针_phead更新为指向下一个节点，从而移除当前队列头部的节点。由于队列是先进先出（FIFO）的数据结构，队头节点是将要被移除的节点。
ps->size--;：队列中元素的数量减少1。这段代码实现了队列的头部出队操作。它首先通过
assert检查队列是否非空，然后将头节点指针移动到下一个节点，以此出队操作，最后更新队列的元素数量。
获取队列头部元素
// 获取队列头部元素 QDataType QueueFront(Queue* ps) {assert(ps && ps->size);return ps->_phead->_data; }
QueueFront函数：
- 这个函数接收一个指向
Queue结构体的指针ps。assert(ps && ps->size);：使用assert宏确保传入的队列指针ps不是NULL，并且队列中至少有一个元素（即ps->size大于0）。return ps->_phead->_data;：返回队列头部节点的_data成员。由于队列是先进先出（FIFO）的数据结构，队头节点的_data成员包含了最早被加入的元素的值。
获取队列队尾元素
// 获取队列队尾元素 QDataType QueueBack(Queue* ps) {assert(ps && ps->size);return ps->_ptail->_data; }
QueueBack函数：
- 这个函数同样接收一个指向
Queue结构体的指针ps。assert(ps && ps->size);：使用assert宏确保传入的队列指针ps不是NULL，并且队列中至少有一个元素。return ps->_ptail->_data;：返回队列尾部节点的_data成员。在链式队列中，尾部节点是最后一个被加入的节点，其_data成员包含了最近一个被加入的元素的值。
获取队列中有效元素个数
// 获取队列中有效元素个数 int QueueSize(Queue* ps) {return ps->size; }
QueueSize函数：
- 这个函数接收一个指向
Queue结构体的指针ps。return ps->size;：返回队列中有效元素的个数，即size成员的值。
检测队列是否为空，如果为空返回非零结果，如果非空返回0
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* ps) {assert(ps);return ps->size == 0; }
QueueEmpty函数：
- 这个函数接收一个指向
Queue结构体的指针ps。assert(ps);：使用assert宏确保传入的队列指针ps不是NULL。return ps->size == 0;：检查队列是否为空。如果size成员的值等于0，则表示队列为空，函数返回非零值（在C语言中，非零值被视为“真”），否则返回0（“假”）
队列代码的总结
Queue.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int QDataType; // 链式结构：表示队列 typedef struct QListNode {QDataType _data;struct QListNode* _next; }QNode; // 队列的结构 （因为队列是先进先出，后进后出，也就是和栈是相反的，此时会尾进头出，所以我们需要更新尾部和头部节点） // (把头结点，尾结点，链表的实际的大小放里面，这样不需要每次使用的时候进行循环找尾，我们只需要每次更新尾结点就可以) typedef struct Queue {QNode* _phead;//头节点QNode* _ptail;//尾结点int size; }Queue; // 这里采取一级指针进行实现代码逻辑，如果不创建队列的结构，我们就需要采取二级指针 // 初始化队列 void QueueInit(Queue* ps); // 销毁队列 void QueueDestroy(Queue* ps); // 队尾入队列 void QueuePush(Queue* ps, QDataType data); // 队头出队列 void QueuePop(Queue* ps); // 获取队列头部元素 QDataType QueueFront(Queue* ps); // 获取队列队尾元素 QDataType QueueBack(Queue* ps); // 获取队列中有效元素个数 int QueueSize(Queue* ps); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* ps);Queue.c
#include"Queue.h" // 初始化队列 void QueueInit(Queue* ps) {ps->_phead = NULL;ps->_ptail = NULL;ps->size = 0; } // 销毁队列 void QueueDestroy(Queue* ps) {assert(ps);QNode* cur = ps->_phead;while (cur){//存下下一个节点的地址，不会出现找空的情况QNode* next = cur->_next;free(cur);cur =next;} } // 队尾入队列 void QueuePush(Queue* ps, QDataType x) {QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("QueuePush:newnode:error:");exit(1);}//把需要插入的数值插入到节点里面newnode->_next = NULL;newnode->_data = x;// ps->_phead == ps->_ptail 的结果确实是 true，这表明队列中只有一个元素（头尾相接）。// 但是，通常情况下，我们不会使用 ps->_phead == ps->_ptail // 来检查队列中是否只有一个元素。相反，我们通常会使用 ps->size == 1 或者 ps->_phead != NULL && ps->_ptail != NULL // 来检查队列中是否只有一个元素。//插入节点 第一个节点,这里的判断是不能写成ps->_phead ==ps->_ptail；因为都是空指针不能进行比较//ps->_phead == NULLif (ps->size == 0){ps->_phead = ps->_ptail = newnode;}else{//尾插节点ps->_ptail->_next = newnode;ps->_ptail= newnode;}ps->size++; } // 队头出队列 void QueuePop(Queue* ps) {assert(ps && ps->size);// 改变头结点ps->_phead = ps->_phead->_next;ps->size--; } // 获取队列头部元素 QDataType QueueFront(Queue* ps) {assert(ps && ps->size);return ps->_phead->_data; } // 获取队列队尾元素 QDataType QueueBack(Queue* ps) {assert(ps && ps->size);return ps->_ptail->_data; } // 获取队列中有效元素个数 int QueueSize(Queue* ps) {return ps->size; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* ps) {assert(ps);return ps->size == 0; }