-
数据结构与算法(C语言版)P6---队列
1、队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除操作的特殊线性表，队列具有__先进先出__FIFO（First In First Out）
入队列：进行插入操作的一端称为__队尾__。
出队列：进行删除操作的一端称为__对头__。
数据存放：现在有数据：A、B、C、D要存放，那存放数据顺序就是一次存入，并且存放的位置如下：
1.1、队列的实现概念
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果数组的结构，出队列在数组头上出数据，效率会比较低。
因为数组队列在处一个数据后们需要整体挪动数据向前，所以麻烦，这里不如链表。而链表在出数据是，把节点释放，然后将phead在指向要出数据的后一个数据即可，并且我们也记录个尾节点ptail，用来链接放在队列中新数据即可。
所以队列的实现主要以链表队列为主要。2、链队列的实现
队列主要有以下接口函数
- 初始化（QueueInit）
- 销毁（QueueDestroy）
- 扩容（BuyQueueNode）
- 队尾插入数据（QueuePush）
- 对头删除数据（QueuePop）
- 取队尾数据（QueueBack）
- 取对头数据（QueueFront）
- 统计队列中数据个数（QueueSize）
- 判断队列是否为空（QueueEmpty）
2.1、定义结构体
这里需要重点说明这个结构体的定义。
1、首先我们定义一个QueueNode结构体，这个结构体就是动态扩容的结点。里面有一个Next指针域，还有一个data数据域。如下：typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode;- 1
- 2
- 3
- 4
- 5
2、然后是重点来了：这里我们需要创建两个QueueNode*类型的指针：head，tail。分别用来队列的头结点和尾节点。如下：
typedef struct Queue { struct QueueNode* head; struct QueueNode* tail; }Queue;- 1
- 2
- 3
- 4
- 5
然后整体结构体定义就如下：
#pragma once #include#include #include #include typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* Next; }QNode; typedef struct Queue { struct QueueNode* head; struct QueueNode* tail; }Queue; - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
2.2、队列初始化
将头结点和尾节点置为NULL即可。
//队列初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.3、销毁
依次遍历结点进行销毁
//销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->Next; free(cur); cur = next; } pq->head = pq->tail = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.4、扩容
//扩容 QNode* BuyQueueNode(QDataType x) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->Next = NULL; return newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.5、队尾插入数据
队列在队尾入数据，因为我们提前设置了尾结点(tail)，那操作就容易了，先将tail的Next域指向新节点的地址，然后再将新节点的地址赋值给tail，便于下次再尾插。
但是由于我们没创建哨兵位，所以在进行结点的插入和删除时，需要考虑边界问题。
那这里，特殊情况就是，如果是第一次插入数据，也就是当pq->head == NULL时，我们可以直接将新节点的地址赋值给头结点和尾节点。//对尾插入数据 void QueuePush(Queue* pq, QDataType x) { QNode* newnode = BuyQueueNode(x); if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->Next = newnode; pq->tail = newnode; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
2.6、对头删除数据
核心思想：先保存头结点的后驱结点的地址，然后释放头结点，然后将先前保存头结点的后驱结点的地址赋值给头结点。
特殊情况：当pq->head == NULL时，也就意味着整个队列为空了，所以我们还需要将pq->tail = NULL。//队头删除数据 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QNode* next = pq->head->Next; free(pq->head); pq->head = next; if (pq->head == NULL) { pq->tail = NULL; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.7、取队尾数据
//取队尾数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.8、取对头数据
//取对头数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.8、统计队列元素个数
使用个计数器，依次遍历队列中的结点，来统计队列元素个数。
//统计队列元素个数 int QueueSize(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); int count = 0; QNode* cur = pq->head; while (cur) { count++; cur = cur->Next; } return count; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
2.10、判断队列是否为空
//判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }- 1
- 2
- 3
- 4
- 5
- 6
2.11、main函数测试程序
下面测试程序功能：遍历输出队列中的数据。
#include "queue.h" int main() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); QueuePush(&q, 6); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); QueueDestroy(&q); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
输出：
3、全代码展示
这里使用三个文件：
- queue.h：用于结构体、各种函数接口的声明
- queue.c：用于各种函数接口的定义。
- test.c：用于创建链表，实现链表。
3.1、queue.h
#pragma once #include#include #include #include typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* Next; }QNode; typedef struct Queue { struct QueueNode* head; struct QueueNode* tail; }Queue; //队列初始化 void QueueInit(Queue* pq); //销毁 void QueueDestroy(Queue* pq); //扩容 QNode* BuyQueueNode(QDataType x); //对尾插入数据 void QueuePush(Queue* pq, QDataType x); //队头删除数据 void QueuePop(Queue* pq); //取队尾数据 QDataType QueueBack(Queue* pq); //取对头数据 QDataType QueueFront(Queue* pq); //统计队列元素个数 int QueueSize(Queue* pq); //判断队列是否为空 bool QueueEmpty(Queue* pq); - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
3.2、queue.c
#include "queue.h" //队列初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } //销毁 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->Next; free(cur); cur = next; } pq->head = pq->tail = NULL; } //扩容 QNode* BuyQueueNode(QDataType x) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->Next = NULL; return newnode; } //对尾插入数据 void QueuePush(Queue* pq, QDataType x) { QNode* newnode = BuyQueueNode(x); if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->Next = newnode; pq->tail = newnode; } } //队头删除数据 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); QNode* next = pq->head->Next; free(pq->head); pq->head = next; if (pq->head == NULL) { pq->tail = NULL; } } //取队尾数据 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } //取对头数据 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } //统计队列元素个数 int QueueSize(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); int count = 0; QNode* cur = pq->head; while (cur) { count++; cur = cur->Next; } return count; } //判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
3.3、test.c
#include "queue.h" int main() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); QueuePush(&q, 6); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); QueueDestroy(&q); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
-
相关阅读:
社区投稿| 以安全视角，深度剖析 Sui Staking 与 LSD
【苏大c++第二次考试模拟】
【论文阅读】（2017）The late acceptance Hill-Climbing heuristic
【人工智能】确定型推理
vcf 文件如何修改染色体修改样本名称提取样本
如何将OFD文件转成WORD？每天免费用
通过STM32Cube配置完成基于I2C协议的AHT20温湿度传感器的数据采集
Vue样式属性绑定
【Vue】vuex mapState和mapGetters
简单2D几何求交点
- 原文地址：https://blog.csdn.net/m0_57776598/article/details/133093741
