数据结构实战

        本节我们使用链表来实现一个队列。队列的特点是先进先出（FIFO）。普通队列的实现非常简单，下面是队列的实现代码：

#include "typedef.h"

//节点
typedef struct s_node
{
	void *data;
	struct s_node *next;
} s_node;

//队列数据结构
typedef struct
{
	//元素大小
	int ele_size;
	//头节点
	s_node *header;
	//脚节点
	s_node *footer;
	//用于释放节点数据的回调函数
	void (*free_data)();
	//用于访问节点数据内容的回调函数
	void (*visit_data)(void *data);
} s_queue;

//构建一个队列
bool init_queue(s_queue *queue, int ele_size, void (*free_data)(), void (*visit_data)())
{
	if (queue == null)
	{
		return false;
	}
	queue->ele_size = ele_size;
	queue->free_data = free_data;
	queue->visit_data = visit_data;
	queue->header = null;
	queue->footer = null;
	return true;
}

//销毁队列
bool destroy_queue(s_queue *queue)
{
	if (queue == null)
	{
		return false;
	}

	if (queue->header == null)
	{
		return true;
	}

	clear_queue(queue);

	return true;
}

//清空队列中所有元素
bool clear_queue(s_queue *queue)
{
	if (queue == null)
	{
		return false;
	}

	//从头节点开始释放
	s_node *p = queue->header;
	while (p != null)
	{
		//释放内存
		queue->free_data(p->data);
		s_node *t = p;
		p = p->next;
		free(t);
	}
	queue->header = null;
	queue->footer = null;

	return true;
}

//在队列尾追加一个元素
bool queue_insert(s_queue *queue, void *e)
{
	if (queue == null || e == null)
	{
		return false;
	}

	//申请新节点内存
	s_node *p_new = (s_node *) malloc(sizeof(s_node));
	p_new->data = e;
	p_new->next = null;

	if (queue->footer == null)
	{
		queue->header = p_new;
		queue->footer = p_new;

		return true;
	}

	queue->footer->next = p_new;
	queue->footer = p_new;

	return true;
}

//在队列头删除一个元素
bool queue_delete(s_queue *queue)
{
	if (queue == null || queue->header == null)
	{
		return false;
	}

	s_node *p_del = queue->header;
	queue->header = queue->header->next;
	if (queue->footer == p_del)
	{
		queue->footer = queue->header->next;
	}
	queue->free_data(p_del);

	return true;
}

//对每个元素执行visit操作
bool queue_visit(s_queue *queue)
{
	if (queue == null || queue->header == null)
	{
		return false;
	}

	//顺序访问每一个元素
	s_node *p = queue->header;
	while (p != null)
	{
		queue->visit_data(p->data);
		p = p->next;
	}
	return true;
}

        再来写一个main函数来测试队列：

#include "queue.h"

void free_int(void *data)
{
	free(data);
}

void print_int(void *data)
{
	printf("%d\n", *((int *) data));
}

typedef struct
{
	int no;
	int age;
	char *name;
} student;

void print_stu(void *data)
{
	student *stu = (student *) data;
	printf("no:%d age:%d name:%s\n", stu->no, stu->age, stu->name);
}

void free_stu(void *data)
{
	student *stu = (student *) data;
	free(stu->name);
	free(stu);
}

int main(int argc, char **args)
{
	//用于存放int型数据的队列
	s_queue queue_int;
	//释放内存函数与访问函数均是int型
	init_queue(&queue_int, sizeof(int), free_int, print_int);
	//插入数据
	for (int i = 0; i < 5; ++i)
	{
		int *e = (int *) malloc(sizeof(int));
		*e = i;
		queue_insert(&queue_int, e);
	}
	//显示queue中所有数据内容
	queue_visit(&queue_int);
	//销毁queue
	destroy_queue(&queue_int);

	printf("\n");

	//用于存放student型数据的queue
	s_queue queue_stu;
	//释放内存函数与访问函数均是student型
	init_queue(&queue_stu, sizeof(student), free_stu, print_stu);

	//在队列尾插入数据
	student *stu1 = (student *) malloc(sizeof(student));
	stu1->no = 15100101;
	stu1->age = 23;
	stu1->name = (char *) malloc(20);
	memcpy(stu1->name, "lidq", 20);
	queue_insert(&queue_stu, stu1);
	//在队列尾插入数据
	student *stu2 = (student *) malloc(sizeof(student));
	stu2->no = 15100102;
	stu2->age = 21;
	stu2->name = (char *) malloc(20);
	memcpy(stu2->name, "zhaoy", 20);
	queue_insert(&queue_stu, stu2);
	//在队列尾插入数据
	student *stu3 = (student *) malloc(sizeof(student));
	stu3->no = 15100103;
	stu3->age = 22;
	stu3->name = (char *) malloc(20);
	memcpy(stu3->name, "liuzh", 20);
	queue_insert(&queue_stu, stu3);

	//显示队列中所有内容
	queue_visit(&queue_stu);

	printf("\n");

	//在队列头删除元素
	queue_delete(&queue_stu);
	//显示队列中所有内容
	queue_visit(&queue_stu);

	//销毁队列
	destroy_queue(&queue_stu);

	return 0;
}

        运行结果：

0
1
2
3
4

no:15100101 age:23 name:lidq
no:15100102 age:21 name:zhaoy
no:15100103 age:22 name:liuzh

no:15100102 age:21 name:zhaoy
no:15100103 age:22 name:liuzh

        本例代码：

code path   chapter.02/e.g.2.4/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure