新开传奇网站发布网单/站长工具使用方法

大家好，我是小卡皮巴拉 

文章目录

目录

引言

一.队列的基本概念

1.1 队列的定义

1.2 队列的特性

1.3 队列的基本操作

二.队列的实现方式

2.1 基于链表的队列

2.2 基于数组的队列

三.基于链表的队列实现

定义链表队列的结构

初始化

入队列——向队列中插入数据

 队列判空

队列有效元素个数

出队列——从队列中删除数据

取队头数据

取队尾数据

销毁队列

兄弟们共勉！！！   

---

 

每篇前言

博客主页：小卡皮巴拉 

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

引言

想象一下你在超市排队结账，每个人都按顺序等待，先到的先结账。这种排队的方式，其实就是数据结构中的“队列”。队列，简单来说，就是数据按照到达的顺序排队，先到的先处理。

在编程中，队列帮助我们管理一系列的任务或数据，确保它们按照正确的顺序被执行或处理。无论是处理用户请求、管理打印任务，还是在算法中进行搜索，队列都发挥着重要的作用。

现在，让我们一起探索这个简单而强大的数据结构，了解它的原理和应用，看看它是如何在编程世界中为我们服务的。

一.队列的基本概念

1.1 队列的定义

队列（Queue）是一种特殊的数据结构，它按照元素进入的顺序进行排列，并遵循先进先出（FIFO, First In First Out）的原则。队列可以被看作是一个有序的元素集合，其中元素的添加（入队）发生在集合的一端（通常称为“队尾”），而元素的移除（出队）则发生在另一端（通常称为“队头”）。

1.2 队列的特性

1. 先进先出（FIFO）：这是队列最显著的特点。元素按照加入队列的顺序被处理，即最早进入队列的元素会最先被移除。

2. 有序性：由于FIFO原则，队列中的元素始终保持有序状态。

3. 动态性：队列的大小可以动态变化。在需要时，可以向队列中添加新元素（入队），也可以从队列中移除元素（出队）。

4. 边界条件：队列有两个重要的边界条件——空队列和满队列（对于有限队列）。空队列表示队列中没有元素，而满队列表示队列已达到其最大容量，无法再添加新元素。然而，在实际应用中，更常见的是通过动态调整或循环使用空间来避免真正的“满”状态。

1.3 队列的基本操作

1. 入队（Enqueue）：向队列中添加一个新元素的操作。通常发生在队尾。

   • 操作结果：队列的长度增加1。
   • 时间复杂度：在大多数情况下，入队操作的时间复杂度为O(1)，即常数时间。

2. 出队（Dequeue）：从队列中移除一个元素的操作。通常发生在队头。

   • 操作结果：队列的长度减少1，并返回被移除的元素。
   • 时间复杂度：同样地，在大多数情况下，出队操作的时间复杂度也为O(1)。

3. 查看队头元素（Front/Peek）：获取队列头部的元素但不移除它。

   • 操作结果：返回队列头部的元素。
   • 时间复杂度：在大多数情况下，查看队头元素的时间复杂度为O(1)。

4. 检查队列是否为空（IsEmpty）：判断队列中是否包含元素。

   • 操作结果：返回一个布尔值，表示队列是否为空。
   • 时间复杂度：检查队列是否为空的操作通常也是O(1)的。

5. 获取队列的大小（Size）：返回队列中当前包含的元素数量。

   • 操作结果：返回一个整数，表示队列的大小。
   • 时间复杂度：获取队列大小的操作通常是O(1)的。

二.队列的实现方式

队列的实现方式主要有两种：

2.1 基于链表的队列

实现方式：
链表队列使用节点（Node）来存储数据，每个节点包含数据部分和指向下一个节点的指针。队列包含两个指针，分别指向队头和队尾。入队操作在队尾添加新节点，出队操作移除队头节点。

优势：

1. 动态性：链表队列可以动态调整大小，无需预分配固定空间。
2. 内存利用率：没有固定的空间限制，可以根据需要分配和释放内存。
3. 插入和删除效率高：在链表中插入和删除元素只需调整指针，时间复杂度为O(1)。

劣势：

1. 内存开销：每个节点都需要额外的指针空间，增加了内存开销。
2. 访问效率低：由于链表不是连续存储的，访问特定位置的元素需要从头节点开始遍历，时间复杂度较高。

2.2 基于数组的队列

