基于C语言的队列实现

->Gitee源码点击这里<-
队列也是线性表，队列在实现时用链表效率更高。

队列的数据处理遵循先进先出原则，所以设计队列的接口时，需要设计头删接口和尾插接口，才能达到先进进出的效果。

队列逻辑示意图

单链表实现，自然要有结点，所以我们要先创建单链表结点的结构体

typedef struct Node
{
	QDatatype data;
	struct Node* next;
};

光有结点还不足以表示队列，队列的核心在于队头和队尾，有了这两个元素才方便我们设计相应的数据处理接口，所以我们在定义一个队列的结构体

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

在主函数中创建一个队列类型的变量，即创建了一个队列，该变量下有两个指针成员，分别指向了队列的第一个结点和最后一个结点

int main()
{
	Queue myqueue;
}

队列创建后，需要对队列进行初始化，队列刚被创建时，队列中没有元素，所以头指针和尾指针都指向NULL

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

接着，我们需要设计数据处理接口

一、入队
我们需要做如下思考：
a.第一个数据结点入队时该作何处理？
第一个结点入队时，head和tail同时指向该结点
b.此后该如何处理？
当队中有结点之后，再入结点时，先让原来的tail指向的最后一个结点中的next存放新节点的地址，然后tail再指向新结点
示意图：

void QueuePush(Queue* pq, QDatatype data)
{
	//入队首先要创建一个新结点出来
	Node* newnode = (Node*)malloc(sizeof(Node));
	if (newnode == NULL)
	{
		printf("newnode malloc failed\n");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->data = data;

	//处理队头指针和队尾指针
	if (pq->tail == NULL) //如果队尾指向NULL，则说明队列中没有结点
	{
		pq->head = pq->tail = newnode;  //队列为空，则头指针和尾指针都指向新结点
	}
	else   
	{
		pq->tail->next = newnode; //先让尾指针指向的那个结点和新结点链接
		pq->tail = newnode;  //再让尾指针指向新结点
	}
}

二、出队
出队接口再队列为空时不可以调用，所以我们要先设计一个判空接口，来判断队列是否为空
判空接口：

void QueueIsEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;   //头指针或尾指针指向空就说明队列五结点
}

出队接口：
出队相当于链表的头删，即释放队首结点，再使head指向原队首结点的下一个结点
我们还需要做如下考虑：
a.队列中只剩一个结点时，该如何处理？
队列中最后一个结点被删除后，队列为空的状态，此时要把head和tail都重新置为空
示意图：

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueIsEmpty);
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		Node* second_node = pq->head->next;
		free(pq->head);
		pq->head = second_node;
	}
}

三、获取队首值
函数返回队列中队首的值

QDatatype QueueHead(Queue* pq)
{
	assert(pq);
	assert(!QueueIsEmpty);
	return pq->head->data;
}

四、获取队尾值
函数返回队列中队尾的值

QDatatype QueueTail(Queue* pq)
{
	assert(pq);
	assert(!QueueIsEmpty);
	return pq->tail->data;
}

五、返回队列长度

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	Node* cur = pq->head;
	while (cur != NULL)
	{
		size++;
		cur = cur ->next;
	}
	return size;
}

六、销毁队列
最重要的，只要涉及到动态开辟空间，使用完毕就需要释放空间

void QueueDestroy(Queue* pq)
{
	assert(pq);
	Node* cur = pq->head;
	while (cur != NULL)
	{
		Node* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

测试代码：

int main()
{
	Queue myqueue;
	QueueInit(&myqueue);
	printf("size = %d\n", QueueSize(&myqueue));
	for (int i = 0; i < 5; i++)
	{
		QueuePush(&myqueue, i);
	}
	printf("size = %d\n", QueueSize(&myqueue));

	for (int i = 0; i < 5; i++)
	{
		printf("%d ", QueueHead(&myqueue));
		QueuePop(&myqueue);
	}
	printf("\n");
	printf("size = %d\n", QueueSize(&myqueue));
	QueueDestroy(&myqueue);
}