What is the connection between data structures and data types?

I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have figured (please correct me) and would like to ask :

• a (abstract) data type is a set $D$ of values, together with some

operations on it (each $n$-ary operation is a mapping $D^n \to D$).
E.g. The set of all the integers with arithmetic operations on it forms a data type.

• A data structure seems to be a data type. Or are they the same

concept? What is the formal definition of a data structure?

-
I have some difficulty in understanding if a "container-like construct" is a data structure or data type, or the set of all of them is. What I mean by a "container-like construct", is some set of values, but with some relation(s) on the set, e.g. a queue, a graph, a stack, an array, a map, .....

E.g., a queue is a set of values in it, with some ordering on the values according to which value was added earlier than which. Is a queue with a fixed size and fixed elements, as a set of values in it, a data type or a data structure? Or do all the queues form a data
type or a data structure? Are adding and removing elements from a
queue, which obviously create new queues, viewed as operations on the set of all the queues?

Similarly, a graph is a set of vertices and has relation between the vertices being the edges. Is a graph with fixed vertices and edges a data type or a
data structure, or is the set of all the graphs a data type or a
data structure? Are transformations from a graph to another different graph considered to be operations on the set of all the graphs? Is searching for a vertex in a graph considered to be an operation on that single graph?

I agree with your definition of abstract data type. (A domain of values, together with some operations on that domain.)

I typically use the term data structure to refer to implementation techniques for data types. Examples of data structures are things like balanced binary trees and hashtables.

For example consider the data type set of integers, with operations like union, intersection, is_member?, and insert_member.

You could implement the data type with at least three different data structures, each of which has advantages and disadvantages. For example, you could implement your set using a balanced binary tree (like a red-black tree, for example). Each node in the tree represents a member of the set, insertion and membership tests take $O(\log n)$. Or, if your sets are over a finite (and relatively small) universe of items you could implement it with a bit array. This is an array of $U$ bits (where $U$ is the size of the universe.) Inserting element $i$ just means setting the $i$th bit, testing for membership just means testing the $i$th bit. But now intersection (respectively union) requires you to take the binary-and (respectively or) of $U$ bits, which kind of stinks when you have sets with just a few elements in them. Similarly with hash table implementations, insertion and testing are nice (on average), but intersection and union can be somewhat more complicated to do efficiently.

StackExchange Computer Science Q#29122, answer score: 7