C语言连续存储实现队列机制

浏览:
字体:
发布时间:2013-12-23 12:22:30
来源:东方联盟

所谓队列,就是如同生活中的队列一样,拥有以下性质:

1).每次加入一个元素时,必须在队尾加入

2).每次拿走一个元素时,必须从对头拿走

总结起来也就是先进先出,后进后出。

从存储上看,队列有两种实现方式,一个是连续存储,一个是离散存储。连续存储就类似于数组,而离散存储就类似于链表,这里我们先实现比较简单的连续存储:

由于队列的操作可以在对头也可以在队尾,也就是说他可以在两端操作,这样我们就要用两个参数来描述:head和tail。一个指向对头,一个指向队尾的下一个。

这里说明一下,由于当队列为空时head=tial,而当队列满时head=tail,这样就出现了二义性。为了避免二义性,我们规定tail指向队尾的下一个元素,这样一来当队列

为空的时候,head=tail,而当队列为满时,tail+1=head。也就是说如果我们有N个空间,那我们只能使用N-1个,要留一个给tail。在head和tail移动的时候,我们也不是

简单地对他们加1,而是将他们加1之后对N取模,这样就可以循环得到从0~N-1的数了。

具体的实现,请看源代码:

/*************************************************************************	> File Name: sequeue.c	> Author: Baniel Gao	> Mail: createchance@163.com 	> Blog: blog.csdn.net/createchance 	> Created Time: Fri 20 Dec 2013 11:57:32 AM CST ************************************************************************/#include #include #define _DEBUG_ 1typedef struct _sequeue_ {	int total;	int head;	int tail;	int *data;} sequeue_st;sequeue_st *sequeue_init(int size);int sequeue_enqueue(sequeue_st *queue, int value);int sequeue_isfull(sequeue_st *queue);int sequeue_dequeue(sequeue_st *queue);int sequeue_isempty(sequeue_st *queue);int sequeue_free(sequeue_st *queue);#if _DEBUG_int sequeue_debug(sequeue_st *queue);#endifint main(void){	sequeue_st *queue;	int size = 10;	int value = 100;		queue = sequeue_init(size);	while (-1 != sequeue_enqueue(queue, value))		value++;#if _DEBUG_	printf("After enqueue....../n");	sequeue_debug(queue);#endif	while (-1 != sequeue_dequeue(queue))		value++;#if _DEBUG_	printf("After dequeue....../n");	sequeue_debug(queue);#endif	sequeue_free(queue);	return 0;}sequeue_st *sequeue_init(int size){	sequeue_st *queue = NULL;	queue = (sequeue_st *)malloc(sizeof(sequeue_st));	queue->head = 0;	queue->tail = 0;	queue->total = size;	queue->data = (int *)malloc(sizeof(int) * size);	return queue;}int sequeue_enqueue(sequeue_st *queue, int value){	if (sequeue_isfull(queue))		return -1;	queue->data[queue->tail] = value;	queue->tail = (queue->tail + 1) % queue->total;	return 0;}int sequeue_dequeue(sequeue_st *queue){	if (sequeue_isempty(queue))		return -1;	queue->head = (queue->head + 1) % queue->total;	return 0;}int sequeue_isempty(sequeue_st *queue){	if (queue->tail == queue->head)		return 1;	return 0;}int sequeue_isfull(sequeue_st *queue){	if ((queue->tail + 1) % queue->total == queue->head)		return 1;	return 0;}int sequeue_free(sequeue_st *queue){	free(queue->data);	free(queue);	return 0;}int sequeue_debug(sequeue_st *queue){	int index;	puts("------------------------ DEBUG ----------------------");	printf("total = %d/thead = %d/ttail = %d/n", queue->total, queue->head, queue->tail);	puts("-----------------------------------------------------");	for (index = 0; index < queue->total; index++)		printf("%5d", queue->data[index]);	puts("/n-----------------------------------------------------");	return 0;}

这里我为了方便对队列的控制于查看,我定义了一个debug函数,用条件编译可以将它屏蔽掉。

运行结果:


这样可以清楚的看到入队和出队的操作。


>更多相关文章
24小时热门资讯
24小时回复排行
资讯 | QQ | 安全 | 编程 | 数据库 | 系统 | 网络 | 考试 | 站长 | 下载 | 关于东盟 | 安全雇佣 | 搞笑视频大全 | 微信学院 |
关于我们 | 联系我们 | 广告服务 | 人才招聘 | 服务条款 | 免责申明 | 帮助中心 | 作品发布 | 网站地图 | 技术培训
Copyright © 2007 - 2018 Vm888.Com. All Rights Reserved
东方联盟 版权所有