スタック・キューは、抽象データ構造?　そもそも抽象データ構造とは何か？

スタック | Programming Place Plus　アルゴリズムとデータ構造編【データ構造】　第５章
のサイトにて

これらの機能を持ってさえいれば、スタックが内部的にどのような形でデータを管理していても構わないといえます。このように、必要な機能の要件だけが定義されているようなデータ構造を、抽象データ構造と呼びます。

と書かれており、さらに

スタックは、抽象データ構造なので、内部のデータの管理方法には自由度があります。

と書かれておりますが、スタック・キュー等のデータ構造を「抽象データ構造」と言うんでしょうか？

そもそも**「抽象データ構造」って何なんでしょうか？**

私自身の大雑把な考えですが、
内部的に「データ構造」とその「操作のまとまり」がある形式の「データ型（構造）」
ということなんでしょうか？

分かりやすい例えで教えてください。よろしくお願いいたします。

回答7件

そもそも「抽象データ構造」って何なんでしょうか？

ですが、

必要な機能の要件だけが定義されているようなデータ構造を、抽象データ構造と呼びます。

と書いてありますけど。

内部的に「データ構造」とその「操作のまとまり」がある形式の「データ型（構造）」

内部のデータ構造が明確になっていれば、すでに「抽象」じゃないですね。
ブラックボックスと思えば良いのでは無いでしょうか。

投稿2019/07/29 14:28

otn

総合スコア81155

ベストアンサー

以前の質問からずっと言っていますが、文章をしっかり読みましょう。
その部分だけを読むのではなく、その周辺まで含めてしっかり文脈を取ってください。

このように、必要な機能の要件だけが定義されているようなデータ構造を、抽象データ構造と呼びます。

「このように」と書いているのですから、例示はその直前にきちんと示されているはずです。

スタックというデータ構造にとって、最低限必要な機能は以下のとおりです。

データを積む (push)
データを降ろす (pop)
スタックが空かどうか調べる (is_empty)

(中略)

これらの機能を持ってさえいれば、スタックが内部的にどのような形でデータを管理していても構わないといえます。

push,pop,is_emptyという機能の抽象的な要件だけを設定していますが、具体的にどのように実現するかについては一切言及していません。
こんな風に、「何ができるか」だけを決めているものが「抽象データ構造」といえるでしょう。
「スタック」などは、これらの構造をもつもの、あるいは構造自体に付けた名前にすぎません。

投稿2019/08/04 03:28

swordone

総合スコア20617

抽象データ型
抽象データ型(ADT,Abstract Data Type)を紹介します。

『独習コンピュータ科学基礎II 論理構造』 James L. Hein 翔泳社より引用。

--> 引用

抽象データ型は、1つ以上のオブジェクトの集合とその集合上に定義されたひとつ以上の演算、演算を記述する若干の公理からなる。抽象データ型とは代数のひとつである。抽象データ型の台には制限がある。台はデータオブジェクトと演算がコンピュータ上で実装できるように構成する。抽象データ型は、実装の詳細を抽象化する。

code
1Stack
2
3台：
4A, Stks[A], Boolean, Erros
5
6演算：
7emptyStk ∈   Stks[A]
8isEmptyStk: Stks[A] -> Boolean
9push: A × Stks[A] -> Stks[A]
10pop: Stks[A] -> Stks[A] ∪  Errors
11top: Stks[A] -> A ∪  Errors
12
13公理：
14isEmptyStk(emptyStk) = True
15isEmptyStk(push(a,s)) = False
16pop(push(a,s)) = s
17pop(emptySyk) = stackError
18top(push(a,s)) = a
19top(emptyStk) = valueError

<--- 引用終わり

本には、Stackだけでなく、台、演算、公理の異なる様々な抽象データ型(List、Queue等)が紹介されています。

台というのは演算が定義される集合です。演算はオブジェクト指向のインターフェイスに相当。振る舞いだけの定義。実装は表現（representation)とよばれます。公理はADTの制約とみなせます。公理は演算を使って定義されます。公理をもとにプログラムの振る舞いを自動チェックできればよいのですが、実装はプログラマが行うのでプログラマが公理を保証します。公理にテストケースが記述されていると思ってください。

参考
バートランド・メイヤー『オブジェクト指向入門第2版原則・コンセプト』 2007年翔泳社
MITに、リスコフの授業が継承されて残っています。Reading10:Abstract Data Types

投稿2019/08/03 23:28

編集2019/08/04 08:22