数据结构中的队列（C语言）

一、队列

1、队列的概念及结构

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

入队列：进行插入操作的一端称为队尾。

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

如图所示：

1.2队列的应用：

1.任务调度：多个任务按照顺序排队等待执行。

2.广度优先搜索（BFS）：在图或树的遍历中，按层次遍历节点。

3.缓存管理：缓存中的数据按照访问顺序排列，最先进入的数据最先被替换。

4.算法设计：某些算法的设计与队列密切相关，如哈夫曼编码、循环队列等。

1.3队列存在的优缺点：

优点：

1、先进先出(FIFO)：队列保持元素的插入顺序，对线插入的元素最先被处理。

2、简单高效：队列的基本操作包括入队和出队，它们的时间复杂度都是O(1)，无论队列的大小如何，操作的时间复杂度都是固定的。

3、应用广泛：队列在很多算法和实际应用场景中都有着广泛的应用，如任务调度、缓存管理、广度优先搜索。

缺点：

1、随机访问困难：队列只允许在队头删除元素，在队尾插入元素，不支持随机访问。如果需要在队列的其他位置插入或删除数据，运行效率较低。

2、队列大小的限制：使用数组实现的队列在创建时需要指定最大容量，因此队列中的元素有限。如果队列已满，则无法插入新的数据。

3、存储空间浪费：如果队列中实际的元素个数远小于最大容量，那么可能造成存储空间的浪费，因为队列的空间是固定的。

1.4队列的基本结构

本文队列采用链式存储进行讲解，而非数组存储。

1.4.1链式存储的原因

基于队列先进先出的特点，队列先进的数据从队尾进来，接着从队头出去，链式存储利用指针将一个一个的元素连接起来。插入数据，则用指针在队尾链接数据；删除数据，则释放掉队头元素。

相较于链式存储，数组存储在队尾插入数据简单（时间复杂度为O(1)），但由于删除数据需要在队头进行，还需把后面的数据通通往前移一位，由此以来，时间复杂度就将变为O(N)，效率变低，所以不推荐使用。

1.4.2存储结构

typedef int QDatatype;   //暂定为整数类型typedef struct QueueNode{    QDatatype val;      //存放数据    struct QueueNode* next; //存放链}QNode;

但仅仅这些还不够，我们还要标记队列的队头和队尾，以方便插入和删除。这样一来，我们队列插入和删除操作的时间复杂度就变为了O(1)。

