数据结构—队列的C语言实现

目录

一、队列的概念及结构

二、结构体定义

三、初始化队列

四、队尾入队列

五、队头出队列

六、获取队头部元素

七、获取队尾部元素

八、获取队列中有效元素个数

九、检测队列是否为空

十、销毁队列

一、队列的概念及结构

1.队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

2.队列的实现
队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，就需要挪动数据，效率会比较低。

二、结构体定义

链式结构：表示队列

typedef int QDataType;

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

队列的结构：

表示队列的结构体内定义两个链表结构指针，head指向队列的头，tail指向队列的尾

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

三、初始化队列

队列的结构体内部两个链表指针head和tail初始化为NULL

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

四、队尾入队列

动态开辟一个链表节点，用来从队列尾入队列；需要判断入队列的时候队列是否为空，若队列为空，即pq->tail=pq->head=NULL，就不能将新开辟的节点放到pq->tail->next位置，这时就需要将新开辟的节点作为最开始队列的头和尾，之后入队列的新节点就放到pq->tail->tail的位置，然后再让pq->tail指向这个新节点；依次这样入队列，只是队列为空的情况要特殊考虑

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}
	newNode->val = x;
	newNode->next = NULL;
	if (pq->head == NULL)    //也可以用pq->tail==NULL为判断条件
	{
		assert(pq->tail == NULL);        
         //理论上pq->tail和pq->head不可能一个不为NULL另一个为NULL，只能同时为NULL或者同时不为 
         //NULL；避免因为其他原因使它们不同时为空，加一个断言方便检查错误
        pq->head = pq->tail = newNode; 
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

五、队头出队列

队列头数据出队列之后就要删除队列的头，让队列头指向下一个位置；首先要判断pq->head->next是否为空，若为空则说明队列只有一个数据，出队列之后，对头不能再指向下一个位置，然后释放掉这一个节点空间，再将队列的头置NULL同时也可以将队列尾置NULL；反之不为空，则先记录队列头的下一个位置，然后free队列头节点，更新队列头，pq->head就指向删除之前队列头节点的下一个位置

void QueuePop(Queue* pq)
{
	assert(pq);

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

六、获取队头部元素

首先需要断言队列是否为空，为空则获取不了队头部元素；然后再返回队列头指向的元素

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->val;
}

七、获取队尾部元素

首先需要断言队列是否为空，为空则获取不了队尾部元素；然后再返回队列尾指向的元素

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);

	return pq->tail->val;
}

八、获取队列中有效元素个数

遍历一遍队列，累加计算队列中有效元素个数

size_t QueueSize(Queue* pq)
{
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

九、检测队列是否为空

判断pq->head是否为NULL或者判断pq->tail是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}

十、销毁队列

从队列的头依次向后释放节点空间，最后将pq->tail和pq->head置NULL

void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}