data-structures - 抽象データ型 (ADT) とは何ですか?

Question

理解できない「抽象データ型」の次の定義に出くわしました。できれば例を挙げて、誰かが説明できますか？

抽象データ型は、データ型を構成するデータ オブジェクトと、これらのオブジェクトを操作する関数の数学的モデルとして定義されます。

Answer 1

いくつかの言語では、それは問題ではありません。私はあなたに次のことを与えることができます：

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

次に、スタックに 3 つの値をプッシュしてから 1 つをポップしたいとします。次のようになります。

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 がスタックのような動作を保証するということだけです。このスタックは抽象データ型です。