typedef struct Queue{    QNode* head; //标记队头指针，用于删除数据    QNode* tail; //标记队尾指针，用于插入数据    int size;    //标记队列中有效元素个数}Queue; 

ps:这是一种重要的算法思维（以空间换时间），提高算法效率。

1.5队列的基本操作

• QueInit(&pq);   初始化一个空队列
• QuePush(&pq, x);   往队列新插入一个数据，并将其放在队尾
• QuePop(&pq);   删除队列中队头的元素，并释放
• QueFront(&pq);   获取处在队列队头的元素数据
• QueBack(&pq);   获取处在队列队尾的元素数据
• QueEmpty(&pq);   判断队列是否为空
• QueSize(&pq);   返回获取队列中元素的个数
• QueDestroy(&pq);   销毁队列，并释放pq所占用的存储空间

  2、队列的实现算法

  1.初始化

  void QueInit(Queue* pq){    pq->head = NULL;     pq->tail = NULL; //将队列的头尾指针置为空    pq->size = 0;    //队列长度初始化为零}

  2.入队列

  void QuePush(Queue* pq, QDatatype x){    //判空    assert(pq);    QNode* newnode = (QNode*)malloc(sizeof(QNode));    //检验是否创建成功    if(newnode == NULL)    {        perror("malloc fail");        return;    }    newnode->val = x;  //将x值赋给newnode    newnode->next = NULL;    //无哨兵位，则需要检验队列中是否为空    //若不为空    if(pq->tail == NULL)    {        pq->tail->next = newnode;//将元素放在队尾        pq->tail = newnode;      //将队尾变作新插入的元素    }    //若为空    else    {        pq->head = pq->tail = newnode;    }    pq->size++;}

  3.出队列

  void QuePop(Queue* pq){    assert(pq);    //当队列中没有节点时，就会强制返回    assert(pq->head != NULL);        QNode* cur = pq->head;        //这里需要分情况讨论，若只有一个节点，tail和head会指向同一个节点    //若有多个节点，tail和head则会分别只想不同的节点，所以需要分开讨论    //若只有一个节点    if(pq->tail->next == NULL)    {        free(pq->tail);        pq->tail = pq->head = NULL;    }    //若有多个节点    else    {        QNode* next = cur->next;//next指向cur的下一个节点，以方便下次删除找到队头        free(pq->head);        cur = next;    }    pq->size--;}

  出队列需要注意的几点：

  （1）当队列中有元素时才可以进行删除操作，所以要进行判空(assert(pq->head != NULL))

  （2）当队列中只有一个节点时，如果只把tail释放掉是不对的，因为tail和head指向同一个节点，释放掉tail，head就变成了野指针，导致严重错误

  （3）当队列中有多个节点，head和tail指向不同的节点，才可以正常删除数据

  只有一个节点的情况：

  有多个节点的情况：

  4.获取队头数据

  QDatatype QueFront(Queue* pq){assert(pq);assert(pq->head != NULL);return pq->head->val;//直接返回队头节点的数据值}

  5.获取队尾数据

  QDatatype QueBack(Queue* pq){assert(pq);assert(pq->head != NULL);return pq->tail->val; //获取队尾数据值}

  6.判空操作

  bool QueEmpty(Queue* pq){assert(pq);        //判断size是否为空来返回，若为空，则返回true；若非空，则返回falsereturn pq->size == 0;}

  7.获取队列节点个数

  int QueSize(Queue* pq){assert(pq);    //在此不需要循环队列，直接返回，因为size标记了队列中的节点个数return pq->size;}

  不需要循环队列，因此时间复杂度为O(1)，如果遍历队列链表，时间复杂度为O(N)，相比之下，相当于优化了结构的性能

  8.销毁队列

  void QueDestroy(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* Next = cur->next; //Next用于迭代队头free(cur);cur = Next;}pq->head = pq->tail = NULL;//指针都置为空pq->size = 0;}

  3、源码呈现

  3.1Queue.h

  #include#include#include#includetypedef int QDatatype;typedef struct QueueNode{QDatatype val;struct QueueNode* next;}QNode;typedef struct Queue{QNode* head;QNode* tail;int size;}Queue;//初始化void QueInit(Queue* pq);//销毁void QueDestroy(Queue* pq);void QuePush(Queue* pq, QDatatype x);void QuePop(Queue* pq);bool QueEmpty(Queue* pq);int QueSize(Queue* pq);QDatatype QueFront(Queue* pq);QDatatype QueBack(Queue* pq);

  3.2Queue.c

  #include"Queue.h"void QueInit(Queue* pq){assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;}void QueDestroy(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* Next = cur->next;free(cur);cur = Next;}pq->head = pq->tail = NULL;pq->size = 0;}//入队列void QuePush(Queue* pq, QDatatype x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;//不带哨兵位，需要进行检验//如果pq->tail不为空if (pq->tail){pq->tail->next = newnode;pq->tail = newnode;}//如果为空else{pq->head = pq->tail = newnode;}pq->size++;}//出队列void QuePop(Queue* pq){assert(pq);//零个节点assert(pq->head != NULL);//一个节点if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}//多个节点else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;}QDatatype QueFront(Queue* pq){assert(pq);assert(pq->head != NULL);return pq->head->val;}QDatatype QueBack(Queue* pq){assert(pq);assert(pq->head != NULL);return pq->tail->val;}int QueSize(Queue* pq){assert(pq);return pq->size;}bool QueEmpty(Queue* pq){assert(pq);return pq->size == 0;}

  3.3Test.c

  #include"Queue.h"int main(){Queue q;QueInit(&q);QuePush(&q, 1);QuePush(&q, 2);QuePush(&q, 3);QuePush(&q, 4);//printf("%d ", QueFront(&q));while (!QueEmpty(&q)){printf("%d ", QueFront(&q));QuePop(&q);}QueDestroy(&q);return 0;}

  码字不易，来个一键三连呗~~