什么是抽象数据类型(ADT)？

Question

我遇到了一个‘抽象数据类型’的定义，我无法理解。谁能解释一下，最好是举个例子？

抽象数据类型定义为组成数据类型的数据对象的数学模型以及操作这些对象的函数。

Answer 1

在某些语言中，无所谓什么，我可以给你以下几点：

Stack make_stack();
void push(Stack stack, value);
value pop(Stack stack);

然后我可以说，假设您想将三个值推到堆栈上，然后弹出一个值。看起来可能是这样的：

Stack my_stack = make_stack();
push(my_stack, 14);             /* stack now contains: 14 */
push(my_stack, "foo");          /* stack now contains: 14 foo */
push(my_stack, 999);            /* stack now contains: 14 foo 999 */
x = pop(my_stack);              /* x = 999, stack contains 14 foo */

这是一种抽象数据类型:我定义了一个新类型，一个堆栈，并为您提供了一个抽象接口。也就是说，我以Stack的形式给出了组成数据类型的数据对象，正如您所说的那样，我给了您make_stack、push和pop函数来操作它。

堆栈可以完全由列表、数组、堆或其他东西实现，并且没有外部可见的方法来知道什么。您所知道的就是有一个特定的API与它一起使用，并且API保证了您得到类似堆栈的行为。此堆栈是一种抽象数据类型。