Need help understanding what an ADT (abstract data type) is exactly

[r0bHadz]

TL;DR Summary

Read quantum quests post. Still confused. What I have so far:

ADT = way of describing something with a mathematical model.

Datastructure: the way you organize your data

How is stack both a data structure and a datatype?

I've read quantum quests data structures bible but I'm still confused. I need help in simplest terms understanding what an ADT actually is and how it's different from a data structure.

So a data structure is a way of organizing data. I can understand why a stack, or a queue would fall under the category of data structure. Because: they have a structure. The first element in, is the first one out, or last one out depending if its a stack or not.

But I do not understand why its a ADT. When I think of mathematical model that describes a stack, I think of a list of elements.

 

[QuantumQuest]

One important point for ADTs is this

This specification does not imply implementation details which are different according to the syntax of a specific programming language

So, you have an ADT which is a mathematical model of the data objects that make up a data type and the functions that operate on these objects and there's nothing implying implementation details in it.

Next

So, effectively, ADTs are purely theoretical entities which we use in conjunction with abstract descriptions of algorithms (meaning not real implementations as programs). We can classify and evaluate data structures through them. On the other hand, a Data Structure is a realization of an ADT i.e. involves aspects of implementation.

So, here it is clear that you can construct a theoretical (mathematical) model with pen and paper and create the steps of an algorithm that operates on it. If / when you want to impement this construct in a specific programming language then implementation details come into play. For instance, let's take the example of a stack for which you talk about.

As an ADT, a stack is a collection of elements with a number of operations defined on it (see the "Stack" section of the tutorial). The operations are defined in a mathematical way as I describe there.
Now, see the example of an implementation of a stack in Pascal. Here, we use the record software construct in order to implement the stack as a data structure and we define functions in order to operate on the data i.e. create a stack, checking if the stack is empty or full which is crucial in order to perform other operations on the stack, push and pop in order to insert and extract data from the stack and also top of the stack.

So, as you see, there are implementation details in order to implement the stack itself and the operations on it in the form of program in some programming language.

EDIT: Also, a few words about this

There is an open relationship among these three notions: A data type, as we saw above, is the implementation of an ADT i.e. of a specification about the relationship of specific data and the operations that can be performed on them and data structures, at the programming level, are essentially sets of variables of the same or different data types.

If you got confused about this, this basically pertains to the way that programming languages implement data types. Take the range of integers that some programming language has. This is a data type in this specific programming language and it also includes a set of operations besides the range of integers itself. So, when a programmer constructs a specific data structure in this programming language - and any other for that matter, he / she essentially defines variables of various data types which as said above contain both the specific data types and the operations on them, so they are data structures of and in itselves and then he / she can construct another data structure e.g. a queue using an array for instance.

That's why I started the presentation of data structures at a low level and then went higher.