C语言数据结构算法基础之循环队列示例

Rohana ·

更新时间:2024-11-15

· 45 次阅读

说明

示例代码

1. 首先定义结构体：

2. 定义各种算法：

3. 测试：

4. 最后的结果：

说明

循环队列是一种先进先出的，首尾相连的队列。

大致的结构如下图：

用数组来抽象的表示一下的话，如下图：

循环队列有两个指针指向数据，上图中的start和end就是那两个指针，它们指向相同的位置，表示的是空，即队列是空的。

随着数据的放入，队列一般有下面的两种形式：

需要注意第二种形式，从图上看end在start的前面了，但是因为循环关系，前后并不重要。

另外需要考虑的是队列满的情况：

但这种情况存在一个问题，即空队列和满队列没有办法区分了，end和start都指向了相同的位置。

为了解决这个问题，一个方法是空出一个位置不放数据，当end再加一个数据就等于start的时候就认为队列是满的：

这时实际的数据长度就会比分配的少1。

下面是队列中空和满的判断：

1. 队列为空时：end == start

2. 队列为满时：(end + 1) % size == start

这里的size是指分配的空间大小，而不是队列长度，队列的实际长度为(end - start + size) % size，最大长度是size-1

这也是因为要考虑循环的关系，所以要加上%size这个操作。

示例代码 1. 首先定义结构体：

//定义循环队列
typedef struct _LoopQueue {
int data[8];//存放数据
int start;//头指针
int end;//尾指针
} LoopQueue;

2. 定义各种算法：

#define TRUE1
#define FALSE0
#define SIZE8
//初始化队列
int init(LoopQueue *lq) {
lq->start = 0;
lq->end = 0;
return TRUE;
}
//判断队列是否为空
int isEmpty(LoopQueue *lq) {
if (lq->start == lq->end) {
return TRUE;
}
return FALSE;
}
//判断队列是否为满
int isFull(LoopQueue *lq) {
if ((lq->end + 1) % SIZE == lq->start) {
return TRUE;
}
return FALSE;
}
//获取队列的长度
int getLength(LoopQueue *lq) {
return (lq->end - lq->start + SIZE) % SIZE;
}
//插入数据
int pushQueue(LoopQueue *lq, int data) {
if(isFull(lq)) {
printf("Queue is full.\n");
return FALSE;
}
lq->data[lq->end] = data;
lq->end = (lq->end + 1) % SIZE;
return TRUE;
}
//弹出数据
int popQueue(LoopQueue *lq, int *data) {
if (isEmpty(lq)) {
printf("Queue is empty.\n");
return FALSE;
}
*data = lq->data[lq->start];
lq->start = (lq->start + 1) % SIZE;
return TRUE;
}
//显示队列中的数据
void printQueue(LoopQueue *lq) {
int index;
int count;
count = getLength(lq);
if (0 == count) {
printf("No data.\n");
return;
}
for (index = 0; index < count; index++) {
printf("%d ", lq->data[index]);
}
printf("\n");
return;
}

3. 测试：

int main()
{
int index;
int num;
//队列测试代码
LoopQueue *lq = (LoopQueue *)malloc(sizeof(LoopQueue));
init(lq);
printQueue(lq);
for (index = 0; index < SIZE; index ++) {//注意这里要放8个数据，但是实际上只能放7个，所以最后一个会报错
pushQueue(lq, index);
}
printQueue(lq);
for (index = 0; index < SIZE; index ++) {//同上，会打印一个错误
if (popQueue(lq, &num)) {
printf("%d\n", num);
}
}
printQueue(lq);
return 0;
}

4. 最后的结果：