- 1openlayer展示热力图_openlayers热力图
- 2CF-Educational Codeforces Round 44 (Rated for Div. 2)-E-Pencils and Boxes_educational round 44
- 3VS code上创建Vue项目详细化教程1-配置VScode与Vue_vscode vue
- 4Vue3浅尝_import { createstore } from 'vuex' 在vue3
- 5机器学习——Google 快速入门课程（综合版）_google机器学习representation: feature engineering
- 6微服务五大组件_微服务组件
- 7PS2接口编程_单片机模拟ps2键盘源码
- 8基于FPGA的自动售货机设计Verilog代码Quartus仿真_fpga自动排队系统仿真
- 9Window下安装Zookeeper
- 10SQL 审核神器 SQLE 专业版全新上线，永久免费！
详解数据结构之队列、循环队列(源码)
赞
踩
详解数据结构之队列、循环队列(源码)
队列属于线性表
队列：就好比如，我们在排队买东西时排队，第一个先来的第一个买，最后一个到的最后一个买，这里的队列也是满足先进先出，后进后出的规律（First In First Out），允许插入数据的一端叫做队头简称入队列，允许删除数据的一端叫做队尾简称出队列。
队列的存储形式：
-
顺序存储结构，实现循环队列 ，队列长度时固定的
-
链式存储结构，实现不循环队列，队列长度理论上是无限大的
两种存储结构实现的队列复杂度：
- 时间复杂度 O(1)
- 空间复杂度 O(1)
队列
使用链式结构实现的队列，其基本结构类似于单链表。使用next指针将每一个节点链接。主要区别在于没有使用一个指针来指向节点，这里定义了两个指针指针单链表，一个phead指针指向单链表的头，一个ptail指针指向单链表的尾。
单链表的头为队列的队头，单链表的尾为队列的队尾。
有了指针指向链表的最后一个节点，就不再需要使用循环遍历到链表的最后一个节点，将入栈的时间复杂度从O(N)优化到O(1)。
typedef int QueueDataType;
typedef struct QueueNode//节点
{
QueueDataType val;
struct QueueNode* next;
}QueueNode;
struct Queue
{
QueueNode* phead;//指向队头的指针
QueueNode* ptail;//指向队尾的指针
int size;//统计单链表的节点个数
};
typedef struct Queue Queue;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
功能实现
//初始化 void QueueInit(Queue* p); //销毁 void QueueDestory(Queue* p); //入队列，队尾,不就是尾插 void QueuePush(Queue* p, QueueDataType x); //出队列，队头 void QueuePop(Queue* p); //取队头数据 QueueDataType QueueFront(Queue* p); //取队尾数据 QueueDataType QueueBack(Queue* p); //判空 bool QueueEmpty(Queue* p); //获取有效数据个数 int QueueSize(Queue* p);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
初始化、销毁
初始化
初始化指向队列的两个指针，和对统计节点个数大小的size，由于传递的是地址就不需要返回值。
//初始化
void QueueInit(Queue* p)
{
assert(p);
p->phead = p->ptail = NULL;
p->size = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
销毁
将队列的节点一一销毁，其操作逻辑与单链表相似。
销毁链表，需要对每一个节点进行释放，而只使用一个指针pcur，释放当前的节点就找不到下一个节点了，这里需要使用两个指针。
一个指针用来释放（pcur），一个指针用来指向待释放之后的节点（next）。
当释放完pcur节点后，更新pcur的位置 pcur = next;，用来释放下一个节点，next指针也需要更新用来指向下一个节点 next = pcur->next;，用来对pcur进行更新。直到pcur指向空指针时释放完所有节点，跳出循环。而 phead和ptail指针，还没有置为空，这时候时野指针，最后一步 p->phead = p->ptail = NULL;。
void QueueDestory(Queue* p)
{
assert(p);
QueueNode* pcur = p->phead;
while (pcur)
{
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
p->phead = p->ptail = NULL;
p->size = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
判空
判断队列的节点是否为空并返回一个布尔值。
如上对队列的初始化，两个头尾指针指向的都为空，此时队列就是空，队列为空返回true，不为返回false。
函数起始别忘了对指针p判空，为空则说明队列不存在了。
//判空
bool QueueEmpty(Queue* p)
{
assert(p);
return p->ptail == NULL && p->phead == NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
入队列、出队列
入队列
想要进行尾插首先得有一个指针指向最后一个节点，然后将创建的新节点插入到该节点后面，最后更新ptail指针指向的位置
入队列有两种情况：
- 队列为空
此时phead和ptail都指向空，插入一个新节点，phead和ptail均指向它。
- 队列不为空
在ptail指针后插入一个新节点，通过节点的next指针连接，然后更新ptail指针，让其指向新的尾。
最后别忘了将统计节点个数的size加1。
//入队列，队尾,不就是单链表的尾插 void QueuePush(Queue* p, QueueDataType x) { assert(p); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//创建新节点 if (newnode == NULL)//判空，有无开辟成功 { perror("malloc"); return; } newnode->val = x;//赋值 newnode->next = NULL; if (p->phead == NULL)//phead和ptail为空时 { p->phead = p->ptail = newnode; } else//两者不为空 { p->ptail->next = newnode; p->ptail = newnode; } p->size++;//别忘了记录新加入的节点 }
- 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
出队列
出队列的逻辑并不复杂，前提是指针p不为空，为空则说明队列不存在、队列不为空，为空则说明没有节点可删，接下来就是对空指针解引用。
它同样分为两种情况：
- 只有一个节点
即phead和ptail指向同一个节点时，将该节点释放，然后将phead和ptail指针指向空。
- 有许多个节点
一，保存phead之后的节点 QueueNode* Next = phead->next;二，然后释放第一个节点 free(phead);三，最后将 Next 赋给 phead，更新头节点的位置。
最后将size减1。
//出队列，队头,这不就是单链表的头删吗 void QueuePop(Queue* p) { assert(p); assert(!QueueEmpty(p)); if (p->phead == p->ptail) { free(p->phead); p->phead = p->ptail == NULL; } else { QueueNode* Next = p->phead->next; free(p->phead); p->phead = Next; } p->size--; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
取队头数据、取队尾数据
取对头数据
取对头数据那是相当简易，只需要将头指针指向的节点的value值返回即可。需要注意的是对指针p和队列的判空，以及返回数据的类型。
//取队头数据
QueueDataType QueueFront(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->phead->val;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
取队尾数据
有了之前定义的ptail指针，就不需要像单链表一个一个节点的遍历到最后一个节点，取队尾数据，只需将尾指针指向的节点的value值返回即可，它需要注意的点与取对头数据相同。
//取队尾数据
QueueDataType QueueBack(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->ptail->val;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
取队列有效数据个数
将队列的size返回，返回值为int，因为它只是用来统计个数的。
//获取有效数据个数
int QueueSize(Queue* p)
{
assert(p);
return p->size;
}
- 1
- 2
- 3
- 4
- 5
- 6
源码
Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int QueueDataType; typedef struct QueueNode { QueueDataType val; struct QueueNode* next; }QueueNode; struct Queue { QueueNode* phead;//指向队头的指针 QueueNode* ptail;//指向队尾的指针 int size; }; typedef struct Queue Queue; //初始化 void QueueInit(Queue* p); //销毁 void QueueDestory(Queue* p); //入队列，队尾,不就是尾插 void QueuePush(Queue* p, QueueDataType x); //出队列，队头 void QueuePop(Queue* p); //取队头数据 QueueDataType QueueFront(Queue* p); //取队尾数据 QueueDataType QueueBack(Queue* p); //判空 bool QueueEmpty(Queue* p); //获取有效数据个数 int QueueSize(Queue* p);
- 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
Queue.c
#include "Queue.h" //初始化 void QueueInit(Queue* p) { assert(p); p->phead = p->ptail = NULL; p->size = 0; } //判空 bool QueueEmpty(Queue* p) { assert(p); return p->ptail == NULL && p->phead == NULL; } //入队列，队尾 void QueuePush(Queue* p, QueueDataType x) { assert(p); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc"); return; } newnode->val = x; newnode->next = NULL; if (p->phead == NULL) { p->phead = p->ptail = newnode; } else { p->ptail->next = newnode; p->ptail = newnode; } p->size++; } //出队列，队头 void QueuePop(Queue* p) { assert(p); assert(!QueueEmpty(p)); if (p->phead == p->ptail) { free(p->phead); p->phead = p->ptail == NULL; } else { QueueNode* Next = p->phead->next; free(p->phead); p->phead = Next; } p->size--; } //取队头数据 QueueDataType QueueFront(Queue* p) { assert(p); assert(!QueueEmpty(p)); return p->phead->val; } //取队尾数据 QueueDataType QueueBack(Queue* p) { assert(p); assert(!QueueEmpty(p)); return p->ptail->val; } //获取有效数据个数 int QueueSize(Queue* p) { assert(p); return p->size; } //销毁 void QueueDestory(Queue* p) { assert(p); QueueNode* pcur = p->phead; while (pcur) { QueueNode* next = pcur->next; free(pcur); pcur = next; } p->ptail = p->ptail = NULL; p->size = 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
循环队列
循环队列，就类似将链表的头尾节点链接在一起了。
使用顺序存储结构的优缺点：
优
- 数组支持随机访问，在O(1)时间内访问任意元素（速度）
- 数组的操作和使用简单好理解
- 不需要使用额外空间存储节点指针
缺
- 数组的大小在创建时就确定了
typedef int CQDataType;
typedef struct CircularQueue
{
CQDataType* arr;
int front;//指向队头元素
int rear;//指向队尾的下一个位置
int capacity;//空间大小
}CQueue;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
初始情况下，front和rear指向同体块空间时，队列为空，入队列后front不变，rear向后加1，如下图。
当插入a5时rear将指向数组外的空间，然后在插入a6，rear继续指向数组之外的空间。纳尼？？都指向数组之外的空间了，那不是越界访问了吗？
现在假设不存在这种问题，插入a5数据后rear指向front，此时有没有发现又乱套了。front和rear指向了同一块空间，前文以及说过当frong和rear指向同一块空间时队列为空，那这种情况又该咋办呢~。
为了解决以上两种情况，这里将数组空出一块空间，不插入a5此时队列就是满队列的情况。
而想要实现rear为4时在加上1能够循环到0，可以使用求模运算操作符。
初始条件下开辟给数组capacity+1的空间，多余的1是给rear用的，防止font和rear相等无法判断是否满队列还是空队列的情况。假设此时capacity为4，那就得开辟空间大小为5的数组，如上图。
pcq->rear + 1) % (pcq->capacity + 1) == pcq->front;如上图，此时rear为4，capacity为4，都加1后 5 % 5结果为刚好等于front此时满队列，而不是如同之前的情况，rear和front的尴尬情况。
实现rear加1后能够在 0 ~ 4内循环，而不造成数组越界访问使用取模操作符 ，如上图，当rear为4时加1为5，但它指向了0，根据pcq->rear = pcq->rear % pcq->capacity + 1;不能得出 此时 5 % 5的结果为0，然后将0赋给rear重置了rear的位置。
功能实现
//开辟空间，n指开辟大小 void CQCreat2(CQueue* pcq, int n); //判断队列空否 bool CQEmpty(CQueue* pcq); //判断队列满否 bool CQFull(CQueue* pcq); //入队列 void CQPush(CQueue* pcq, CQDataType x); //出队列 void CQPop(CQueue* pcq); //取队头元素 CQDataType CQFront(CQueue* pcq); //取队尾元素 CQDataType CQBACK(CQueue* pcq); //销毁队列 void CQDestory(CQueue* pcq);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
开辟空间、销毁队列
开辟空间、初始化
开辟大小为n + 1的空间，让后将front和rear置0，将n赋给capacity，表示了rear和front的最大取值。
void CQCreat2(CQueue* pcq, int n)
{
pcq->arr = (CQDataType*)malloc(sizeof(CQDataType) * (n + 1));
pcq->front = pcq->rear = 0;
pcq->capacity = n;
}
- 1
- 2
- 3
- 4
- 5
- 6
销毁队列
销毁队列，将arr数组释放，让后置空（此时为野指针），需要注意的是对 pcq->arr，的判空，若它为空指针就不需要释放数组。
//销毁队列
void CQDestory(CQueue* pcq)
{
assert(pcq);
if(pcq->arr)
free(pcq->arr);
pcq->arr = NULL;
pcq->front = pcq->rear = pcq->capacity = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
判断队列满否、空否
判断队列是否被放满
前文以及提过，判空后队列满返回真，队列未满返回假，使用assert断言避免pcq为空指针，从而造成对空指针的解引用。
//判断队列满否
bool CQFull(CQueue* pcq)
{
assert(pcq);
return (pcq->rear + 1) % (pcq->capacity + 1) == pcq->front;
}
- 1
- 2
- 3
- 4
- 5
- 6
判断队列是否为空队列
front与rear相等队列为空返回真，不相等返回假。
//判断队列空否
bool CQEmpty(CQueue* pcq)
{
assert(pcq);
return pcq->front == pcq->rear;//相等为空
}
- 1
- 2
- 3
- 4
- 5
- 6
入队列、出队列
入队列
入队列不难理解，只需要找到对应得数组标然后放进去即可。但需要严重关注的是在入队列前对数组是否满了进行判断，以及成功入了一个元素rear加1后，对rear重新修正大小，避免造成数组越界。
//入队列
void CQPush(CQueue* pcq, CQDataType x)
{
assert(pcq);
assert(!CQFull(pcq));
pcq->arr[pcq->rear++] = x;
pcq->rear %= pcq->capacity + 1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
出队列
出队列，同理出队列，想要出队列那就不可能对一个空队列出元素，那得先调用判断队列是否为空队列的函数，然后在出队列，想要实现出队列，只需要让front加1即可，前front指向的数据被放弃掉是无效的，将front加1后同rear一样需要对其重新修正大小，避免造成数组越界。
//出队列
void CQPop(CQueue* pcq)
{
assert(pcq);
assert(!CQEmpty(pcq));
pcq->front++;
pcq->front %= pcq->capacity + 1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
取对头数据、取队尾数据
取对头数据
只需将front指向的数据返回。
//取队头元素
CQDataType CQFront(CQueue* pcq)
{
assert(pcq);
assert(!CQEmpty(pcq));
return pcq->arr[pcq->front];
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
取队尾数据
只需将rear指向的数据返回。
//取队尾元素
CQDataType CQBACK(CQueue* pcq)
{
assert(pcq);
assert(!CQEmpty(pcq));
int ret = pcq->rear - 1;
if (pcq->rear == 0)
{
ret = pcq->capacity;
}
return pcq->arr[ret];
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
源码
CircularQueue.h
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int CQDataType; typedef struct CircularQueue { CQDataType* arr; int front; int rear; int capacity; }CQueue; //开辟空间，n指开辟大小 CQueue* CQCreat(int n); void CQCreat2(CQueue* pcq, int n); //判断队列空否 bool CQEmpty(CQueue* pcq); //判断队列满否 bool CQFull(CQueue* pcq); //入队列 void CQPush(CQueue* pcq, CQDataType x); //出队列 void CQPop(CQueue* pcq); //取队头元素 CQDataType CQFront(CQueue* pcq); //取队尾元素 CQDataType CQBACK(CQueue* pcq); //销毁队列 void CQDestory(CQueue* pcq);
- 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
CircularQueue.c
#include "Queues.h" //开辟空间，n指开辟大小 void CQCreat2(CQueue* pcq, int n) { pcq->arr = (CQDataType*)malloc(sizeof(CQDataType) * (n + 1)); pcq->front = pcq->rear = 0; pcq->capacity = n; } //判断队列空否 bool CQEmpty(CQueue* pcq) { assert(pcq); return pcq->front == pcq->rear;//相等为空 } //判断队列满否 bool CQFull(CQueue* pcq) { assert(pcq); return (pcq->rear + 1) % (pcq->capacity + 1) == pcq->front; } //入队列 void CQPush(CQueue* pcq, CQDataType x) { assert(pcq); assert(!CQFull(pcq)); pcq->arr[pcq->rear++] = x; pcq->rear %= pcq->capacity + 1; } //出队列 void CQPop(CQueue* pcq) { assert(pcq); assert(!CQEmpty(pcq)); pcq->front++; pcq->front %= pcq->capacity + 1; } //取队头元素 CQDataType CQFront(CQueue* pcq) { assert(pcq); assert(!CQEmpty(pcq)); return pcq->arr[pcq->front]; } //取队尾元素 CQDataType CQBACK(CQueue* pcq) { assert(pcq); assert(!CQEmpty(pcq)); int ret = pcq->rear - 1; if (pcq->rear == 0) { ret = pcq->capacity; } return pcq->arr[ret]; } //销毁队列 void CQDestory(CQueue* pcq) { assert(pcq); free(pcq->arr); pcq->arr = NULL; pcq->front = pcq->rear = pcq->capacity = 0; } Type x) { assert(pcq); assert(!CQFull(pcq)); pcq->arr[pcq->rear++] = x; pcq->rear %= pcq->capacity + 1; } //出队列 void CQPop(CQueue* pcq) { assert(pcq); assert(!CQEmpty(pcq)); pcq->front++; pcq->front %= pcq->capacity + 1; } //取队头元素 CQDataType CQFront(CQueue* pcq) { assert(pcq); assert(!CQEmpty(pcq)); return pcq->arr[pcq->front]; } //取队尾元素 CQDataType CQBACK(CQueue* pcq) { assert(pcq); assert(!CQEmpty(pcq)); int ret = pcq->rear - 1; if (pcq->rear == 0) { ret = pcq->capacity; } return pcq->arr[ret]; } //销毁队列 void CQDestory(CQueue* pcq) { assert(pcq); free(pcq->arr); pcq->arr = NULL; pcq->front = pcq->rear = pcq->capacity = 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
- 101
- 102
- 103
- 104
- 105
- 106
- 107
