看动画学算法之:双向队列dequeue2022年11月21日

向头部插入数据和向尾部删除数据的方法和基本队列的实现是一致的,这里就不列出来了。

也就是说实现了这四个方法的队列就是双向队列。我们不管它内部是怎么实现的。

和普通队列项目,双向队列可以分别在头部和尾部进行插入和删除工作,所以一个dequeue需要实现这4个方法:

尾部删除我们需要找到尾部节点的前一个节点,将这个节点置位rear节点。这就需要我们能够通过rear节点找到它的前一个节点。

双向链表中的每一个节点都有next和prev两个指针。通过这两个指针,我们可以快速定位到他们的后一个节点和前一个节点。

dequeue指的是双向队列,可以分别从队列的头部插入和获取数据,也可以从队列的尾部插入和获取数据。

最通俗的解读,最深刻的干货,最简洁的教程,众多你不知道的小技巧等你来发现!

因为是循环数组,size_30,t_70 />上面的3种实现的enQueue和deQueue方法,所以他们的时间复杂度是O(1)。这里不能做简单的数组拷贝,也就是说知道head可以拿到它后面一个数据。

在头部插入和在尾部插入都可以快速定位到目标节点。但是我们考虑一下尾部删除的问题。

看动画学算法之:双向队列dequeue2022年11月21日

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

滚动到顶部