湖北智能网站建设推荐,工程公司管理软件,做微信的网站有哪些,网站使用帮助目录 文章目录 前言 1.队列 1.1 队列的概念及结构 1.2 队列的实现 1.2.1 队列的定义 1.2.2队列的初始化 1.2.3 入队 1.2.4 判空 1.2.5 出队 1.2.6 队头队尾数据 1.2.7 队列长度 1.2.8 队列销毁 总结 前言 队列#xff0c;作为一种重要的数据结构#xff0c;在计算机科学中扮演… 目录 文章目录 前言 1.队列 1.1 队列的概念及结构 1.2 队列的实现 1.2.1 队列的定义 1.2.2队列的初始化 1.2.3 入队 1.2.4 判空 1.2.5 出队 1.2.6 队头队尾数据 1.2.7 队列长度 1.2.8 队列销毁 总结 前言 队列作为一种重要的数据结构在计算机科学中扮演着重要的角色它按照先进先出FIFO的原则进行操作。它可以用来解决许多实际问题队列的应用范围广泛从操作系统中的进程调度到网络中的数据传输再到算法中的搜索和排序队列无处不在。那么接下来让我们一同开始这段关于队列的探索之旅吧 1.队列
1.1 队列的概念及结构 队列 只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出的特性。 入队列进行插入操作的一端称为队尾出队列进行删除操作的一端称为队头 1.2 队列的实现 队列的特性是先进先出这里就要考虑选择顺序表还是链表来实现队列。队列需要大量的头删尾插的操作顺序表进行头删的效率太低所以这里我们选用链式结构来实现。 1.2.1 队列的定义 typedef int Datatype;
typedef struct QueueNode
{struct QueueNode* next;Datatype data;}QueueNode; 和定义链表的节点一样。但是也有所不同我们知道队列需要大量的头删和尾插为了方便尾插和头删我们最好再创建两个指针一个指向头另一个指向尾。那这样岂不是需要二级指针解决吗 这里我将会介绍一种新的方法来解决头删问题前边我们已经知道对链表头进行操作方法有三种
一种是使用二级指针来达到修改头节点的目的另外一种是使用函数返回类型来达到修改的目的此外我们还可以使用带头结点的链表来解决对链表头操作时需要特殊处理的情况 进行尾插操作时需要传递头指针和尾指针这样使用时函数的参数变多了调用函数时也比较费劲那这里我们不如直接再定义一个结构体来存放队列的头指针和尾指针以及队列的长度。
typedef int Datatype;
typedef struct QueueNode
{struct QueueNode* next;Datatype data;}QueueNode;
typedef struct Queue
{QueueNode* head;QueueNode* tail;int size;
}Que; 这样我们传参时就只需传第二个结构体就可以进行了。通过第二个结构体找到第一个结构体然后进行一系列头删、尾插的操作使用时实质和二级指针类似它效果和带头节点的链表类似只需要一级指针就可以解决。 虽然栈和队列的逻辑非常简单但是它们的结构却变得更加复杂了链表和顺序表是后续数据结构学习的基础一定要灵活掌握。
1.2.2队列的初始化
void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
} 初始化就非常简单了只需要将头指针和尾指针进行初始化置为NULL长度置为0。这里我们也不需要创建新节点由于我们就只要一个接口需要创建新节点尾插所以不需要封装成函数对节点进行初始化。
我们在调用函数时也非常简单将第二个结构体传过去
Que q;//创建结构体变量QueueInit(q); 1.2.3 入队
void QueuePush(Que* pq, Datatype x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
} 在入队操作时我们需要创建新的节点这里注意创建新节点是为队列的节点申请空间定义的第一个结构体才是队列节点的类型所以新建节点是的类型也应该与第一个结构体对于链表没有节点时这时需要将头指针和尾指针指向新节点进行特殊处理。后续再次入队就可以直接将新节点链接到尾节点的后边。入队新节点的同时注意将size记录队列长度。 1.2.4 判空
入队之后就是出队但考虑到后续多个接口中需要判空这里就提前封装成一个函数 bool IsEmpty(Que* pq)
{assert(pq);return (pq-head NULL);
} 函数类型为bool类型该类型返回值只有true1和false0两种所以最后直接返回条件pq-head NULL如果为真就为true假就为false。 1.2.5 出队
void QueuePop(Que* pq)
{assert(pq);assert(!IsEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QueueNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
} 出队需要先判断队列是否为NULL然后将头指针向后移动改变结构体指针释放掉第一个节点然后队列长度size--但需要考虑一下特殊情况就是删空的情况如果只剩下一个节点就可以直接释放掉然后将头指针和尾指针置为NULL。 1.2.6 队头队尾数据
//队头
Datatype QueueFront(Que* pq)
{assert(pq);assert(!IsEmpty(pq));return pq-head-data;
}
//队尾
Datatype QueueBlack(Que* pq)
{assert(pq);assert(!IsEmpty(pq));return pq-tail-data;
} 这里没什么好说的直接返回队列头指针和尾指针指向节点的数据。但注意都需要进行判空操作。
1.2.7 队列长度
int QueueSize(Que* pq)
{assert(pq);return pq-size;
} 直接返回队列的size即可。
1.2.8 队列销毁 void DestoryQueue(Que* pq)
{assert(pq);QueueNode* cur pq-head;while (cur){QueueNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
} 像链表一样遍历队列一个一个的销毁节点最后将指针置为NULL队列长度size置为0。 在链表学习以来部分同学会不会有这样的疑惑销毁空间是不是不允许部分销毁吗那一个一个节点的销毁不就可以部分销毁那是因为标准C规定的是释放空间时一个malloc申请的空间必须全部释放不可以将一个malloc申请的空间部分释放而链表是每次增加节点就申请一次空间malloc一次每个节点都是相对独立的空间所以需要一个个的遍历逐个销毁。 总结 希望通过这篇博客可以使你对队列有了更深入的了解并能够应用这一概念解决实际问题。无论是在计算机科学中还是在日常生活中队列都是一种重要的工具和思维方式它能够帮助我们更好地组织和管理事务。最后感谢阅读
