c语言队列的顺序存储实现
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
//队列的顺序存储实现
typedef int Position;
struct QNode {
int *Data;
Position Front,Rear;//定义队列的头部以及尾部
int MaxSize;//数组的大小
};
typedef struct QNode *Queue;
Queue CreateQueue(int MaxSize) {
Queue Q = (Queue)malloc(sizeof(struct QNode));//为该队列分配一块内存空间
Q->Data = (int *)malloc(MaxSize * sizeof(int));//为数组分配一块内存空间
Q->Front = Q->Rear = 0;
Q->MaxSize = MaxSize;
return Q;
}
bool IsFull(Queue Q) {
/*队列的顺序存储的实现--理解关键之处:(Q->Rear + 1) %% Q->MaxSize == Q->Front
该代码采取预留一个空位解决了(Front==Rear)时,对列是满还是空的问题。该公式就实现
了该判断,(注意Front==Rear==0),并且当队列为满时,肯定是队列只剩余一个空位
而Front总是指向该空位。(Front指向的位置一定没有元素,Rear总是指向队列尾部的最后一个元素
*/
return ((Q->Rear + 1) %% Q->MaxSize == Q->Front);
}
bool AddQ(Queue Q, int x) {
if (IsFull(Q)) {
printf("队列满");
return false;
} else {
Q->Rear = (Q->Rear + 1) %% Q->MaxSize;
Q->Data[Q->Rear] = x;
return true;
}
}
bool IsEmpty(Queue Q) {
return (Q->Front == Q->Rear);
}
int DeleteQ(Queue Q) {
if (IsEmpty(Q)) {
printf("队列空");
// return ERROR;
} else {
Q->Front = (Q->Front+1) %% Q->MaxSize;
return Q->Data[Q->Front];
}
}
//定义一个显示队列的方法
void showQueue(Queue Q){
//判断是否为空
if(IsEmpty(Q)) {
printf("队列为空,不能显示数据");
return;
}
//遍历数组,显示数据
/*
(Q->Rear+Q->MaxSize-Q->Front) %% Q->MaxSize):
该语句计算出Front与Rear相差多少,加上一个Q->Front,就为i设定了边界值
*/
for (int i = Q->Front + 1; i <= Q->Front + ((Q->Rear+Q->MaxSize-Q->Front) %% Q->MaxSize); i++) {
printf("Q->Data[%%d] = %%d
",i%%Q->MaxSize,Q->Data[i%%Q->MaxSize]);//取模运算的奇妙之处
}
}
int main(void) {
Queue Q = CreateQueue(5);
printf("直接显示数据Test:因为预留了一个位置,队列只能增加4个元素(队里数组大小为5):
");
AddQ(Q,1);
AddQ(Q,2);
AddQ(Q,3);
AddQ(Q,4);
showQueue(Q);
printf("队列满Test:
");
AddQ(Q,5);
printf("
元素出队列Test:
");
printf("出队列值:%%d
",DeleteQ(Q));
printf("出队列值:%%d
",DeleteQ(Q));
printf("出队列值:%%d
",DeleteQ(Q));
printf("出队列值:%%d
",DeleteQ(Q));
printf("
空队列显示Test:
");
DeleteQ(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
- 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
输出:
直接显示数据Test:因为预留了一个位置,队列只能增加4个元素(队里数组大小为5):
Q->Data[1] = 1
Q->Data[2] = 2
Q->Data[3] = 3
Q->Data[4] = 4
队列满Test:
队列满
元素出队列Test:
出队列值:1
出队列值:2
出队列值:3
出队列值:4
空队列显示Test:
队列空
--------------------------------
Process exited after 0.06129 seconds with return value 0
请按任意键继续. . .
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
推荐阅读