スタック | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第5章
のサイトにて
これらの機能を持ってさえいれば、スタックが内部的にどのような形でデータを管理していても構わないといえます。このように、必要な機能の要件だけが定義されているようなデータ構造を、抽象データ構造と呼びます。
と書かれており、さらに
スタックは、抽象データ構造なので、内部のデータの管理方法には自由度があります。
と書かれておりますが、スタック・キュー等のデータ構造を「抽象データ構造」と言うんでしょうか?
そもそも**「抽象データ構造」って何なんでしょうか?**
私自身の大雑把な考えですが、
内部的に「データ構造」とその「操作のまとまり」がある形式の「データ型(構造)」
ということなんでしょうか?
分かりやすい例えで教えてください。よろしくお願いいたします。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答7件
0
そもそも「抽象データ構造」って何なんでしょうか?
ですが、
必要な機能の要件だけが定義されているようなデータ構造を、抽象データ構造と呼びます。
と書いてありますけど。
内部的に「データ構造」とその「操作のまとまり」がある形式の「データ型(構造)」
内部のデータ構造が明確になっていれば、すでに「抽象」じゃないですね。
ブラックボックスと思えば良いのでは無いでしょうか。
投稿2019/07/29 14:28
総合スコア84423
0
ベストアンサー
以前の質問からずっと言っていますが、文章をしっかり読みましょう。
その部分だけを読むのではなく、その周辺まで含めてしっかり文脈を取ってください。
このように、必要な機能の要件だけが定義されているようなデータ構造を、抽象データ構造と呼びます。
「このように」と書いているのですから、例示はその直前にきちんと示されているはずです。
スタックというデータ構造にとって、最低限必要な機能は以下のとおりです。
- データを積む (push)
- データを降ろす (pop)
- スタックが空かどうか調べる (is_empty)
(中略)
これらの機能を持ってさえいれば、スタックが内部的にどのような形でデータを管理していても構わないといえます。
push,pop,is_emptyという機能の抽象的な要件だけを設定していますが、具体的にどのように実現するかについては一切言及していません。
こんな風に、「何ができるか」だけを決めているものが「抽象データ構造」といえるでしょう。
「スタック」などは、これらの構造をもつもの、あるいは構造自体に付けた名前にすぎません。
投稿2019/08/04 03:28
総合スコア20649
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
抽象データ型
抽象データ型(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総合スコア1081
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
スタックにせよキューにせよ、
- 任意個数のデータを保持しておくことができる
- データには順序が付けられて保持されている
- データの出し入れは順序に従って行われる
という点を抑えておけば、実際のデータの保管方法については、使う側が知っている必要はありません。
構築する側からすれば、やろうと思えばデータベースのテーブルを使ってキューやスタックを実現することもできます。
スタックやキューといった、入出力だけを定義する(インターフェース)だけで、実装は隠蔽されているとすれば、それは抽象的と言ってよいのかと思います。
投稿2019/07/29 23:37
総合スコア13703
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
そもそも「抽象データ構造」って何なんでしょうか?
サイトを読んだ限りでは、特定の構造のデータストアを特定の方法で
アクセスできるようにするアプローチをそう呼んでいる気がします。
そういう意味ではデータベースも抽象データ構造ということに
なりそうですが、ここで論じるにはなじまないかな。
データの扱いをオブジェクト指向っぽい考え方をしたようなやつ
に見えます。
投稿2019/07/29 22:40
総合スコア7458
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
スタックは、抽象データ構造なので、内部のデータの管理方法には自由度があります。
スタックが抽象データ構造と言い切るには、リアリティが有りすぎ(構造がシンプル過ぎ)と思いますが、外から見えるデータ構造とは、独立した内部データ構造を持てるという意味では、[抽象]かも知れません。
ただ、スタックが抽象データ構造と言うのは、あまり聞きません。
投稿2019/07/29 15:06
総合スコア6383
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。