队列是计算机科学中的一种基本数据结构，用于存储和管理数据。在计算机程序中，队列被广泛应用于任务调度、进程管理等场景。本文将介绍队列的概念、特点、常见操作以及应用。
队列的概念
你们在用电脑时有没有经历过，机器有时会处于疑似死机的状态，鼠标点什么似乎都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算reset时，突然它像酒醒了一样，把你刚才单击的所有操作全部都按顺序执行了一遍,这是因为操作系统在当时可能CPU一时忙不过来，等前面的事忙完后，后面多个指令需要通过一个通道输出，按先后次序排队执行造成的结果。所以在这操作系统中，是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。
- 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头.
- 队列的特点
队列具有以下几个特点：
- 先进先出。最早进入队列的元素在队列中排在最前面，最后进入队列的元素排在最后面。
- 只能在队列的前端执行出队操作，在队列的后端执行入队操作。
队列的应用
队列在计算机程序中有很多应用场景，下面介绍其中几个常见的应用。
- 消息传递:
在消息传递模型中，消息被发送到队列中等待接收方进行处理。发送方可以通过入队操作向队列发送消息，而接收方则通过出队操作从队列中获取消息。- 缓存
在网络通信中，缓存被广泛应用于加速数据传输。当一个请求到达时，它可能需要从远程服务器中获取数据，这个过程需要等待一定时间。为了避免每次请求都需要重新获取数据，可以将数据缓存在本地队列中。当下一次请求到达时，可以直接从队列中获取数据，避免了等待时间。- 任务调度
在许多系统中，任务必须按照一定的顺序进行处理。例如，操作系统中的进程调度就是一种任务调度。当一个进程被创建时，它会被添加到系统的任务队列中等待处理。调度器通过出队操作从队列中选择下一个要执行的进程，并将其分配给CPU执行。
- 总的来说队列是计算机科学中非常重要的一种数据结构，具有先进先出的特点。队列通过入队和出队操作管理数据，常见的应用场景包括任务调度、消息传递和缓存等。对于程序员来说，了解队列的基本概念和常见操作是非常必要的。
队列的存储结构
队列可以使用数组或者链表的结构来实现，那哪一个存储结构更加优呢？下面我们来分析他们在队列中存储各自的优缺点。
- 数组存储结构的优点：
1 . 数组在内存中是连续存储的，因此访问元素时速度较快。CPU高速缓存命中率会更高。
2 . 数组实现相对简单，不需要额外的指针来维护元素之间的关系。- 数组存储结构的缺点
1 . 需要事先确定队列的最大长度，这可能会导致性能下降。
2 . 需要移动元素来保持队列的顺序.
- 链式存储的优点
1 . 不需要事先确定队列的最大长度，可以动态扩展.
2 . 插入和删除操作只需要修改指针，不需要移动元素.
3 . 可以实现多个队列共享一个链表- 链式存储的缺点
1 . CPU高速缓存命中率会更低,不是连续存储的，因此访问元素时速度较慢。
2 .实现相对复杂。
- 终言： 使用链表的结构实现更优一些,因为数据存储有一个致命的缺点就是大量挪动元素。
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针head指向链队列的头结点，而队尾tail尾指针指向终端结点.。
// 定义队列节点结构体
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next; // 指向下一个节点的指针
QDataType data; // 节点数据
}QNode;
// 定义队列结构体
typedef struct Queue
{
QNode* phead; // 队列头指针，指向第一个节点
QNode* ptail; // 队列尾指针，指向最后一个节点
int size; // 队列大小，即节点数量
}Queue;
在这个链表中，每个节点包含两个成员变量：指向下一个节点的指针和节点数据。队列结构体中包含头指针、尾指针和节点数量三个成员变量。头指针指向队列的第一个节点，尾指针指向队列的最后一个节点，节点数量表示队列中节点的数量。由于是单向链表，所以只需要维护头指针和尾指针就可以实现入队和出队操作。
队列接口的实现
队列的初始化
- 先把队列元素全部置空，size置0.
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
队尾入队列
- 详细步骤已放代码注释,以下是该入队列核心思路.
- 如果队列为空，将头指针和尾指针都指向新节点。
- 如果队列不为空，将尾指针指向新节点，并将前一个节点的指向下一个节点的指针更新为新节点。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq); // 断言：如果传入的队列 pq 为空，程序将停止运行并提示错误。
// 创建新节点 newnode 并为其分配内存空间。
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail\n"); // 如果分配空间失败，则程序将输出一条错误信息。
return;
}
// 设置新节点的数据和指针值。
newnode->data = x; // 新节点中储存的数据值为变量 x。
newnode->next = NULL; // 新节点的指向下一个节点的指针初始值设为 NULL。
// 将新节点加入队列末尾。
if (pq->ptail == NULL) // 如果队列为空（没有节点），则头指针和尾指针均指向新节点。
{
assert(pq->phead == NULL); // 确认队首指针也为 NULL。
pq->phead = pq->ptail = newnode;
}
else // 否则，仅将尾指针指向新节点，并将前一个节点的指向下一个节点的指针更新为新节点。
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++; // 队列长度加一。
}
队头出队列
- 详细步骤已放代码注释,以下是该入队列核心思路.
1 . 出队列前要判断该队列是否为空.
2 . 如果队列中只有一个节点，即头指针和尾指针指向同一个节点，则释放头结点.并将将头指针和尾指针均置为NULL.
3 . 如果队列中有不止一个节点，即头指针和尾指针指向不同的节点，则保存头结点的下一个节点，释放头结点，将头指针指向下一个节点.
void QueuePop(Queue* pq)
{
assert(pq); // 判断参数pq是否为空
assert(!QueueEmpty(pq)); // 判断队列是否为空
if (pq->phead->next == NULL) // 如果队列中只有一个节点
{
free(pq->phead); // 释放头结点
pq->phead = pq->ptail = NULL; // 将头指针和尾指针均置为NULL
}
else // 如果队列中有不止一个节点
{
QNode* next = pq->phead->next; // 保存头结点的下一个节点
free(pq->phead); // 释放头结点
pq->phead = next; // 将头指针指向下一个节点
}
pq->size--; // 减小队列的大小
}
获取队列头部元素
- 需要注意的是要判断该队列是否为空.如不为空，则返回队列头节点的数据域。
QDataType QueueFront(Queue* pq)
{
assert(pq); // 判断参数pq是否为空
assert(!QueueEmpty(pq)); // 判断队列是否为空
return pq->phead->data; // 返回头结点所指向节点的数据值
}
获取队列队尾元素
- 需要注意的是要判断该队列是否为空…如不为空，则返回队列尾节点的数据域。
QDataType QueueBack(Queue* pq)
{
assert(pq); // 判断参数pq是否为空
assert(!QueueEmpty(pq)); // 判断队列是否为空
return pq->ptail->data; // 返回尾结点所指向节点的数据值
}
获取队列中有效元素个数
- 返回队列的成员变量size的值即可.
int QueueSize(Queue* pq)
{
assert(pq); // 判断参数pq是否为空
return pq->size; // 返回队列的成员变量size的值
}
检测队列是否为空
- 判断队列的成员变量size是否为0，如果为0则说明队列为空，返回true，否则返回false。
bool QueueEmpty(Queue* pq)
{
assert(pq); // 判断参数pq是否为空
return pq->size == 0; // 如果队列为空，返回true，否则返回false
}
销毁队列
- 详细步骤已放代码注释，需要注意的是每次销毁节点时，要保存它下一个节点。
void QueueDestroy(Queue* pq)
{
assert(pq); // 判断参数pq是否为空
QNode* cur = pq->phead; // 定义一个指针cur指向队列头结点pq->phead。
while (cur) // 利用while循环遍历链表
{
QNode* next = cur->next; // 定义一个指针next指向当前节点的下一个节点。
free(cur); // 释放当前节点的内存。
cur = next; // 将cur指向next节点。
}
pq->phead = pq->ptail = NULL; // 将队列头结点和尾结点置为NULL。
pq->size = 0; // 将队列大小设置为0。
}
总结
-
链式队列不需要移动元素，因此相比于顺序队列，链式队列的空间利用率更高。. 链式队列的缺点是需要额外的空间存储指针，因此相比于顺序队列，链式队列的空间复杂度更高。总之，链式队列是一种高效、灵活的队列数据结构，适用于需要频繁进行入队和出队操作的场景。文章来源：https://www.toymoban.com/news/detail-458082.html
-
队列是一种简单但非常有用的数据结构，掌握它的基本概念、操作和实现方式对于编程学习和刷题，后面的面试都非常重要。文章来源地址https://www.toymoban.com/news/detail-458082.html
到了这里，关于【数据结构】从数据结构角度深入探究队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
