队列是一个重要的数据结构,他的特性是先进先出,所以由于这个特性,队列只有一个入口和一个出口,所以只有push和pop
下面我们看一下他如何实现
首先我们来看一下他的结构体
这里我们看到我们定义了两个结构体,其中一个是队列的节点,另外一个是队列,这里是这样的,我们的队列是用链表来实现的,(这里用链表实现相对简单一点 )所以就用链表实现,但是这里我们肯定是要有一个记录头和尾的节点的,所以我们又定义了一个队列的结构体,这个结构体里面有两个节点,分别是头和尾。下面我们来看一下这个的包含关系,更容易理解一点
就是这个样子的,结构体queue里面包含两个queuenode类型的指针,来记录头和尾(因为后面有需要)
下面我们就浅浅的看一下需要实现哪些函数(基本)
就是这些了,下面我们就一个一个的看一下
首先来看一下初始化
初始化函数比较简单,就是一个queue里面的两个节点都置为空,然后把size置为0就可以了。
下面看一下Push
还就是之前的断言这里不讲了,还有就是malloc函数,由于是链表实现,所以我们需要一个节点就malloc一个
下面说一下队列的插入是怎么样的,队列是只有一个口插入一个口出数据,所以队列是先入先出的
下面来一张图片
就是这个样子的,所以我们让他一直头插,所以我们就直接头尾插就好了,其实也就是链表的头插,所以就需要一个tail指针了
下面说一下
根据我们上面说的,Pop就是头删了,所以就是头删就可以,当然由于Push的时候是要么Head和Tail都为空,要么就都不是空,所以这里当Head的下一个为空的时候(就是只剩下一个节点的时候),删除之后就要把head和tail都置为空,剩下的就和正常是一样的了
下面看一下size,他真的是...so easy不过还是看一下吧
其实我并不太想说什么,就是直接返回里面的size就可以了
下面还是看一下取头节点的数据
其实也并不难,直接返回头节点的数据
下面就是尾节点的数据
也就是返回尾节点数据
下面在看一下是否为空,空的话返回true,非空返回false
就是如果size为空就返回true了....反之则false
最后一个就是destroy了
我们来看一下
就是和链表删除也是差不多的,定义一个节点然后就是挨个删除
结束