数据结构-队列

链式队列

[TOC]

一：定义

队列属于一种线性结构，队列采用fifo(先进先出)，要求所有数据从队列的前端进行输出，后端进行输入

二：队列结构定义

/*
	队列结构定义
*/
typedef struct Node
{
	int data;                    // 数据域  假设当前存储的是int 类型的数据
	struct Node* next;                  // 指针域，指向下一个节点

}Node,*Queue_ptr;


typedef struct
{
	Queue_ptr fornt;            //  队列头指针
	Queue_ptr rear;             //  队列尾巴指针
}Queue_type,*Queue_type_str;

三 ：队列相关操作函数实现

3.1 初始化一个队列

// 初始化一个队列
void init_queue(Queue_type_str *queue)
{
	if (*queue != NULL) { printf("非空初始化"); return; }          //  当前的队列已经初始化
	*queue = (Queue_type *)malloc(sizeof(Queue_type));           //  分配内存
	printf("*queue == %p\r\n", *queue);
	if (*queue == NULL) { return; }
	(*queue)->rear = (*queue)->fornt = (Node*)malloc(sizeof(Node));   // 头节点和尾节点指向同一个节点，表示为空，同时该节点不存储数据
	(*queue)->fornt->next = NULL;
	printf("队列初始化成功\r\n");
}

3.2 入列

// 入列操作
/*
*   因为入列只需要从队列尾操作数据，所以只需要操作 rear 指针
*/
void In_queue(Queue_type_str queue,int data)
{
	Node* temp_node = NULL;          // 创建一个入队列的节点待用。稍后会把这个队列插入到指定的队列中
	if (!queue) { printf("In_queue 使用为初始化的队列\r\n"); return; }          // 未初始化的队列不进行操作
	temp_node = (Node*)malloc(sizeof(Node));
	if (!temp_node) { printf("数据入列失败\r\n"); return; };
	temp_node->data = data;
	temp_node->next = NULL;          // 将节点的数据进行格式化
	queue->rear->next = temp_node;   // 将上一节点的指针域指向尾端
	queue->rear = temp_node;         // 队列尾指针永远指向最后一个
	
}

3.3 出列

// 出队列
void Out_queue(Queue_type_str queue, int *data)
{
	Node* temp_node = NULL;
	if (!queue) { return; }          // 未初始化的队列不进行操作
	if (queue->fornt == queue->rear) { printf("空队列\r\n"); } // 判断是否为空
	temp_node = queue->fornt->next;                   // 指向第一个数据
	*data = temp_node->data;
	queue->fornt->next = temp_node->next;             // 指向下一个数据
	if (!temp_node->next)                             // 如果是末尾数据
	{
		queue->rear = queue->fornt;
	}
	free(temp_node);                                  // 释放当前节点

}

3.4 销毁列

// 删除队列
void Delete_queue(Queue_type_str* queue)
{
	Node* temp_node = NULL;
	if (!(*queue)) {return; }          // 未初始化的队列不进行操作
	temp_node = (*queue)->fornt->next;        // 从头节点开始销毁
	while ((*queue)->fornt->next)
	{
		(*queue)->fornt->next = temp_node->next;
		free(temp_node);
		temp_node = (*queue)->fornt->next;
	}
	free((*queue)->fornt);
	free((*queue));
	(*queue) = NULL;
}

3.5 遍历列

该部分用于应用测试和验证

// 遍历当前队列
void ergodic_queue(Queue_type_str queue)
{
	int num = 0;
	Node* temp_node = NULL;
	if (!queue) { printf("队列不存在\r\n");  return; }          // 未初始化的队列不进行操作
	temp_node = queue->fornt->next;        // 从头节点开始遍历
	printf("node data:");
	while (temp_node)
	{
		num++;
		printf("%d ", temp_node->data);
		temp_node = temp_node->next;
	}
	printf("-------\r\n");
	printf("total num = %d\r\n",num);
}

四：应用举例

int main()
{
	int may_tet = 0;
	Queue_type_str my_queue1 = NULL;
	init_queue(&my_queue1);                        // 初始化一个队列
	for (int i = 0;i<100;i++)                      // 入列测试
	{
		In_queue(my_queue1, i);
	}
	ergodic_queue(my_queue1);                      // 遍历
	In_queue(my_queue1,666);                       // 再次入列
	ergodic_queue(my_queue1);                      // 再次遍历
	printf("OUT:");
	for (int aa = 0;aa<50;aa++)
	{
		Out_queue(my_queue1, &may_tet);                 // 出列测试
		printf("%d ", may_tet);
	}
	printf("\r\n");
	ergodic_queue(my_queue1);                      // 再次遍历 验证
	Delete_queue(&my_queue1);                      // 删除该队列
	ergodic_queue(my_queue1);                      // 再次遍历 验证

	return 0;
}

赏

谢谢你请我吃糖果