数据结构 - 队列（顺序队列、通用数据类型）

在文章数据结构 - 队列（顺序队列、单一数据类型）和数据结构 - 队列（链式队列、通用数据类型）分别介绍了队列的不同形式，针对不同的使用场合可以选择不同形式。本文在前面的基础上，介绍一种可以通用数据结构、复用性高的顺序循环队列。

在前面文章通用数据结构的队列实现原理中，使用了malloc函数动态分配数据类型大小的空间以实现可以通用数据类型，其中有限队列的形式中，是在初始化的过程中就完成了空间的分配，并链接成循环队列，但是其在链式指针上面又浪费了很多空间。而采用顺序式，也可以在初始化时候完成空间分配，并把连续的地址连成循环。
在初始化分配的时候，分配来连续的数据类型大小乘于队列长度大小的空间，并采用以下的宏定义就可以实现访问数组式的访问到队列成员。

#define ARRAY_AT(arr, size, index)	(*(((unsigned char *)arr)+(index)*(size)))

#ifndef __queue_H
#define __queue_H

typedef struct 
{
	void			*arr;			
	unsigned int	item_size;		
	unsigned int	queue_len;		
	unsigned int	items_cnt;		
	unsigned int	head;			
	unsigned int	tail;			
	unsigned char	state;			
	unsigned char	overwrite;		
}QUEUE;	

unsigned char queue_init(QUEUE *queue, unsigned int item_size, unsigned int queue_len, unsigned char overwrite);
unsigned char queue_empty(QUEUE *queue);
unsigned char queue_full(QUEUE *queue);
unsigned int queue_cnt(QUEUE *queue);
unsigned char queue_push(QUEUE *queue, void *data);
unsigned char queue_pop(QUEUE *queue, void *data);
void queue_clean(QUEUE *queue);
void queue_free(QUEUE *queue);

#endif

QUEUE结构体当中，包含了存放队列成员空间的基地址（*arr），每个成员所占用的空间大小（item_size），队列长度（queue_len），队列成员计数（items_cnt），头尾索引，覆写队列标志（overwrite，为1时，新入队的数据在满队的时候会把队首的数据覆盖掉，为0时，在满队时候新数据将不能入队）

#include "queue.h"
#include 
#include 

#ifndef ARRAY_AT(arr, size, index)
#define ARRAY_AT(arr, size, index)	(*(((unsigned char *)arr)+(index)*(size)))
#endif


unsigned char queue_init(QUEUE *queue, unsigned int item_size, unsigned int queue_len, unsigned char overwrite)
{
	queue->arr = malloc(item_size * queue_len);		
	if (queue->arr != NULL)
	{
		queue->item_size = item_size;
		queue->queue_len = queue_len;
		queue->overwrite = overwrite;
		queue->tail = 0;
		queue->head = 0;
		queue->state = 0;
		queue->items_cnt = 0;
	}
	else 
	{
		return 0;
	}

	memset(queue->arr, 0, item_size * queue_len);

	return 1;
}


unsigned char queue_empty(QUEUE *queue)
{
    if (queue->state == 0)
	{
		return 1;
	}
    else
	{
		return 0;
	}
}


unsigned char queue_full(QUEUE *queue)
{
    if (queue->head == queue->tail && queue->state == 1)
	{
		return 1;
	}
    else
	{
		return 0;
	}
}


unsigned int queue_cnt(QUEUE *queue)
{
	if (queue->state == 1)
	{
		if (queue->tail > queue->head)
		{
			return queue->tail - queue->head;
		}
		else if (queue->tail < queue->head)
		{
			return queue->tail + queue->queue_len - queue->head;
		}
		else 
		{
			return queue->queue_len;
		}
	}
    else
	{
		return 0;
	}
}


unsigned char queue_push(QUEUE *queue, void *data)
{
	if (queue_full(queue))
	{
		if (queue->overwrite == 1)
		{
			memcpy(&ARRAY_AT(queue->arr, queue->item_size, queue->tail), data, queue->item_size);
			queue->tail++;
			queue->tail %= queue->queue_len;
			queue->head++;
			queue->head %= queue->queue_len;
			return 1;
		}
		else 
		{
			return 0;
		}
	}
	else
	{
		
		memcpy(&ARRAY_AT(queue->arr, queue->item_size, queue->tail), data, queue->item_size);
		queue->tail++;
		queue->tail %= queue->queue_len;			
		queue->state = 1;							
		queue->items_cnt++;
		return 1;
	}

	return 1;
}


unsigned char queue_pop(QUEUE *queue, void* data)
{
    if (queue_empty(queue))
    {
		return 0;
    }
    else
    {
		
		memcpy(data, &ARRAY_AT(queue->arr, queue->item_size, queue->head), queue->item_size); 
		queue->head++;
		queue->head %= queue->queue_len;			
		queue->items_cnt--;
		if(queue->head == queue->tail)				
		{
			queue->state = 0;						
		}
		return 1;
    }
}


void queue_clean(QUEUE *queue)
{
    queue->tail = 0;
    queue->head = 0;
    queue->state = 0;
	queue->items_cnt = 0;
}


void queue_free(QUEUE *queue)
{
    queue->tail = 0;
    queue->head = 0;
    queue->state = 0;
	queue->items_cnt = 0;
	queue->overwrite = 0;
	queue->queue_len = 0;
	queue->item_size = 0;
	free(queue->arr);
	queue->arr = NULL;
}

在和单一数据结构的顺序队列对比，push函数成员的赋值语句由

queue_array[queue_ctrl->tail++] = data;	

变成了

memcpy(&ARRAY_AT(queue->arr, queue->item_size, queue->tail), data, queue->item_size);
queue->tail++;

同样pop函数里面出队也发生了如此改变，原理上是没有变的。
注意：使用queue_free函数释放队列要再次初始化才可继续使用队列变量。

#include 
#include "queue.h"

typedef struct 
{
	char name[12];
	int heght;
	float weight;
}STUDENT;

void print_student(STUDENT student)
{
	printf("name: %s, height = %d, weight = %.2frn", student.name, student.heght, student.weight);
}

int main()
{
	int i = 0;
	QUEUE queue;
	QUEUE queue_stu;
	int data = 0;
	STUDENT student;
	int queue_len = 0;

	queue_init(&queue, sizeof(int), 10, 0);
	queue_init(&queue_stu, sizeof(STUDENT), 10, 0);

	for (i = 0; i < 11; i++)
	{
		data = i + 1;
		queue_push(&queue, &data);

		sprintf(student.name, "student%d", i);
		student.heght = 170 + i;
		student.weight = 60.5 + i;
		queue_push(&queue_stu, &student);
	}
	
	queue_len = queue.queue_len;
	for (i = 0; i < queue_len; i++)
	{
		if (queue_pop(&queue, &data) == 1)
		{
			printf("pop<%d> = %drn", i, data);
		}
	}

	queue_len = queue_stu.queue_len;
	for (i = 0; i < queue_len; i++)
	{
		if (queue_pop(&queue_stu, &student) == 1)
		{
			print_student(student);
		}
	}

	getchar();
	return 0;
}

测试代码和前面链式通用数据类型的基本一致。
运行结果：

综合对比，笔者比较推荐本文所介绍的队列形式。
最后的最后，本人才疏学浅，此代码仅供参考交流，本人如有叙述错误，麻烦各位指正，有什么好的建议欢迎留言。