-
数据结构——队列
上一期我们认识了栈，这一期我们来看看队列是如何实现的
队列的概念以及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有
先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
用图片展示：
队列的实现
我们先来看一张图片：
队列里面的每一个数据都是结构体类型的，其中front（head）结构体指针指向队头，rear（tail）结构体指针指向队尾。
这里用不用带哨兵位是头节点都可以，我这里没有用哨兵头节点，大家像用头节点可以自己加上
1、结构体的定义
typedef int DataType; typedef struct QueueNode//单链表的形式 { DataType data;//数值 struct QueueNode* next;//指向下一个节点的指针 }QN;//重命名为QN typedef struct Queue//定义一个结构体用来存放两个结构体指针，这样修改外面指针（也就是改变head和tail指向节点）的时候，不用传二级指针和接收改变指针的返回值 { QN* head;//指向队列的对头 QN* tail;//指向队列的对尾 int size;//记录队列数据个数，用一个计数器可以提高计算效率 }Queue;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
2、函数接口声明
队列与栈的区别在于：
1、栈是：后进先出；队列是：先进先出
2、栈只能取出栈顶数据，队列可以取出队头数据和队尾数据void QueueInit(Queue* ps);//初始化 void QueueDestroy(Queue* ps);//释放空间 bool QueueEmpty(Queue* ps);//判断队列是否为空 void QueuePush(Queue* ps,DataType x);//入队列 void QueuePop(Queue* ps);//出队列 DataType QueueFront(Queue* ps);//队头数据 DataType QueueBack(Queue* ps);//队尾数据 int QueueSize(Queue* ps);//队列剩余数据个数- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
3、初始化
void QueueInit(Queue* ps)//初始化 { assert(ps); ps->head = ps->tail = NULL;//两个指针都指向空 ps->size = 0;//此时队列没有数据 }- 1
- 2
- 3
- 4
- 5
- 6
4、销毁空间
void QueueDestroy(Queue* ps)//释放空间 { assert(ps); QN* cur = ps->head;//cur等于头指针，ps是结构体指针，结构体指针指向头指针 while (cur)//如果头指针不为空，就进入循环释放空间 { QN* del = cur;//保留头指针的节点 cur = cur->next;//头指针向后移动 free(del);//释放头指针移动前的节点 } ps->head = ps->tail = NULL;//释放完之后，头尾指针指向NULL ps->size = 0;//数据个数清0 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
5、入队列
与栈同理，只有入数据才就行扩容，所以扩容不用写一个函数
void QueuePush(Queue* ps, DataType x)//入队列 { assert(ps); QN* newnode = (QN*)malloc(sizeof(QN));//扩容一个新的节点出来 if (newnode == NULL) { perror("malloc fail\n"); exit(-1); } else { newnode->data = x;//对新节点就行初始化操作 newnode->next = NULL;//这里将新节点的next置空，不用考虑插入节点后的next指向了 } if (ps->tail == NULL)//第一次入队列数据head和tail都是指向NULL的，直接让head和tail都指向第一个新节点 { ps->head = ps->tail = newnode; } else { ps->tail->next = newnode;//将扩容节点插在tail后面 ps->tail = newnode;//让tail指向到插入的节点处 } ++ps->size;//插入size就加1，记录此时队列节点的个数 }- 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
6、出队列
void QueuePop(Queue* ps)//出队列（队列出数据就相当于单链表的头删） { assert(ps); assert(!QueueEmpty(ps));//如果队列没有节点了，断言生效 if(ps->head->next==NULL)//如果队列只剩下一个节点了，直接释放该节点，然后将头尾指针置空 { free(ps->head); ps->head = ps->tail = NULL; } else { QN* cur = ps->head;//保存当前头节点 ps->head = ps->head->next;//让头指针指向下一个节点 free(cur);//释放之前的头节点 cur = NULL; } --ps->size;//出一个数据size就减1 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
7、判断队列是否为空
bool QueueEmpty(Queue* ps)//判断队列是否为空 { assert(ps); return ps->head == NULL && ps->tail == NULL;//头尾指针都指向NULL，队列才为空 }- 1
- 2
- 3
- 4
- 5
8、取出队头数据
这个很简单，下面的取出队尾数据也是
DataType QueueFront(Queue* ps)//队头数据 { assert(ps); assert(!QueueEmpty(ps)); return ps->head->data; }- 1
- 2
- 3
- 4
- 5
- 6
9、取出队尾数据
DataType QueueBack(Queue* ps)//队尾数据 { assert(ps); assert(!QueueEmpty(ps)); return ps->tail->data; }- 1
- 2
- 3
- 4
- 5
- 6
10、队列剩余数据个数
int QueueSize(Queue* ps)//队列剩余数据个数 { assert(ps); return ps->size; /*QN* cur = ps->head;//不使用size的方法，遍历队列，如果偶尔查看数据个数还好，经常使用效率太慢了 int capacity = 0; while (cur) { ++capacity; cur = cur->next; } return capacity;*/ }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
全部代码
Queue.h
#pragma once #include#include #include #include typedef int DataType; typedef struct QueueNode//单链表的形式 { DataType data;//数值 struct QueueNode* next;//指向下一个节点的指针 }QN;//重命名为QN typedef struct Queue//定义一个结构体用来存放两个结构体指针 //这样修改外面指针（也就是改变head和tail指向节点）的时候，不用传二级指针和接收改变指针的返回值 { QN* head;//指向队列的对头 QN* tail;//指向队列的对尾 int size;//记录队列数据个数，用一个计数器可以提高计算效率 }Queue; void QueueInit(Queue* ps);//初始化 void QueueDestroy(Queue* ps);//释放空间 bool QueueEmpty(Queue* ps);//判断队列是否为空 void QueuePush(Queue* ps,DataType x);//入队列 void QueuePop(Queue* ps);//出队列 DataType QueueFront(Queue* ps);//队头数据 DataType QueueBack(Queue* ps);//队尾数据 int QueueSize(Queue* ps);//队列剩余数据个数 - 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
Queue.c
#define _CRT_SECURE_NO_WARNINGS #include"Queue.h" void QueueInit(Queue* ps)//初始化 { assert(ps); ps->head = ps->tail = NULL;//两个指针都指向空 ps->size = 0;//此时队列没有数据 } void QueueDestroy(Queue* ps)//释放空间 { assert(ps); QN* cur = ps->head;//cur等于头指针，ps是结构体指针，结构体指针指向头指针 while (cur)//如果头指针不为空，就进入循环释放空间 { QN* del = cur;//保留头指针的节点 cur = cur->next;//头指针向后移动 free(del);//释放头指针移动前的节点 } ps->head = ps->tail = NULL;//释放完之后，头尾指针指向NULL ps->size = 0;//数据个数清0 } void QueuePush(Queue* ps, DataType x)//入队列 { assert(ps); QN* newnode = (QN*)malloc(sizeof(QN));//扩容一个新的节点出来 if (newnode == NULL) { perror("malloc fail\n"); exit(-1); } else { newnode->data = x;//对新节点就行初始化操作 newnode->next = NULL;//这里将新节点的next置空，不用考虑插入节点后的next指向了 } if (ps->tail == NULL)//第一次入队列数据head和tail都是指向NULL的，直接让head和tail都指向第一个新节点 { ps->head = ps->tail = newnode; } else { ps->tail->next = newnode;//将扩容节点插在tail后面 ps->tail = newnode;//让tail指向到插入的节点处 } ++ps->size;//插入size就加1，记录此时队列节点的个数 } void QueuePop(Queue* ps)//出队列（队列出数据就相当于单链表的头删） { assert(ps); assert(!QueueEmpty(ps));//如果队列没有节点了，断言生效 if(ps->head->next==NULL)//如果队列只剩下一个节点了，直接释放该节点，然后将头尾指针置空 { free(ps->head); ps->head = ps->tail = NULL; } else { QN* cur = ps->head;//保存当前头节点 ps->head = ps->head->next;//让头指针指向下一个节点 free(cur);//释放之前的头节点 cur = NULL; } --ps->size;//出一个数据size就减1 } bool QueueEmpty(Queue* ps)//判断队列是否为空 { assert(ps); return ps->head == NULL && ps->tail == NULL;//头尾指针都指向NULL，队列才为空 } DataType QueueFront(Queue* ps)//队头数据 { assert(ps); assert(!QueueEmpty(ps)); return ps->head->data; } DataType QueueBack(Queue* ps)//队尾数据 { assert(ps); assert(!QueueEmpty(ps)); return ps->tail->data; } int QueueSize(Queue* ps)//队列剩余数据个数 { assert(ps); return ps->size; /*QN* cur = ps->head;//不使用size的方法，遍历队列，如果偶尔查看数据个数还好，经常使用效率太慢了 int capacity = 0; while (cur) { ++capacity; cur = cur->next; } return capacity;*/ }- 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
test.c
#define _CRT_SECURE_NO_WARNINGS #include"Queue.h" //void Test1() //{ // Queue p; // QueueInit(&p);//初始化 // QueuePush(&p, 1);//入队列 // QueuePush(&p, 2); // QueuePush(&p, 3); // QueuePush(&p, 4); // while (!QueueEmpty(&p)) // { // printf("%d ",QueueFront(&p)); // QueuePop(&p);//出队列 // } // printf("\n"); // printf("%d ", QueueSize(&p)); // // QueueDestroy(&p);//释放空间 //} void menu() { printf("-----------------------------------------------\n"); printf("***********************************************\n"); printf("***1、入队列数据 2、出队列数据***\n"); printf("***3、查看队列数据个数 4、判断队列是否为空***\n"); printf("***5、提取队头数据 6、提取队尾数据***\n"); printf("*************7、出队列打印所有数据*************\n"); printf("***********************************************\n"); printf("-----------------------------------------------\n"); } int main() { //Test1(); Queue p; QueueInit(&p); int n = 0; int x = 0; do { menu(); printf("请选择操作:"); scanf("%d", &n); switch (n) { case 1: printf("请输入入队列数据，以-1截止:\n"); do { scanf("%d", &x); //QueuePush(&p, x); if (x == -1) break; QueuePush(&p, x); } while (x != -1); break; case 2: QueuePop(&p); break; case 3: printf("%d\n", QueueSize(&p)); break; case 4: if (QueueEmpty(&p)) { printf("队列为空\n"); } else { printf("队列不为空\n"); } break; case 5: printf("%d\n",QueueFront(&p)); QueuePop(&p); break; case 6: printf("%d\n", QueueBack(&p)); QueuePop(&p); break; case 7: while (!QueueEmpty(&p)) { printf("%d ", QueueFront(&p)); QueuePop(&p); } printf("\n"); break; case 0: QueueDestroy(&p); printf("退出程序\n"); break; default: printf("操作错误，请重新选择\n"); break; } } while (n); 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
- 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
总结
到这里栈和链表就结束了，如果有时间的话还会出一些栈和队列的oj题，如果没有时间的话下一期就直接进入二叉树了，又是一个难点。
那么就让我们下期见吧！ -
相关阅读:
经典算法-----汉诺塔问题
2022面试相关- web浏览器相关知识
毕业设计EMS办公管理系统（B/S结构）+J2EE+SQLserver8.0
Unity中的MVC思想
Swin Transformer：最佳论文，准确率和性能双佳的视觉Transformer | ICCV 2021
2022-Q3
Java基于API接口爬取商品数据
2022-08-15 - 初识MySQL
UE4 Sequence添加基础动画效果 （03-主序列的使用）
C. Fighting Tournament（模拟/map）
- 原文地址：https://blog.csdn.net/kdjjdjdjjejje128/article/details/126174582
