常见制作网页的软件,seo怎么弄,有没有免费装修设计的网站,做网站建设一般多少钱文章目录 前言1.队列的基本概念2.链表与数组实现队列的区别2.1数据存储结构2.2性能2.3内存使用 3.为什么选择链表实现队列#xff1f;4.结构定义函数声明 5.核心操作5.1初始化 (QInit)5.2销毁 (QDestroy)5.3入队 (QPush)5.4出队 (QPop) 6.队列的查询操作6.1队首元素 (QueueFro… 文章目录 前言1.队列的基本概念2.链表与数组实现队列的区别2.1数据存储结构2.2性能2.3内存使用 3.为什么选择链表实现队列4.结构定义函数声明 5.核心操作5.1初始化 (QInit)5.2销毁 (QDestroy)5.3入队 (QPush)5.4出队 (QPop) 6.队列的查询操作6.1队首元素 (QueueFront)6.2队尾元素 (QueueBack) 7.辅助函数7.1判断空 (QueueEmpty)7.2队列大小 (QueueSize) 总结 前言
在计算机科学中队列是一种非常基础且广泛使用的数据结构。它的工作原理类似于现实生活中的排队先来的先服务FIFO, First-In-First-Out。在本文中我们将深入探讨如何在C语言中使用链表实现一个队列并解析相关的代码实现。 1.队列的基本概念
队列是一种遵循先进先出原则的线性数据结构。在队列中添加操作入队发生在一端队尾而移除操作出队则发生在另一端队首。这种结构在多种场景中非常有用如任务调度、数据缓冲等。 2.链表与数组实现队列的区别
当使用数组和链表实现队列时主要区别在于数据存储结构、性能和内存使用
2.1数据存储结构 数组队列使用一个固定大小的数组。当数组满时需要进行扩容这可能涉及复制整个数组到新的内存位置。 链表队列使用动态分配的节点每个节点包含数据和指向下一个节点的指针。不需要事先分配固定大小的空间。 2.2性能 数组入队和出队操作通常是O(1)复杂度但当数组需要扩容时复杂度会增加。 链表由于不需要扩容入队和出队操作始终保持O(1)复杂度。 2.3内存使用 数组可能会有未使用的预留空间特别是在队列大小波动较大时。 链表每个元素单独分配无需预留额外空间但每个节点需要额外存储指针略增加内存使用。 3.为什么选择链表实现队列
在C语言中链表是一种常用的数据结构用于创建动态大小的序列。相比于数组实现链表实现的队列具有动态分配内存的优点不受固定大小的限制。
与基于数组的队列实现相比链表实现的队列具有以下优势 动态大小不受固定长度的限制可以根据需要动态扩展或收缩。 内存利用每个元素仅在需要时分配内存减少了空间浪费。 性能优化避免了数组实现中可能发生的元素搬移操作。 接下来我们来用链表进行实现队列。 4.结构定义
该队列的实现基于两种结构QueueNode 和 Queue。
typedef int QDataType; // 定义队列数据类型为int// 队列节点的结构体定义
typedef struct QueueNode
{QDataType val; // 节点存储的数据struct QueueNode* next; // 指向下一个节点的指针
} QNode;// 队列的结构体定义
typedef struct Queue
{QNode* phead; // 指向队列头部的指针QNode* ptail; // 指向队列尾部的指针int size; // 队列的大小
} Queue;这里QueueNode 表示队列中的每个节点包含一个数据字段和一个指向下一个节点的指针。而Queue结构则持有指向队列头部和尾部的指针并跟踪队列的当前大小。
函数声明
// 函数声明
void QInit(Queue* pq); // 初始化队列
void QDestroy(Queue* pq); // 销毁队列void QPush(Queue* pq, QDataType x); // 向队列中添加元素
void QPop(Queue* pq); // 从队列中移除元素QDataType QueueFront(Queue* pq); // 获取队列头部元素
QDataType QueueBack(Queue* pq); // 获取队列尾部元素bool QueueEmpty(Queue* pq); // 检查队列是否为空
int QueueSize(Queue* pq); // 获取队列的大小5.核心操作
5.1初始化 (QInit)
初始化函数设置队列的头部和尾部指针为NULL大小为0。这是创建队列的必要步骤。
// 初始化队列
void QInit(Queue* pq)
{assert(pq); // 断言队列指针非空pq-phead pq-ptail NULL; // 将头指针和尾指针都设为NULLpq-size 0; // 将队列大小设置为0
}5.2销毁 (QDestroy)
销毁函数释放队列中所有节点的内存并重置队列的状态。这是队列不再使用时的清理步骤。
// 销毁队列
void QDestroy(Queue* pq)
{assert(pq); // 断言队列指针非空QNode* cur pq-phead;while (cur){QNode* next cur-next; // 保存下一个节点free(cur); // 释放当前节点cur next; // 移动到下一个节点}pq-phead NULL; // 将头指针设为NULLpq-ptail NULL; // 将尾指针设为NULLpq-size 0; // 将队列大小设置为0
}5.3入队 (QPush)
在队列的尾部添加一个新元素。如果队列为空则新元素同时成为头部和尾部元素。
// 向队列中添加元素
void QPush(Queue* pq, QDataType x)
{assert(pq); // 断言队列指针非空QNode* newNode (QNode*)malloc(sizeof(QNode)); // 分配新节点内存if (newNode NULL){perror(malloc fail); // 内存分配失败处理exit(-1);}newNode-val x; // 设置新节点的值newNode-next NULL; // 新节点的下一个节点为NULLif (pq-ptail NULL) // 如果队列为空{pq-phead pq-ptail newNode; // 队列头尾都指向新节点}else{pq-ptail-next newNode; // 将新节点接到队列尾部pq-ptail newNode; // 更新尾指针}pq-size; // 队列大小增加
}5.4出队 (QPop)
从队列的头部移除一个元素。如果队列为空调整尾部指针。
// 从队列中移除元素
void QPop(Queue* pq)
{assert(pq); // 断言队列指针非空assert(pq-phead); // 断言队列不为空QNode* Del pq-phead; // 保存要删除的节点pq-phead pq-phead-next; // 更新头指针free(Del); // 释放节点内存if (pq-phead NULL) // 如果队列变空{pq-ptail NULL; // 更新尾指针}pq-size--; // 队列大小减少
}6.队列的查询操作
6.1队首元素 (QueueFront)
返回队列头部节点的值但不移除它。
// 获取队列头部元素的值
QDataType QueueFront(Queue* pq)
{assert(pq); // 断言队列指针非空assert(pq-phead); // 断言队列不为空return pq-phead-val; // 返回头部元素的值
}6.2队尾元素 (QueueBack)
返回队列尾部节点的值。
// 获取队列尾部元素的值
QDataType QueueBack(Queue* pq)
{assert(pq); // 断言队列指针非空assert(pq-ptail); // 断言队列不为空return pq-ptail-val; // 返回尾部元素的值
}7.辅助函数
7.1判断空 (QueueEmpty)
检查队列是否为空。
// 检查队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq); // 断言队列指针非空return pq-phead NULL; // 如果头指针为NULL则队列为空
}7.2队列大小 (QueueSize)
返回队列中节点的数量。
// 获取队列的大小
int queueSize(Queue* pq)
{return pq-size; // 返回队列的大小
} 总结
理解队列的不同实现方式对于选择最适合特定应用场景的数据结构至关重要。链表实现的队列提供了灵活性和一致的性能特别适用于大小不确定或需要频繁扩展的场景。而数组实现则在空间预分配和随机访问方面更有优势。深入了解这些差异可以帮助程序员做出更明智的选择。我希望这篇文章能够帮助你更好地理解和实现队列。如果你有任何问题或想分享你的经验请在评论区留言。
