Have all data structures an abstract data type?

Question

I some places I'm reading contradictory things about this topic, for example here

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

The answer was:

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

But here

Is Heap considered an Abstract Data Type?

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

And for example in the book:

Java Software Structures,International Edition [John Lewis, Joseph Chase]

it has a heap as ADT and a DS with this code:

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();
}

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

• List is an ADT of Static and Dynamic Array, linked-list
• Stack, is an ADT, but you can implement the stack with an array or a linked list, but finally this stack is a data structure
• Queue, the same that Stack
• Heap, the same that Stack

So abstract data type is the behaviour that you'll implement with another data structure that has its own ADT.

Is this correct?

Thanks

Answer 1

An Abstract Data Type, as you said, describes the behavior (or "semantics") of an entity (usually from the point of view of those who use that entity). So in your examples, stacks, queues, lists, etc...

A data structure is just a particular way of organizing data. So it is just one way to represent a data type.

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

I wouldn't say that. If I define a data structure that represent the classical example of a Car (again, considering a data structure just as a way to organize data), the behavior of that data structure does not necessarily represent an ADT.