-
数据结构：队列——概念及队列顺序存储的实现
基本概念
-
队列定义：
队列也是一种受限的线性表，只允许一端插入，另一端删除
-
基本操作
void InitQueue(SqQueue &Q) 初始化队列 bool QueueEmpty(SqQueue Q) 判断队空 bool EnQueue(SqQueue &Q,ElemType e) 入队 bool DnQueue(SqQueue &Q,ElemType &e) 出队 bool GetHead(SqQueue Q,ElemType &e) 读队头元素- 1
- 2
- 3
- 4
- 5
-
顺序队列和循环队列
- 顺序队列
下图表示队列的初始化、入队、出队，可以看出队初始化：front=rear=0 队空：front==0&&rear==0- 1
- 2
假设rear=maxsize表示队满，当有元素出栈时，rear仍=maxsize，但此时队列是满的，所以rear==maxsize不能作为队满的条件
那么，用rear-front==maxsize呢？当有元素出队而队中仍有元素时，队尾指针已经到达队末尾，不会有元素能进入队中，队不会满。
- 循环队列
由于顺序队列的不足，因此引出循环队列的概念将顺序队列臆造为一个环状的空间。如图：
- 顺序队列
队列的顺序存储（循环队列）
牺牲一个单元来区分队空和队满
入队
-
图解
-
代码
/*入队*/ bool EnQueue(SqQueue &Q,ElemType e){ if(QueueFull(Q))return false; Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%MaxSize; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
出队
-
图解
-
代码
/*出队*/ bool DnQueue(SqQueue &Q,ElemType &e){ if(QueueEmpty(Q))return false; e=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
栈空和栈满理解
队空：front==rear 队满：(rear+1)%maxsize==front- 1
- 2
以下两种情况都属于栈满，该方法需要牺牲掉一个空间来区分栈空和栈满,这个空间并不是指特定的，只是在队头和队尾之间留一个空。
完整代码
#include "stdio.h" #include "stdlib.h" #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; //存放元素 int front,rear; //队头指针和队尾指针 }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front=Q.rear=0; } /*判断队空*/ bool QueueEmpty(SqQueue Q){ if (Q.rear==Q.front)return true; else return false; } /*判断队满*/ bool QueueFull(SqQueue Q){ if ((Q.rear+1)%MaxSize==Q.front)return true; else return false; } /*入队*/ bool EnQueue(SqQueue &Q,ElemType e){ if(QueueFull(Q))return false; Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%MaxSize; return true; } /*出队*/ bool DnQueue(SqQueue &Q,ElemType &e){ if(QueueEmpty(Q))return false; e=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; return true; } /*读队头元素*/ bool GetHead(SqQueue Q,ElemType &e){ if(QueueEmpty(Q))return false; e=Q.data[Q.front]; return true; } /*队长*/ int Length(SqQueue Q){ return (Q.rear-Q.front+MaxSize)%MaxSize; } /*遍历*/ void Proint(SqQueue Q){ for (int i = Q.front; i < Q.rear; ++i) { printf("%d ",Q.data[i]); } printf("\n"); } int main(){ SqQueue Q; printf("***************************************\n"); printf("******** 1.初始化队 2.空队判断 ********\n"); printf("******** 3. 进 队 4. 出 队 ********\n"); printf("******** 5.读取队首 6.队满判断 ********\n"); printf("******** 7. 遍 历 8. 队 长 ********\n"); printf("******** 0. 退 出 ********\n"); printf("***************************************\n"); bool flag= true; int x; ElemType e; while(flag){ printf("请输入命令："); scanf("%d",&x); switch (x) { case 1: InitQueue(Q); printf("\t空队初始化完成\n"); break; case 2: if(QueueEmpty(Q)) printf("\t该队是空队\n"); else printf("\t该队不是空队\n"); break; case 3: printf("\t请输入要进队的元素："); int a; scanf("%d",&e); if(EnQueue(Q,e))printf("\t元素入队成功\n"); else printf("\t元素入队失败\n"); break; case 4: if(DnQueue(Q,e)) printf("\t元素出队成功,出队的元素为：%d\n",e); else printf("\t元素出队失败\n"); break; case 5: if(GetHead(Q,e)) printf("\t队首元素为：%d\n",e); else printf("\t该队为空栈\n"); break; case 6: if(QueueFull(Q)) printf("\t该队已满\n"); else printf("\t该队还未满\n"); break; case 7: printf("\t当前队中元素有："); Proint(Q); break; case 8: printf("\t当前队长为：%d\n",Length(Q)); break; case 0: printf("退出成功\n"); flag= false; break; default: printf("命令错误，请重新输入！！！"); break; } } }- 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
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
运行截图
增设size表示元素个数的数据成员
栈空和栈满理解
typedef struct {
ElemType data[MaxSize]; //存放元素
int front,rear; //队头指针和队尾指针
int size;//表示队中成员个数
}SqQueue;队空：size=0
队满：size=maxsize
完整代码
#include "stdio.h" #include "stdlib.h" #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; //存放元素 int front,rear; //队头指针和队尾指针 int size; }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front=Q.rear=0; Q.size=0; } /*判断队空*/ bool QueueEmpty(SqQueue Q){ if (Q.size==0)return true; else return false; } /*判断队满*/ bool QueueFull(SqQueue Q){ if (Q.size==MaxSize)return true; else return false; } /*入队*/ bool EnQueue(SqQueue &Q,ElemType e){ if(QueueFull(Q))return false; Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%MaxSize; Q.size++; return true; } /*出队*/ bool DnQueue(SqQueue &Q,ElemType &e){ if(QueueEmpty(Q))return false; e=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; Q.size--; return true; } /*读队头元素*/ bool GetHead(SqQueue Q,ElemType &e){ if(QueueEmpty(Q))return false; e=Q.data[Q.front]; return true; } /*队长*/ int Length(SqQueue Q){ return Q.size; } /*遍历*/ void Proint(SqQueue Q){ for (int i = Q.front; i < Q.rear; ++i) { printf("%d ",Q.data[i]); } printf("\n"); } int main(){ SqQueue Q; printf("***************************************\n"); printf("******** 1.初始化队 2.空队判断 ********\n"); printf("******** 3. 进 队 4. 出 队 ********\n"); printf("******** 5.读取队首 6.队满判断 ********\n"); printf("******** 7. 遍 历 8. 队 长 ********\n"); printf("******** 0. 退 出 ********\n"); printf("***************************************\n"); bool flag= true; int x; ElemType e; while(flag){ printf("请输入命令："); scanf("%d",&x); switch (x) { case 1: InitQueue(Q); printf("\t空队初始化完成\n"); break; case 2: if(QueueEmpty(Q)) printf("\t该队是空队\n"); else printf("\t该队不是空队\n"); break; case 3: printf("\t请输入要进队的元素："); int a; scanf("%d",&e); if(EnQueue(Q,e))printf("\t元素入队成功\n"); else printf("\t元素入队失败\n"); break; case 4: if(DnQueue(Q,e)) printf("\t元素出队成功,出队的元素为：%d\n",e); else printf("\t元素出队失败\n"); break; case 5: if(GetHead(Q,e)) printf("\t队首元素为：%d\n",e); else printf("\t该队为空栈\n"); break; case 6: if(QueueFull(Q)) printf("\t该队已满\n"); else printf("\t该队还未满\n"); break; case 7: printf("\t当前队中元素有："); Proint(Q); break; case 8: printf("\t当前队长为：%d\n",Length(Q)); break; case 0: printf("退出成功\n"); flag= false; break; default: printf("命令错误，请重新输入！！！"); break; } } }- 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
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
运行截图
增设tag数据成员
栈空和栈满理解
typedef struct {
ElemType data[MaxSize]; //存放元素
int front,rear; //队头指针和队尾指针
int tag;//用0、1来表示
}SqQueue;队空：rear == front&&tag == 0
队满：rear == front&&tag == 1
完整代码
#include "stdio.h" #include "stdlib.h" #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; //存放元素 int front,rear; //队头指针和队尾指针 int tag; }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front=Q.rear=0; Q.tag=0; } /*判断队空*/ bool QueueEmpty(SqQueue Q){ if (Q.rear==Q.front&&Q.tag==0)return true; else return false; } /*判断队满*/ bool QueueFull(SqQueue Q){ if (Q.rear==Q.front&&Q.tag==1)return true; else return false; } /*入队*/ bool EnQueue(SqQueue &Q,ElemType e){ if(QueueFull(Q))return false; Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%MaxSize; Q.tag=1; return true; } /*出队*/ bool DnQueue(SqQueue &Q,ElemType &e){ if(QueueEmpty(Q))return false; e=Q.data[Q.front]; Q.front=(Q.front+1)%MaxSize; Q.tag=0; return true; } /*读队头元素*/ bool GetHead(SqQueue Q,ElemType &e){ if(QueueEmpty(Q))return false; e=Q.data[Q.front]; return true; } /*队长*/ int Length(SqQueue Q){ return (Q.rear-Q.front+MaxSize)%MaxSize; } /*遍历*/ void Proint(SqQueue Q){ for (int i = Q.front; i < Q.rear; ++i) { printf("%d ",Q.data[i]); } printf("\n"); } int main(){ SqQueue Q; printf("***************************************\n"); printf("******** 1.初始化队 2.空队判断 ********\n"); printf("******** 3. 进 队 4. 出 队 ********\n"); printf("******** 5.读取队首 6.队满判断 ********\n"); printf("******** 7. 遍 历 8. 队 长 ********\n"); printf("******** 0. 退 出 ********\n"); printf("***************************************\n"); bool flag= true; int x; ElemType e; while(flag){ printf("请输入命令："); scanf("%d",&x); switch (x) { case 1: InitQueue(Q); printf("\t空队初始化完成\n"); break; case 2: if(QueueEmpty(Q)) printf("\t该队是空队\n"); else printf("\t该队不是空队\n"); break; case 3: printf("\t请输入要进队的元素："); int a; scanf("%d",&e); if(EnQueue(Q,e))printf("\t元素入队成功\n"); else printf("\t元素入队失败\n"); break; case 4: if(DnQueue(Q,e)) printf("\t元素出队成功,出队的元素为：%d\n",e); else printf("\t元素出队失败\n"); break; case 5: if(GetHead(Q,e)) printf("\t队首元素为：%d\n",e); else printf("\t该队为空栈\n"); break; case 6: if(QueueFull(Q)) printf("\t该队已满\n"); else printf("\t该队还未满\n"); break; case 7: printf("\t当前队中元素有："); Proint(Q); break; case 8: printf("\t当前队长为：%d\n",Length(Q)); break; case 0: printf("退出成功\n"); flag= false; break; default: printf("命令错误，请重新输入！！！"); break; } } }- 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
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
运行截图
队列的链式存储
队列的链式存储，类似于单链表，入队——头插法，出队——删除首元结点。
假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列。这样就不会出现存储分配不合理和“溢出”现象队列的存储类型（比较特殊）
typedef struct LinkNode{ ElemType data; struct LinkNode *next; }LinkNode; typedef struct { LinkNode *front,*rear; }liQueue;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
完整代码
#include "stdio.h" #include "stdlib.h" typedef int ElemType; typedef struct LinkNode{ ElemType data; struct LinkNode *next; }LinkNode; typedef struct { LinkNode *front,*rear; }liQueue; /*初始化队列*/ void InitQueue(liQueue &Q){ Q.rear=Q.front=(LinkNode*) malloc(sizeof(LinkNode)); Q.front->next=NULL; } /*判断队空*/ bool QueueEmpty(liQueue Q){ if (Q.rear==Q.front)return true; else return false; } /*入队*/ bool EnQueue(liQueue &Q,ElemType e){ LinkNode *s=(LinkNode*) malloc(sizeof(LinkNode)); s->data=e; s->next=NULL; Q.rear->next=s; Q.rear=s; return true; } /*出队*/ bool DnQueue(liQueue &Q,ElemType &e){ if (QueueEmpty(Q))return false; LinkNode *p=Q.front->next; e=p->data; Q.front->next=p->next; if (Q.rear==p) Q.rear==Q.front; free(p); return true; } /*读队头元素*/ bool GetHead(liQueue Q,ElemType &e){ if (QueueEmpty(Q))return false; e=Q.front->next->data; return true; } /*队长*/ int Length(liQueue Q){ int i=0; LinkNode *p=Q.front->next; if (p!=Q.rear){ p=p->next; i++; } return ++i; } /*遍历*/ void Proint(liQueue Q){ LinkNode *p=Q.front->next; while (p!=NULL){ printf("%d ",p->data); p=p->next; } printf("\n"); } int main(){ liQueue Q; printf("***************************************\n"); printf("******** 1.初始化队 2.空队判断 ********\n"); printf("******** 3. 进 队 4. 出 队 ********\n"); printf("******** 5.读取队首 6. 队 长 ********\n"); printf("******** 7. 遍 历 0. 退 出 ********\n"); printf("***************************************\n"); bool flag= true; int x; ElemType e; while(flag){ printf("请输入命令："); scanf("%d",&x); switch (x) { case 1: InitQueue(Q); printf("\t空队初始化完成\n"); break; case 2: if(QueueEmpty(Q)) printf("\t该队是空队\n"); else printf("\t该队不是空队\n"); break; case 3: printf("\t请输入要进队的元素："); int a; scanf("%d",&e); if(EnQueue(Q,e))printf("\t元素入队成功\n"); else printf("\t元素入队失败\n"); break; case 4: if(DnQueue(Q,e)) printf("\t元素出队成功,出队的元素为：%d\n",e); else printf("\t元素出队失败\n"); break; case 5: if(GetHead(Q,e)) printf("\t队首元素为：%d\n",e); else printf("\t该队为空栈\n"); break; case 6: printf("\t当前队长为：%d\n",Length(Q)); break; break; case 7: printf("\t当前队中元素有："); Proint(Q); break; case 0: printf("退出成功\n"); flag= false; break; default: printf("命令错误，请重新输入！！！"); break; } } }- 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
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
运行截图
参考资料
《王道：数据结构考研复习指导》
-
-
相关阅读:
devtools以及修改theymleaf后自动刷新浏览器
java随手记
电商项目缓存问题的解决方案（初步）
Java学习笔记5.2.2 List接口 - LinkedList类
React组件进阶
DQL（数据库查询）
神经网络和深度神经网络,深度神经网络发展历程
基于单片机PID电机控制系统设计
codeforces-1734C - Removing Smallest Multiples
扩展欧几里得
- 原文地址：https://blog.csdn.net/weixin_46629453/article/details/125956562
