全文目录

• 引言
• 队列
• • 介绍
  • 接口实现
  • • 队列的初始化与销毁
    • 判断队列是否为空
    • 队尾入队列
    • 队头出队列
    • 访问队头元素
    • 访问队尾元素
• 总结

引言

在上一篇文章中，我们了解了栈这种数据结构，它的存储特点为先进后出。并且用数组实现了栈：
戳我康栈的详解哦

在本篇文章中，将介绍另一种线性结构：队列

队列

介绍

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

接口实现

在实现栈时，由于它只需要能访问栈顶的元素，所以采用数组实现会比较高效。但是对于队列来说，需要从队头出元素，如果使用数组实现的话就会比较麻烦，所以采用单链表来实现队列：

我们可以将想要存储的数据类型重命名为STDataType，这样在想要改变类型时就会很方便：

typedef int QDataType;

与之前实现链表的思路相同，我们首先需要实现链表结点的结构：

//每一个结点
typedef struct QListNode
{struct QListNode* pNext;QDataType data;
}QNode;

对于队列，我们可以与链表有所不同：
由于单链表在访问最后一个元素时，也需要遍历链表，会比较麻烦。所以我们可以再创建一个结构体类型：存放链表的头结点地址front与尾结点地址rear，另外也可以再存储一个变量size来表示链表的长度：

// 队列的结构
typedef struct Queue
{QNode* front;QNode* rear;int size;
}Queue;

在动态开辟一个Queue*型的变量后，就可以来实现各种接口来对队列的指针pq进行操作了：

Queue* pq = (Queue*)malloc(sizeof(Queue));

队列的初始化与销毁

初始化队列时，由于还不需要存储数据，所以不需要为结点开辟空间。
只需要将pq中的头尾结点地址front与rear初始化为NULL，并且将size初始化为0即可：

// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq->front = NULL;pq->rear = NULL;pq->size = 0;
}

销毁队列时，与销毁单链表相同，需要销毁链表的每一个结点：
当依次销毁单链表的每一个节点时，我们需要两个指针变量cur与next。通过这两个指针变量，next可以在cur被销毁前记录cur->next的值，从而实现在销毁cur指向的空间后，可以通过next访问到下一个结点而继续进行销毁操作。
依次循环，当cur为NULL时终止，实现销毁每一个结点；

销毁结束后，再将front、rear、size的值全改为0；

最后，再将我们之前动态开辟的结构体空间pq释放即可：

// 销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->front;QNode* next = pq->front;while (cur){next = cur->pNext;free(cur);cur = next;}pq->front = NULL;pq->rear = NULL;pq->size = 0;free(pq);
}

判断队列是否为空

在检测队列是否为空时，只需要判断front是否为NULL即可：
当front为NULL时，即队列为空，返回真；
当front不为NULL时，队列不为空，返回假：

// 检测队列是否为空，如果为空返回非0,非空返回0
int QueueEmpty(Queue* pq)
{assert(pq);return pq->front == NULL;
}

队尾入队列

队尾入队列时，与链表的尾插类似，但在我们将链表的尾结点地址rear记录下来后，单链表的尾插就会变得很容易：
在创建并初始化新结点后，我们只需要将pq->rear->pNext 改为 newnode，即连接尾结点与新结点；再将pq->rear 改为newnode，即使rear继续指向尾结点即可：

但是，当队列中没有元素时，尾插后需要将front的指针改为指向新结点，即此时新结点为首结点；
最后，size++：

// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode);newnode->data = data;newnode->pNext = NULL;if (QueueEmpty(pq)){pq->front = newnode;pq->rear = newnode;}else{pq->rear->pNext = newnode;pq->rear = newnode;}pq->size++;
}

队头出队列

在头删之前，首先要判断队列是否为空，若队列为空，就不能再继续删除了；

队头出队列时，与单链表的头删类似：
只需要将头结点的空间释放，然后front指针向后移动一个结点即可。但是由于释放front指向的空间后，就不能通过它来访问下一个结点了，所以我们可以先用cur存储队列中的第二个元素，释放结束后，再将front改为cur，使front继续指向头节点：

但是，当队列中只剩一个元素时，将它释放后rear指针将成为野指针，所以要将front与rear指针全部初始化为NULL；
最后，size–：

// 队头出队列
void QueuePop(Queue* pq)
{assert(pq && QueueEmpty(pq) == 0);QNode* cur = pq->front->pNext;if (cur)//当队列中只有一个元素时，需要将头与尾改为NULL{free(pq->front);pq->front = cur;}else{free(pq->front);pq->front = NULL;pq->rear = NULL;}pq->size--;
}

访问队头元素

访问队头元素，只需要返回front指向结点的data成员即可：

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq && QueueEmpty(pq) == 0);return pq->front->data;
}

访问队尾元素

访问队尾元素，只需要返回rear指向结点的data成员即可：

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq && QueueEmpty(pq) == 0);return pq->rear->data;
}

总结

到此，关于队列的介绍以及接口实现就就结束了
后面会有一些关于栈和队列的OJ题目详解，欢迎大家持续关注哦

如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题，欢迎大家在评论区提出

如果本文对你有帮助，希望一键三连哦

希望与大家共同进步哦