问我对抽象数据类型的理解正确吗？

EN

你正确地理解了这一点。ADT是可移植的理论结构，然后可以在大多数给定的编程语言中实现。

示例:堆栈

作为ADT的堆栈是一种类型的列表，它提供了对其数据成员的Last，First Out (LIFO)访问。因此，只能在堆栈的“顶部”点访问它。

在Python中，它看起来类似于：

class Stack:

    def __init__(self): # initializes the stack with an empty list to hold stuff
        self.list = []

    def push(n): # pushes item n onto the stack
        stack.list.append(n)

    def pop: # removes the "top" item from the stack
        del stack.list[-1]

    def peek: # looks at the top item of the stack
        view = stack.list[-1]
        return view

这应该是一种实现基本堆栈的方法。我还没有测试过这段代码，所以请自己承担风险。实际上，Python希望您在默认情况下将列表作为堆栈使用，因此教程文档将对其进行介绍。甚至有一个内置的“流行”方法。

通常，您会将堆栈实现为数组或链接列表。如果您想要更少的内存开销，并且通常更容易编写代码，这个数组就会很有用。然而，基于列表的堆栈可以更容易、更快地扩展。

这只是一个主题的要点，我强烈建议遵循这里的链接。

“抽象数据类型定义了一组抽象对象，这些抽象对象的特征完全取决于这些对象上可用的操作。这意味着可以通过定义该类型的字符操作来定义抽象数据类型。”Liskov :用抽象数据类型编程。

考虑到上面非正式的定义，以下伪代码可以看作是ADT：

type stack;
stack stack_create();
void stack_push(stack, T);
T stack_pop(stack);

有一点是，对堆栈对象一无所知，只有可用的操作可以推断出什么--在上面的例子中，是stack_create、stack_push和stack_pop。实现和结构细节的每一点都留给实现方。

现在，使用一个名为Stack的OO/python类，并使用push和pop方法。

class Stack:

    def __init__(self):
       ...
    def push(self, element):
       ...
    def pop(self):
       ...

如果它的客户端知道有一个名为Stack的类，并且他们可以访问它，那么查看它的一种方法是，对象的特点是它们是类Stack的实例，其结构包含push和pop字段--而不管它们是可调用的。客户端还知道，他们可以从Stack继承来创建其他东西，等等。

也就是说，更多的人知道/接触到客户。因此，这个Stack类型比前一个类型抽象得多(它公开为一个具有两个字段的具体结构，有一个类，您可以使用它进行继承，等等)。因此，可以说这种Stack类型不是符合给定定义的抽象数据类型。为了更严格，人们必须写这样的东西：

def create_stack():
   ...
def stack_push(stack, element):
   ...
def stack_pop(stack):
   ...

下面是它的一个可能的实现(在下面的例子中，如果您已经拥有上面的类，并且只想使它成为一个ADT，那么它只是一个包装器)：

def create_stack():
   retur Stack()
def stack_push(stack, element):
   return stack.push(element)
def stack_pop(stack):
   return stack.pop()

现在，客户端只知道操作及其接口，并使用它们(并且只有它们)推断什么是“堆栈”类型。从外部看，不知道堆栈的实际实现和结构(除非它们通过检查create_stack结果的结构而违背抽象)。

类似地，在C中，您可以通过将这些函数声明放在.h头文件(使用作为堆栈类型的前向声明，或简单地使用void*)，然后将结构定义和函数实现放在.c文件中来模拟。

关于类型系统的注意事项:当然，上述所有内容都不适用于具有静态类型检查和良好类型系统的语言-这类语言可能需要提供某些工具，以使合理的ADT成为可能。此外，在上面引用的文件中，“强”类型检查的方式似乎仅仅是作者偏好的问题；我没有看到它们被讨论或显示为ADTs的一个要求--文本在讨论类型检查时似乎非常谨慎，因为它们是相关的，但并不重要。另外，“ADT的C方法”的解释(见上文)是由撰写面向对象编程与抽象数据类型的研究人员William提出的。另一方面，编辑：库克写：

“抽象数据类型依赖于静态类型系统来实施类型抽象。动态语言使用对象而不是用户-defined抽象数据类型并不是偶然。动态语言通常支持原语类型内置的抽象数据类型；此处的类型抽象由运行时系统强制执行。”

不幸的是，在抽象数据类型和对象方面存在许多混淆。

我认为OP使用的是“抽象数据类型”这一短语，好像它意味着“数据抽象”，或者只是定义抽象数据的一般意义。

抽象数据类型是数据抽象的一个非常具体的实现，最好在语言ML中实现。对象是另一种数据抽象形式。

你可以在我的报纸上读到更多这方面的内容：

http://www.cs.utexas.edu/~wcook/publications.htm#oo