文章目录

• 前言
• • • 前情回顾：
• 1. 队列
• • • 1.1 队列的概念及结构
    • 1.2 队列的实现
• 2. 队列的具体实现
• • • 2.1 头文件：（Queue.h）
    • 2.2 函数实现：（Queue.c）
    • 2.3 测试：（Test.c）
• 总结

前言

在学过 “栈” 这个数据结构之后，本篇博客将继续介绍另一个常见的数据结构 ——— “队列”。

前情回顾：

• 栈的基本操作 + OJ练习 （C语言版）

1. 队列

1.1 队列的概念及结构

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

1.2 队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据时要将数组每个元素都移动，时间复杂度为O(N) , 效率会比较低。

链表实现队列：
我们可以设计一个能记录头和尾的单链表，这样无论是“入队”还是“出队”时间复杂度都是O(1) , 效率会比数组队列高。

如图所示：在这里每一次的入队就相当于一次尾插，每一次的出队就相当于一次头删。

2. 队列的具体实现

这里只要有实现单链表的基础，链表实现队列就不会困难。
这里代码就不再详细解读，和单链表实现几乎相同。

有疑惑的小伙伴可以去复习单链表相关的问题，参考博文如下 ：

• 单链表的实现 - 详解 （C语言版）

2.1 头文件：（Queue.h）

#include#include#include#include#include#includetypedef int QDataType;typedef struct QueueNode{QDataType data;struct QueueNode* next;}QNode;//记录头指针和尾指针typedef struct Queue{QNode* head;QNode* tail;}Queue;//队列的初始化void QueueInit(Queue* pq);//队列的销毁void QueueDestroy(Queue* pq);//入队void QueuePush(Queue* pq, QDataType x);//出队void QueuePop(Queue* pq);//判断队列是否为空bool QueueEmpty(Queue* pq);//队列中数据的个数size_t QueueSize(Queue* pq);//队头的数据QDataType QueueFront(Queue* pq);//队尾的数据QDataType QueueBack(Queue* pq);

2.2 函数实现：（Queue.c）

#include"Queue.h"//队列的初始化void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}//队列的销毁void QueueDestroy(Queue* pq){QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}//入队void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("%s\n", strerror(errno));exit(-1);}newnode->data = x;newnode->next = NULL;//尾插 - 用了尾指针就不用找尾了if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}//出队void QueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);//头删 - 只有一种个结点的情况时tail会成野指针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;}}//判断队列是否为空bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL && pq->tail == NULL;}//队列中数据的个数size_t QueueSize(Queue* pq){assert(pq);QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;}//队头的数据QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;}//队尾的数据QDataType QueueBack(Queue* pq){assert(pq);assert(pq->tail);return pq->tail->data;}

2.3 测试：（Test.c）

void QueueTest(){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);}printf("\n\n");}int main(){QueueTest();return 0;}

因为遵循先进先出的规则，所以打印结果如下：

总结

队列的实现很容易，更重要的是队列在题目中的运用，一篇将带来队列和栈有关的OJ题，敬请期待~