搞懂数据结构——队列基本功能的实现

🎊这篇文章，木羽会带大家了解第四种线性表——队列的相关概念，当然，还有队列基本功能的实现

目录

• 
  

  一、概念及结构

• • 🎡概念
  • 🎡结构
• 
  

  二、基本功能的实现

• • 🎡头文件
  • 🎡函数声明
  • 🎡初始化队列
  • 🎡入队列
  • 🎡出队列
  • 🎡显示队头元素
  • 🎡显示队尾元素
  • 🎡判断队列长度
  • 🎡判断队列是否为空
  • 🎡清空队列
  • 🎡销毁队列

一、概念及结构 🎡概念

队列也是一种特殊的线性表，只允许在一端进行插入数据的 *** 作，在另一端进行删除数据的 *** 作，由先进先出（FIFO）的原则，其中进行插入 *** 作（入队列）的一端叫做队尾，进行删除 *** 作（出队列）的一端叫做队头。

🎡结构

队列当然也可以用数组做链表来实现，但与栈相反，队列用链表来实现更好一些，因为在删除数据元素时，需要在队头进行，若使用数组实现，需要大量移动数据，会使效率变低。

所以接下来我会用单链表来实现队列的基本功能。

队列和日常生活中的排队是一个道理，先来的先出，后来的后出。

二、基本功能的实现 🎡头文件

#include
#include
#include
#include

typedef int QDateNode;

typedef struct QueueNode  //定义结点
{
	struct QueueNode* next;
	QDateNode date;
}QNode;

typedef struct Queue  //定义头尾指针
{
	QNode* head;
	QNode* tail;
}Queue;

🎡函数声明

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

//入队列
void QueuePush(Queue* Q,QDateNode e);

//出队列
void QueuePop(Queue* Q);

//输出队头元素
QDateNode QueueFront(Queue Q);

//输出队尾元素
QDateNode QueueBack(Queue Q);

//判断队列长度
int QueueSize(Queue* Q);

//判断队列是否为空
bool QueueEmpty(Queue* Q);

//清空队列
void QueueClear(Queue* Q);

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

🎡初始化队列

//初始化队列
void QueueInit(Queue* Q)
{
	assert(Q);
	Q->head = Q->tail = NULL;
}

🎡入队列

//入队列
void QueuePush(Queue* Q,QDateNode e)
{
	assert(Q);
	QNode* newnode;
	newnode = (QNode*)malloc(sizeof(QNode)); //开辟新节点
	if (newnode == NULL)  //开辟失败则退出
	{
		printf("malloc is fail!");
		exit(-1);
	}
	newnode->date = e;   //数据域赋值
	newnode->next = NULL;   //因为是队尾入，所以指针域置为空
	if (Q->tail == NULL)    //若为空队列
		Q->head = Q->tail = newnode;
	else
	{
		Q->tail->next = newnode;
		Q->tail = newnode;
	}
	printf("The Queuepush is successful!\n");
}

🎡出队列

//出队列
void QueuePop(Queue* Q)
{
	assert(Q);
	assert(Q->head);
	if (Q->head->next == NULL)   //若队列中只有一个元素
	{
		free(Q->head);
		Q->head = Q->tail = NULL;
	}
	else
	{
		QNode* node= Q->head->next;
		free(Q->head);
		Q->head = node;
	}
	printf("The Queuepop is successful!\n");
}

🎡显示队头元素

//输出队头元素
QDateNode QueueFront(Queue Q)  //因为只是想查看一下元素，所以不需要改变队列
{
	assert(&Q);
	QNode* cur = Q.head;
	return(cur->date);
}

🎡显示队尾元素

//输出队尾元素
QDateNode QueueBack(Queue Q)
{
	assert(&Q);
	QNode* cur = Q.tail;
	return(cur->date);
}

🎡判断队列长度

//判断队列长度
int QueueSize(Queue* Q)
{
	assert(Q);
	int size=0;
	QNode* cur=Q->head;
	while (cur)    //遍历队列，每次经过一个结点size加一
	{
		cur = cur->next;
		size++;
	}
	return size;
}

🎡判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* Q)
{
	assert(Q);
	return(Q->head==NULL);
}

🎡清空队列

//清空队列
void QueueClear(Queue* Q)
{
	Q->head = Q->tail = NULL;
}

🎡销毁队列

//销毁队列
void QueueDestroy(Queue* Q)
{
	assert(Q);
	QNode* cur = Q->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	Q->head = Q->tail = NULL;
}