实现方式：
数组队列使用固定大小的数组来存储元素，并使用两个索引（如front和rear）来指示队头和队尾的位置。入队操作在队尾添加元素，出队操作移除队头元素。当数组空间不足时，可以进行扩容操作（但通常不常见，因为扩容会导致性能下降）。更常见的是采用循环队列的方式，当队尾到达数组末尾时，回到数组开头继续添加元素。

优势：

1. 内存利用率高：数组是连续存储的，内存利用率较高，没有额外的指针开销。
2. 访问效率高：可以通过索引直接访问数组中的元素，时间复杂度为O(1)。
3. 实现简单：数组队列的实现相对简单，不需要处理复杂的指针操作。

劣势：

1. 固定大小：数组队列的大小是固定的，需要提前分配足够的空间。如果空间不足，可能导致性能下降或内存溢出。
2. 扩容成本高：虽然可以采用扩容的方式来解决空间不足的问题，但扩容会导致额外的内存分配和数据复制操作，成本较高。
3. 假溢出：在普通数组队列中，当队尾指针达到数组末尾时，即使数组中间还有空闲空间，也无法继续入队，导致“假溢出”现象。循环队列可以解决这个问题，但实现相对复杂一些。

 一般情况下，基于链表的队列实现更加常见，下面我们来给出基于链表的队列的实现。

三.基于链表的队列实现

定义链表队列的结构

首先，我们定义了一个名为QDataType的类型别名，它基于int类型。这个类型别名将用于队列中存储的数据元素。

接着，我们定义了一个名为QueueNode的结构体，它代表队列中的一个节点。这个结构体包含以下两个成员：

• data：这是一个QDataType类型的变量，用于存储队列节点的数据。
• next：这是一个指向QueueNode类型的指针，它指向队列中的下一个节点。如果这是队列的最后一个节点，则此指针通常被设置为NULL。

然后，我们定义了一个名为Queue的结构体（通过typedef，我们也可以用Queue来直接引用它，而不需要使用struct关键字）。这个结构体代表了一个队列的数据结构，并包含以下三个成员：

• phead：这是一个指向QueueNode类型的指针，它指向队列的头部（即队列中第一个进入的元素所在的节点）。如果队列为空，则此指针通常被设置为NULL。
• ptail：这是一个指向QueueNode类型的指针，它指向队列的尾部（即队列中最后一个进入的元素所在的节点）。这个指针使得我们可以在队列的尾部高效地添加新元素。如果队列为空，则此指针也通常被设置为NULL。
• size：这是一个整型变量，表示队列中有效元素的个数。这个值在队列的操作过程中会动态变化，并且提供了队列当前长度的直接信息。

函数代码：

typedef int QDataType;
//定义队列结点的结构
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;//定义队列的结构
typedef struct Queue
{QueueNode* phead;//队头QueueNode* ptail;//队尾int size;        //队列有效元素个数
}Queue;

初始化

函数名称：QueueInit

函数目的：初始化一个队列，为其分配必要的资源，并设置初始状态。

函数参数：

• Queue* pq：这是一个指向Queue结构体的指针，指向需要被初始化的队列。

函数体详细解析：

1. 参数有效性检查：
   • 使用assert(pq);语句来确保传入的指针pq是有效的。如果pq为NULL，则程序会终止，并显示错误信息。
2. 初始化队列头部和尾部指针：
   • 将pq->phead和pq->ptail都设置为NULL，表示队列在初始化时是空的，没有节点。
3. 初始化队列大小：
   • 将pq->size设置为0，表示队列中没有元素。

通过QueueInit函数的执行，一个队列被成功初始化，其头部和尾部指针均指向NULL，且队列大小为0，表示队列当前为空且已准备好进行后续的入队和出队操作。

函数代码：

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}

入队列——向队列中插入数据

函数名称：QueuePush

函数目的：向队列中添加一个新元素。

函数参数：

• Queue* pq：指向需要添加元素的队列的指针。
• QDataType x：需要被添加到队列中的元素值。

函数体详细解析：

1. 参数有效性检查：
   • 使用assert(pq);语句来确保传入的队列指针pq是有效的。如果pq为NULL，则程序会终止，并显示错误信息（由断言机制提供）。
2. 内存分配：
   • 通过malloc(sizeof(QueueNode))为新的队列节点分配内存。sizeof(QueueNode)计算了QueueNode结构体所需的内存大小。
   • 将分配的内存地址转换为QueueNode*类型，并赋值给newnode指针。
   • 检查malloc是否成功分配了内存。如果newnode为NULL，则表示内存分配失败。此时，程序通过perror函数输出错误信息，并通过exit(1)终止执行。
