数据结构重读 – 队列 & 双端队列

队列(queue)是一种先进先出(FIFO)的线性表。只允许在一端进行插入,而在另一端删除元素。

允许插入的一端叫做队尾,允许删除的一端叫做队头。

双端队列(deque):限定插入和删除操作在表两端进行的线性表。

双端队列在一些限定条件下可以退化为:
(1)普通队列(只能在一端插入而另外一端删除)
(2)两个栈底相连的栈

队列 / 双端队列的定义:

由于可以在双端操作,所以肯定得有一个head,一个rear(tail)。我觉得确实用一个多的空头表示比较合适,然后头的data可以表示队列中有多少元素。

注意1:删除队列头时,如果被删除的元素是队列中最后一个元素时,一定要记得更新尾结点为NULL!

注意2:双端队列在队尾删除的时候,由于没有保存前向指针,需要从head从头遍历到tail的前一个,还要注意考虑只有一个结点的特殊情况。

代码如下:

 

 

Leave a Reply

Your email address will not be published.