双端队列和循环缓冲区有什么区别?

问题描述 投票:1回答:2

由于缺乏数据结构教育,我事先表示歉意。

据我了解:

  • 用作内存的固定大小的双端队列可以替换其最早的值(尽管我们删除了新值)

  • 用作内存的循环缓冲区也可以替换其最早的值

两个概念之间有什么区别?它们是一样的吗?一个是另一个的子集吗?

python algorithm data-structures buffer deque
2个回答
3
投票

一个很好的相关问题就是这个:队列和带有尾指针的链表之间有什么区别?队列添加到末尾并从前面删除,这与使用带尾指针的链表相同。

不同之处在于,其中之一是抽象,而其中之一是实现抽象的具体方法。有几种实现队列的方法,包括带有尾指针,循环缓冲区甚至是展开树的链表。类似地,您可以对带有尾指针的链表执行某些操作,而对尾双端指针则不会,例如将大段拼接到列表中或从列表中剪出。

在您的情况下,“双端队列”是抽象的。您可以将双端队列视为“可以在两端进行添加和删除的东西”,并且可以使用循环缓冲区,链接列表或展开树等来实现。循环缓冲区是多种方式之一您可以实现双端队列,并且除了实现双端队列之外,还可以使用循环缓冲区执行其他操作。

希望这会有所帮助!


0
投票

双端队列是abstract data type,因为它是由您可以执行的操作定义的;它支持什么操作。您可以在双端队列的任一端添加和删除元素。

循环缓冲区是data structure,因为它是通过在内存中的表示方式以及应如何操纵其状态以完成双端队列操作的方式定义的。

两者之间的关系是循环缓冲区是双端队列的implementation

© www.soinside.com 2019 - 2024. All rights reserved.