3. 初始化新节点：
   • 将传入的元素值x赋值给新节点的data成员。
   • 将新节点的next成员设置为NULL，表示这是队列中的最后一个节点（至少在当前添加操作完成时是这样）。
4. 更新队列的队尾和队头指针：
   • 如果队列为空（即pq->phead == NULL），则将队头和队尾指针都指向新节点newnode。
   • 如果队列不为空，则将当前队尾节点的next指针指向新节点newnode，并更新队尾指针pq->ptail，使其指向新节点。这里有一个潜在的优化点：可以直接将pq->ptail = newnode;，因为在上一步已经确保了pq->ptail->next = newnode;。不过，原代码中的写法在逻辑上也是正确的，只是稍微多了一次对pq->ptail的读取操作。
5. 更新队列大小：
   • 将队列的大小pq->size增加1，以反映新添加的元素。

函数代码：

//入队列——向队列中插入数据
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!\n");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空，队头和队尾都是newnodeif (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}

 队列判空

函数名称：QueueEmpty

函数目的：判断队列是否为空。

函数参数：

• Queue* pq：指向需要检查的队列的指针。

函数体详细解析：

1. 参数有效性检查：
   • 使用assert(pq);语句来确保传入的队列指针pq是有效的。如果pq为NULL，则程序会终止，并显示错误信息（由断言机制提供）。这是为了防止程序在尝试访问pq指向的内存时发生崩溃。
2. 判断队列是否为空：
   • 函数通过检查队列的头部指针pq->phead是否为NULL来判断队列是否为空。如果pq->phead为NULL，则表示队列中没有节点，因此队列为空。
   • 这里需要注意的是，由于队列是先进先出的数据结构，只要队列的头部指针为NULL，就可以确定队列为空，无需检查尾部指针pq->ptail。在正常的队列操作中，如果队列为空，头部和尾部指针都会是NULL。但是，只检查头部指针就足以确定队列是否为空，因为只要有一个节点存在，头部指针就不会是NULL。
3. 返回值：
   • 函数返回一个布尔值。如果队列为空，则返回true（或非零值，在C语言中通常使用1表示真）；如果队列不为空，则返回false（或零值）。

函数代码：

//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);//队列为空时，头为空或头和尾均为空return pq->phead == NULL;
}

队列有效元素个数

函数名称：QueueSize

函数目的：获取队列中有效元素的个数。

函数参数：

• Queue* pq：指向需要查询的队列的指针。

函数体解析：

这个函数非常简单，它直接返回队列结构体中存储的元素个数pq->size。这个size字段通常是在队列操作过程中维护的，以确保它始终反映队列中当前有效元素的数量。

函数代码：

//队列有效元素个数
int QueueSize(Queue* pq)
{return pq->size;
}

出队列——从队列中删除数据

函数名：QueuePop

目的：从队列中删除（出队）最前面的数据元素。

参数：

• Queue* pq：指向需要操作的队列的指针。该队列应该是一个有效的队列，即pq不应为NULL，且队列不应为空。

函数体详细解析：

1. 参数有效性检查：
   • assert(pq);：确保传入的队列指针pq是有效的，即不是NULL。如果pq为NULL，则程序会在这里终止，并显示错误信息（由断言机制提供）。
   • assert(!(QueueEmpty(pq)));：确保队列不为空。这是通过调用QueueEmpty函数来实现的，该函数应该返回一个布尔值，指示队列是否为空。如果队列为空，则QueueEmpty(pq)将返回true（或非零值），而!(QueueEmpty(pq))将返回false（或零值），这将导致断言失败，程序终止。
2. 出队操作：
   • QueueNode* temp = pq->phead;：声明一个QueueNode类型的指针temp，并将其初始化为队列的头节点pq->phead。这是为了保存当前头节点的地址，以便稍后可以释放其内存。
   • pq->phead = pq->phead->next;：将队列的头指针pq->phead更新为指向下一个节点。这样，原来的头节点就被从队列中移除了。
3. 更新尾指针：
   • if (pq->phead == NULL)：检查更新后的头指针是否为NULL。如果是，这意味着队列现在为空，因为所有的节点都已经被移除。
     • pq->ptail = NULL;：如果队列为空，则将尾指针pq->ptail也设置为NULL。这是必要的，因为尾指针应该始终指向队列中的最后一个节点，或者如果队列为空，则应该为NULL。
