亲宝软件园·资讯

展开

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. 最后的结果:

加载全部内容

相关教程
猜你喜欢
用户评论