抽象数据类型

抽象数据类型，常见的缩写ADT.S，是一种基于它们的使用方式以及它们提供的行为进行分类数据结构的一种方式。它们未指定如何在内存中实现或布置数据结构，但仅提供最小的预期接口和行为集。例如，一个堆是一种抽象数据类型，它指定具有LIFO（最后，首先）行为的线性数据结构。堆栈通常使用阵列要么链接清单，但使用二进制搜索树的不必要复杂的实现仍然是有效实现。要清楚，可以说堆栈是阵列的不正确，反之亦然。阵列可以是用过的作为堆栈。同样，堆栈可以是实施的使用数组。

由于抽象数据类型没有指定实现，这意味着它也是不正确的谈论时间给定抽象数据类型的复杂性。一个联想阵列可以不可以有 $O（1）$平均搜索时间。一个由a实现的关联数组哈希表做有 $O（1）$平均搜索时间。

为了进一步复杂化问题，由于某些抽象数据类型几乎始终用特定数据结构实现，因此某些程序员将互换使用这两个术语：例如，优先级队列和堆，或关联数组和哈希表。使用术语的上下文通常可以提供区别。