data-structures - 什么是抽象数据类型 (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 保证您获得类似堆栈的行为。此堆栈是一种抽象数据类型。