C语言数据结构算法循环队列
jiangwei0512 人气:3说明
循环队列是一种先进先出的，首尾相连的队列。
大致的结构如下图：
用数组来抽象的表示一下的话，如下图：
循环队列有两个指针指向数据，上图中的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 TRUE 1
#define FALSE 0
#define SIZE 8
//初始化队列
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. 最后的结果：
加载全部内容