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

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

ただいまの
回答率

87.35%

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

解決済

回答 7

投稿

  • 評価
  • クリップ 1
  • VIEW 1,205

score 162

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

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

と書かれており、さらに

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

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

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

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

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 7

+5

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

ですが、

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

と書いてありますけど。

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

+3

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

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

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/07/30 07:19

    >外から見えるデータ構造とは、独立した内部データ構造を持てる

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

    キャンセル

+1

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

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

--> 引用

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

Stack

台:
A, Stks[A], Boolean, Erros

演算:
emptyStk ∈   Stks[A]
isEmptyStk: Stks[A] -> Boolean
push: A × Stks[A] -> Stks[A]
pop: Stks[A] -> Stks[A] ∪  Errors
top: Stks[A] -> A ∪  Errors

公理:
isEmptyStk(emptyStk) = True
isEmptyStk(push(a,s)) = False
pop(push(a,s)) = s
pop(emptySyk) = stackError
top(push(a,s)) = a
top(emptyStk) = valueError


<--- 引用終わり

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

Wikipediaによると

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 87.35%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る