所有的数据结构都是抽象数据类型吗？

Question

我在某些地方读到关于这个主题的矛盾的东西，例如这里

Is heap an abstract data type? If so, what about priority queues?

答案是：

both priority queues & heaps are data types (more accurate; abstract data type or ADT)

但是这里

Heap is not an ADT. It is a Data Structure.

书中的例子：

Java 软件结构，国际版 [John Lewis, Joseph Chase]

它有一个堆作为 ADT 和一个 DS，代码如下：

public interface HeapADT<T> extends BinaryTreeADT<T>
{
/**
* Adds the specified object to this heap.
*
* @param obj the element to be added to this heap
*/
public void addElement (T obj);
/**
* Removes element with the lowest value from this heap.
*
* @return the element with the lowest value from this heap
*/
public T removeMin();
/**
* Returns a reference to the element with the lowest value in
* this heap.
*
* @return a reference to the element with the lowest value in this heap
*/
public T findMin();
}

主要问题是如果我们说一个DS的所有行为定义都是一个ADT，例如

• List是静态数组和动态数组的ADT，linked-list
• Stack,是一个ADT，但是可以用数组或者链表来实现栈，不过最后这个栈是一个数据结构
• Queue，同Stack
• Heap,同Stack

所以抽象数据类型是您将使用另一个具有自己的 ADT 的数据结构来实现的行为。

这是正确的吗？

谢谢

Answer 1

正如您所说，抽象数据类型描述了实体的行为（或 "semantics"）（通常是从使用该实体的人的角度来看）。所以在你的例子中，堆栈、队列、列表等...

数据结构只是组织数据的一种特殊方式。所以它只是一种表示数据类型的方式。

The main question is if we say that all behaviour definition of a DS is an ADT

我不会这么说。如果我定义一个代表 Car 经典示例的数据结构（同样，将数据结构视为一种组织数据的方式），该数据结构的行为不一定代表 ADT。