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

Question

4

我很抱歉我的数据结构教育不够。

据我所知：

这两个概念有什么区别？它们是相同的吗？一个是另一个的子集吗？

- Linsu Han

在标题中，你只说“deque”，但在正文中突然说“固定大小的deque”。那到底是哪一个？ - Kelly Bundy

2个回答

3

双端队列是一种抽象数据类型，因为它的定义取决于你可以用它做什么，即它支持哪些操作。你可以在双端队列的任意一端添加或删除元素。

循环缓冲区是一种数据结构，因为它的定义取决于它在内存中的表示方式以及如何操作它的状态来满足双端队列的操作。

两者之间的关系是，循环缓冲区是双端队列的实现。

- kaya3

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

一个很相关的问题是：队列和有尾指针的链表有什么区别？队列在末尾添加，在前面删除，这与使用有尾指针的链表相同。

它们之间的区别在于一个是抽象，而另一个是实现此抽象的具体方式。有几种方法可以实现队列，包括使用带尾指针的链表、循环缓冲区或甚至是伸展树。同样，有些事情你可以对带尾指针的链表做的，但不能应用到deque上，例如将大片段剪切到或从列表中剪切出。

在您的情况下，“deque”是抽象。您可以将deque视为“可以从两端添加和删除的东西”，它可以使用循环缓冲区、链表或伸展树等来实现。循环缓冲区是实现deque的许多方法之一，并且还有其他一些可以使用循环缓冲区的方法，不仅仅是实现deque。

希望这能帮助您！