質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

Q&A

解決済

7回答

848閲覧

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

mr0237

総合スコア164

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

1グッド

1クリップ

投稿2019/07/29 14:12

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

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

と書かれており、さらに

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

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

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

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

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

DrqYuto👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答7

0

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

ですが、

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

と書いてありますけど。

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

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

投稿2019/07/29 14:28

otn

総合スコア84423

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

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

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

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

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

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

(中略)

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

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

投稿2019/08/04 03:28

swordone

総合スコア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
xebme

総合スコア1081

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

スタックにせよキューにせよ、

  • 任意個数のデータを保持しておくことができる
  • データには順序が付けられて保持されている
  • データの出し入れは順序に従って行われる

という点を抑えておけば、実際のデータの保管方法については、使う側が知っている必要はありません。
構築する側からすれば、やろうと思えばデータベースのテーブルを使ってキューやスタックを実現することもできます。

スタックやキューといった、入出力だけを定義する(インターフェース)だけで、実装は隠蔽されているとすれば、それは抽象的と言ってよいのかと思います。

投稿2019/07/29 23:37

tacsheaven

総合スコア13703

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

サイトを読んだ限りでは、特定の構造のデータストアを特定の方法で
アクセスできるようにするアプローチをそう呼んでいる気がします。

そういう意味ではデータベースも抽象データ構造ということに
なりそうですが、ここで論じるにはなじまないかな。

データの扱いをオブジェクト指向っぽい考え方をしたようなやつ
に見えます。

投稿2019/07/29 22:40

takasima20

総合スコア7458

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

スタックが抽象データ構造と言い切るには、リアリティが有りすぎ(構造がシンプル過ぎ)と思いますが、外から見えるデータ構造とは、独立した内部データ構造を持てるという意味では、[抽象]かも知れません。

ただ、スタックが抽象データ構造と言うのは、あまり聞きません。

投稿2019/07/29 15:06

pepperleaf

総合スコア6383

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mr0237

2019/07/29 22:19

>外から見えるデータ構造とは、独立した内部データ構造を持てる すいません。これってデータ構造の内部に独立したデータ構造を持てるということでしょうか?
guest

0

Wikipediaによると

抽象データ型の概念に非常に近い

と書かれており、抽象データ型は

データ構造とそれを直接操作する手続きをまとめてデータ型の定義とすることでデータ抽象[1]を実現する手法またはそのひとまとまりとして定義されたデータ型

云々と書かれているので、まぁ少なくとも内部実装は意識しないもんだと思います。

スタックもキューもその「外部から見たデータ構造と振る舞い」の説明どおりに動いていれば、色んな言語で色んな内部実装があろうかと思いますので、そういう意味では「抽象データ構造」なんでしょう。

投稿2019/07/29 15:49

gentaro

総合スコア8949

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問