4. 释放内存：
   • free(temp);：释放之前保存的头节点temp的内存。这是必要的，以避免内存泄漏。
5. 更新队列大小：
   • --pq->size;：将队列的大小pq->size减1，以反映已经移除了一个节点。

取队头数据

函数名：QueueFront

目的：获取队列前面的（即最先进入的）数据元素，但不从队列中移除它。

参数：

• Queue* pq：指向需要操作的队列的指针。该队列应该是一个有效的队列，即pq不应为NULL，且队列不应为空。

返回类型：QDataType

• 这是一个假设的数据类型，表示队列中存储的数据的类型。在实际代码中，QDataType应该被替换为实际的数据类型，如int、float、char*等，或者是一个用户定义的结构体或类的类型。

函数体详细解析：

1. 参数有效性检查：
   • assert(pq);：确保传入的队列指针pq是有效的，即不是NULL。如果pq为NULL，则程序会在这里终止，并显示错误信息（由断言机制提供）。
   • assert(!QueueEmpty(pq));：确保队列不为空。这是通过调用QueueEmpty函数来实现的，该函数应该返回一个布尔值（通常是int类型，其中0表示false，非0表示true），指示队列是否为空。如果队列为空，则断言失败，程序终止。
2. 获取队列前面的数据元素：
   • return pq->phead->data;：返回队列头节点pq->phead中存储的数据元素。这里假设QueueNode结构体（队列节点的类型）有一个名为data的成员，用于存储数据元素。

函数代码：

//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}

取队尾数据

函数名：QueueBack

目的：获取队列尾部的（即最后进入的）数据元素，但不从队列中移除它。

参数：

• Queue* pq：指向需要操作的队列的指针。该队列应该是一个有效的队列，即pq不应为NULL，且队列不应为空。

返回类型：QDataType

• 这是一个占位符数据类型，表示队列中存储的数据的类型。在实际代码中，QDataType应该被替换为实际的数据类型，如int、float、char*等，或者是一个用户定义的结构体、类的类型，或者是某种形式的指针。

函数体详细解析：

1. 参数有效性检查：
   • assert(pq);：确保传入的队列指针pq是有效的，即不是NULL。如果pq为NULL，则程序会在这里终止，并显示错误信息（由断言机制提供）。
   • assert(!QueueEmpty(pq));：确保队列不为空。这是通过调用QueueEmpty函数来实现的，该函数应该返回一个布尔值（在C语言中，通常是int类型，其中0表示false，非0表示true），指示队列是否为空。如果队列为空，则断言失败，程序终止。
2. 获取队列尾部的数据元素：
   • return pq->ptail->data;：返回队列尾节点pq->ptail中存储的数据元素。这里假设QueueNode结构体（队列节点的类型）有一个名为data的成员，用于存储数据元素。

函数代码：

//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}

销毁队列

函数名：QueueDestroy

目的：销毁队列，释放其占用的所有内存资源。

参数：

• Queue* pq：指向需要销毁的队列的指针。该队列应该是一个有效的队列，即pq不应为NULL。但是，此函数将清空队列，即使它不是空的。

返回类型：void

• 此函数不返回任何值。

函数体详细解析：

1. 参数有效性检查：
   • assert(pq);：确保传入的队列指针pq是有效的，即不是NULL。如果pq为NULL，则程序会在这里终止，并显示错误信息（由断言机制提供）。这是基本的错误检查，但在实际应用中，即使pq为NULL，一个更健壮的实现可能会选择安静地返回而不是断言失败。
2. 遍历并释放队列节点：
   • QueueNode* pcur = pq->phead;：声明一个QueueNode类型的指针pcur，并将其初始化为队列的头节点pq->phead。
   • while (pcur)：使用一个循环来遍历队列中的所有节点，直到pcur变为NULL，表示已经到达队列的末尾。
     • QueueNode* next = pcur->next;：在释放当前节点之前，先保存下一个节点的指针，以便在释放当前节点后能够继续遍历。
     • free(pcur);：释放当前节点的内存。
     • pcur = next;：将pcur更新为下一个节点，继续循环。
3. 重置队列指针和大小：
   • pq->phead = pq->ptail = NULL;：将队列的头指针和尾指针都设置为NULL，表示队列现在是空的。
   • pq->size = 0;：将队列的大小设置为0，表示队列中没有元素。

函数代码：

//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

兄弟们共勉！！！   

码字不易，求个三连

抱拳了兄弟们！