【数据结构：队列】基本特点、定义及实现

数据结构：队列

队列：Queue 特点：先进先出，堆存储 【适合：头部取出，尾部添加】 允许在表的前端（front）进行删除操作 而在表的后端（rear）进行插入操作

先进先出（FIFO—first in first out）线性表 必须为其静态分配或动态申请一片连续的存储空间 并设置两个指针进行管理。 一个是队头指针front，它指向队头元素； 另一个是队尾指针rear，它指向下一个入队元素的存储位置

头文件

#pragma once

#include <stdio.h>
#include <malloc.h>

typedef int QuDataType;
// 链式结构：表示队列
typedef struct QListNode
{
          
   
	struct QListNode* _next;
	QuDataType _data;
}QueueNode;

// 队列的结构
typedef struct Queue
{
          
   
	QueueNode* _front;
	QueueNode* _rear;
}Queue;

// 初始化队列
void QueueInit(Queue* q);

// 队尾入队列
void QueuePush(Queue* q, QuDataType data);

// 队头出队列
void QueuePop(Queue* q);

// 获取队列头部元素
QuDataType QueueFront(Queue* q);

// 获取队列队尾元素
QuDataType QueueBack(Queue* q);

// 获取队列中有效元素个数
int QueueSize(Queue* q);

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);

// 销毁队列
void QueueDestroy(Queue* q);

实现

#include "Queue.h"
//一个数据入队列必须要先创建节点
QueueNode * BuyQueueNode(QuDataType x)    //创建节点并初始化此节点
{
          
   
	QueueNode * cur = (QueueNode *)malloc(sizeof(QueueNode));
	cur->_data = x;
	cur->_next = NULL;
	return cur;
}
void QueueInit(Queue* q) //初始化队列结构
{
          
   
	q->_front = NULL;
	q->_rear = NULL;
}
void QueuePush(Queue* q, QuDataType x)  //队列尾部入数据
{
          
   
	QueueNode * cur = BuyQueueNode(x);  //先把创建好的节点传过来
	if (q->_front == NULL)             //若是队列本身为空，队列里就只有这一个节点，又为队列头又为队列尾
	{
          
   
		q->_front = q->_rear = cur; 
	}
	else
	{
          
   
		q->_rear->_next = cur; //否则，链表尾插操作
		q->_rear = cur;
	}
}
void QueuePop(Queue* q)     //队列头部出数据
{
          
   
	if (q->_front == NULL)    //本身队列为空，不做操作
	{
          
   
		return;
    }
	QueueNode* tmp = q->_front->_next;   //先保留下一个节点，防止断链
	free(q->_front);
	q->_front = tmp;   //更新对列头部
}
QuDataType QueueFront(Queue* q)   //获取队列首部元素
{
          
   
	return q->_front->_data;
}
QuDataType QueueBack(Queue* q)//获取队列尾部元素
{
          
   
	return q->_rear->_data;
}
int QueueEmpty(Queue* q)   //判断队列是否为空
{
          
   
	return q->_front == NULL;   //为空，返回1
}
int QueueSize(Queue* q)  //获取队列中的元素个数
{
          
   
	QueueNode * cur;
	int count = 0;
	for (cur = q->_front; cur; cur = cur->_next)//循环遍历，计数即可
	{
          
   
		count++;
	}
	return count;
}
void QueueDestory(Queue* q)  //销毁队列
{
          
   
	if (q->_front == NULL)
	{
          
   
		return;
	}
	while (q->_front)
	{
          
   
		QueuePop(q);//对每一个元素迭代出队即可
	}
}