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

Question

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

堆是抽象数据类型吗？如果是这样，那么优先队列呢？

答案是：

优先队列和堆都是数据类型（更准确；抽象数据类型或 ADT）

但在这儿

堆是否被视为抽象数据类型？

堆不是 ADT。它是一个数据结构。

例如在书中：

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，链表

• Stack，是一个ADT，但是你可以用数组或者链表来实现栈，但是最后这个栈是一个数据结构

• Queue，与 Stack 相同

• 堆，同栈

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

它是否正确？

Answer 1

正如您所说，抽象数据类型描述了实体的行为（或“语义”）（通常从使用该实体的人的角度来看）。因此，在您的示例中，堆栈、队列、列表等...数据结构只是组织数据的一种特殊方式。所以它只是表示数据类型的一种方式。主要问题是如果我们说 DS 的所有行为定义都是 ADT我不会那样说。如果我定义一个代表 a 的经典示例的数据结构Car（同样，将数据结构视为一种组织数据的方式），则该数据结构的行为不一定代表 ADT。