【数据结构】从数据结构角度深入探究队列

队列是计算机科学中的一种基本数据结构,用于存储和管理数据。在计算机程序中,队列被广泛应用于任务调度、进程管理等场景。本文将介绍队列的概念、特点、常见操作以及应用。

队列的概念

你们在用电脑时有没有经历过,机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹。就当你失去耐心,打算reset时,突然它像酒醒了一样,把你刚才单击的所有操作全部都按顺序执行了一遍,这是因为操作系统在当时可能CPU一时忙不过来,等前面的事忙完后,后面多个指令需要通过一个通道输出,按先后次序排队执行造成的结果。所以在这操作系统中,是应用了一种数据结构来实现刚才提到的先进先出的排队功能,这就是队列。

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

  • 队列的特点

队列具有以下几个特点:

  1. 先进先出。最早进入队列的元素在队列中排在最前面,最后进入队列的元素排在最后面。
  2. 只能在队列的前端执行出队操作,在队列的后端执行入队操作。

在这里插入图片描述


队列的应用

队列在计算机程序中有很多应用场景,下面介绍其中几个常见的应用。

  1. 消息传递:
    在消息传递模型中,消息被发送到队列中等待接收方进行处理。发送方可以通过入队操作向队列发送消息,而接收方则通过出队操作从队列中获取消息。
  2. 缓存
    在网络通信中,缓存被广泛应用于加速数据传输。当一个请求到达时,它可能需要从远程服务器中获取数据,这个过程需要等待一定时间。为了避免每次请求都需要重新获取数据,可以将数据缓存在本地队列中。当下一次请求到达时,可以直接从队列中获取数据,避免了等待时间。
  3. 任务调度
    在许多系统中,任务必须按照一定的顺序进行处理。例如,操作系统中的进程调度就是一种任务调度。当一个进程被创建时,它会被添加到系统的任务队列中等待处理。调度器通过出队操作从队列中选择下一个要执行的进程,并将其分配给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;
}

队尾入队列

在这里插入图片描述

  • 详细步骤已放代码注释,以下是该入队列核心思路.
    1. 如果队列为空,将头指针和尾指针都指向新节点。
    2. 如果队列不为空,将尾指针指向新节点,并将前一个节点的指向下一个节点的指针更新为新节点。
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq); // 断言:如果传入的队列 pq 为空,程序将停止运行并提示错误。
    
    // 创建新节点 newnode 并为其分配内存空间。
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc failn"); // 如果分配空间失败,则程序将输出一条错误信息。
        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。
}

总结

  • 链式队列不需要移动元素,因此相比于顺序队列,链式队列的空间利用率更高。. 链式队列的缺点是需要额外的空间存储指针,因此相比于顺序队列,链式队列的空间复杂度更高。总之,链式队列是一种高效、灵活的队列数据结构,适用于需要频繁进行入队和出队操作的场景。

  • 队列是一种简单但非常有用的数据结构,掌握它的基本概念、操作和实现方式对于编程学习和刷题,后面的面试都非常重要。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>