本文共 2460 字，大约阅读时间需要 8 分钟。

系列文章目录

前言

一、队列的概念及结构

1.队列的概念

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

2.队列的结构

二、队列的实现

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

1.定义用链表表示的队列struct QueueNode

代码如下：

typedef int QDataType;struct QueueNode             //队列结构,用链表来表示{
   	struct QueueNode* next;	QDataType data;};

2.定义队列的队头、队尾指针struct Queue

代码如下：

struct Queue                //队列头尾指针{
   	struct QueueNode* head;	struct QueueNode* tail;};

3.队列的初始化函数QueueInit

代码如下：

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

4.队列的销毁函数QueueDestroy

遍历队列，记住free前先存储下一个节点的地址。

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

5.队列的队尾入数据函数QueuePush

先开辟一个结点，在分两种情况，一种情况队列一个节点都没有，那可以直接当节点，第二种情况队列一开始有节点，尾插数据即可。

void QueuePush(struct Queue* pq, QDataType x)   //队尾入数据{
   	assert(pq);	struct QueueNode* newnode = (struct QueueNode*)malloc(sizeof(struct QueueNode));	if (newnode == NULL)	{
   		printf("开辟失败!\n");		exit(-1);	}	newnode->data = x;	newnode->next = NULL;	if (pq->tail == NULL)   //无节点	{
   		pq->head = pq->tail = newnode;	}	else	{
   		pq->tail->next = newnode;		pq->tail = newnode;	}}

6.队列的队头出数据函数QueuePop

代码如下：

void QueuePop(struct Queue* pq){
   	assert(pq);	assert(!QueueEmpty(pq));	if (pq->head->next==NULL)  //只有一个节点	{
   		free(pq->head);		pq->head = pq->tail = NULL;	}	else	{
   		struct QueueNode* next = pq->head->next;		free(pq->head);		pq->head = next;	}}

7.队列的取出队头数据函数QueueFront

记住每次取数据前判断队列是否为空，不为空才进行下一步。

QDataType QueueFront(struct Queue* pq){
   	assert(pq);	assert(!QueueEmpty(pq));	return pq->head->data;}

8.队列的取出队尾数据函数QueueBack

记住每次取数据前判断队列是否为空，不为空才进行下一步。

QDataType QueueBack(struct Queue* pq){
   	assert(pq);	assert(!QueueEmpty(pq));	return pq->tail->data;}

9.队列是否为空函数QueueEmpty

代码如下：

bool QueueEmpty(struct Queue* pq){
   	assert(pq);	return pq->head == NULL;}

10.队列的长度函数QueueSize

代码如下：

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

总结

以上就是今天要讲的内容，本文仅仅简单介绍了队列的使用，对于队列提供了一些简便方法帮助我们解题，能使我们快速便捷地处理数据的函数和方法。另外这个结构虽然相比链表更简单，使用代码实现起来更容易写，但我们也要认真学习，以后会发现队列结构会带来很多优势，我们务必掌握。另外，如果有需要源码的私信我即可。还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。

转载地址：http://yke.baihongyu.com/