• 締切済み

スタック、キュー、リスト、2分木の使い道は？

主な定番データ構造として (1)スタック (2)キュー (3)リスト (4)2分木 これらのデータ構造がありますが、特に「スタック」と「キュー」は一体何に使えるのでしょうか？ 「スタック」や「キュー」は使い道が思いつかないのですが、一体何に使えるのですか？ データ構造である「スタック」「キュー」「リスト」「2分木」の使い道を教えてください。 よろしくお願いいたします。

みんなの回答

  • ubku
  • ベストアンサー率37% (227/608)
回答No.1

スタックは戻り先を覚えておくのに向いています。 return で元の処理に戻れるのは、ジャンプ（CALL）の時に自動的に戻り先をスタックに積んであったからです。ジャンプ先でさらにジャンプした場合でもスタックなら一番上からひとつずづ取り出すだけで、キレイに元の処理に戻れます。 また、プログラム処理中にもCPUには絶えず割り込みが入ります。キーが入力されたとか、マウスが動いたとか、ユーザーが気付かないバックグラウンドの処理とか、OSが処理する割り込みは膨大です。それらは全て、戻り先をスタックに積んでから行い、割り込み処理が終わったら、スタックから取り出した戻り先に戻る、ということが自動的に行われています。 キューは順番待ちの処理に向いています。プリンターの印刷待ちがわかりやすい例です。簡単ですね。 リストはデータの途中への追加・削除が高速に出来るので、HDDのデータ保存に使われています。 二分木は検索が高速に出来るので、大規模なデータの検索を行うような場面で使われます。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. その他([技術者向] コンピューター)

関連するQ&A

  • スタックとキューの使い所

    こんにちは。つい二ヶ月前くらいにVBを始めた初心者なのですが、データ構造で、スタックとキューの二つのデータ構造の特徴（長所＆短所）と、この二つを使うときというのは例えばどういう時なのかが全然わかりません。どなたかぜひ、教えていただけないでしょうか？

  • キューとスタックの問題です、宜しくお願いします

    　（多分基本情報処理に関する問題だと思うのですが）データ構造に関する問題です、いくら考えても分かりません、宜しくお願いします。 【問】空の状態のキューとスタックの二つのデータ構造がある。 次の手続きを順に実行した場合、変数xに代入されるデータはどれか。 ここで、 ・データｙをスタックに挿入することをpush（ｙ） ・スタックからデータを取り出すことをpop（ ） ・データｙをキューに挿入することをenq（ｙ） ・キューからデータを取り出すことをdeq（ ） と表す。 (1)push（a） (2)push (b) (3)enq(pop( )) (4)enq（c） (5)push（d） (6)push（dep( )） (7)pop（ ） → x 以上の答えとして(6)にはｂがスタックにpushされるので、後入れ先出し を考えると当然「xにはb」が入るはずなのですが、どうも答えは「ｄ」となっています。 「ｄ」は「ｂ」より前にスタックされてますので、最新で取出される情報は「b」しかないと思うのですが、誰か誤りを指摘してください、宜しくお願いします。

  • ｃ言語　リストデータ構造　キュー　スタック　がわかりません

    ポインタを用いた線形リストデータ構造を利用して，キーボードから順に入力した複数の整数値（int型）を空の「スタック」および「キュー」にそれぞれ保存し，取り出した時，出力される整数値を順に表示するプログラム． 動作確認のために入力する整数値は，年号と月の数字の部分とせよ（2008年5月なら，「2→0→0→8→0→5」の順）．また，スタックとキューに保存されているデータがどのような順で出力されるかをそれぞれ表示するようにせよ．（スタックの場合は「5→0→8→0→0→2」の順で出力され，キューの場合は「2→0→0→8→0→5」の順で出力されることを表示させ確認せよ） こうのようなプログラムを作らなくてはいけないのですが、まったくわかりません。参考にでもソースを教えていただけないでしょうか？ また、詳しく解説されている(初級と中級レベルそれぞれについて)サイトや書籍がありましたらそちらもお願いいたします。

  • キューとスタックについて

    キューとスタックについて質問です。 abcと言う文字列があった場合、キューとスタックで何通りの取り出し方が出来るかと言う問題があります。 スタックについては5通りで納得しているのですが、キューは私は1通りだと思うのですが、 友達は3通りだと言います。 1通りと3通りのどちらが正解なのでしょうか。

  • スタックとキュー

    スタックにデータを積む関数push、データを取り出す関数push、キューにデータを積む関数enqueue,データを取り出す関数dequeueを作成しろという課題がでたのですが、関数がさっぱりわかりません。あと、popやpushの他に関数は作らなければ動きませんか？メインはなんとかできそうです。

  • C言語のリスト、スタック、キュー、逆ポーランド法など

    リスト、スタック、キュー、逆ポーランド法などプログラム例ののったサイト知りませんか？どうしてもわからないのですどうか教えてください。

  • 2分木と双方向線形リストを同時に実現する方法

    ファイルに書かれている文字列を読み込み， (1)ソートしてファイル出力 (2)読み込んだ順と逆順にファイル出力 というプログラムを作成する場合， (1)は２分木のデータ構造を用いて実現したのですが，２分木のデータ構造をそのまま利用することで逆順に出力させることは可能でしょうか？ 私は無理だと思うので，２分木に加えて双方向の線形リストになるようにポインタを設定する必要があると考えているのですが，もっと上手く実現するアルゴリズムはあるでしょうか？ アドバイスを頂けるとありがたいです．

  • リストや木についての質問

    リストや木等のデータ構造（？）は ポインタのつなぎ方みたいな物なのでしょうか？？ それとも、それには何か特別な関数（メモリー確保を除く）が必要なのでしょうか？？

  • スタックモジュール

    「スタックモジュール」を作ることを考える。データ構造の定義と、以下の操作の定義を書け。ただしC言語を使え。 create 空のスタックを作る push スタックにデータを一つ挿入 pop スタックトップのデータを返すとともに、そのデータをスタックから削除 という問題です。 私は、C言語でのスタック構造は配列でしか扱ったことがなく、「スタックモジュール」の意味がよくわかりません。スタック構造はFILOのデータ構造ですが、これをC言語で書こうとすると配列を宣言して終わってしまう気がします。 create・push・popは、int (&num){......}のように普通に関数を宣言すればよいのでしょうか。 どなたか教えてください。

  • スタックとキューの違いを示すプログラム。

    学校でスタックとキューの違いを示せという課題が出たのですが、どうしてもわからなかったので、苦し紛れに質問させていただきました…。 いろいろ情報を集めて分からないながらにも以下のプログラムを書いてみたのですがスタックはできてもキューが実現できません。 あまり内部の処理を書き変えずに以下のスタックのプログラムをキューに書き換えたいのですがどうしたらいいでしょうか？ ポインタを利用した連結リスト構造です。 #include <stdio.h> #include <stdlib.h> struct Cell//構造体Cellの定義 { int element; Cell* p_prev; Cell* p_next; }; void Cell_Initialize(Cell* p)//要素を初期化用 { p->element = -1; p->p_next = NULL; p->p_prev = NULL; } void Push(Cell* p, int val) { Cell* p_temp = p; while(1) { if(p != NULL) { if(p_temp->p_next == NULL) { p_temp->p_next = (Cell*)malloc(sizeof(Cell));//新しいセルを作成するときのメモリの確保 Cell_Initialize(p_temp->p_next);//初期化 p_temp->p_next->element = val; p_temp->p_next->p_prev = p_temp; break; } else { p_temp = p_temp->p_next; } } } } int Pop(Cell* p) { Cell* p_temp = p; int temp; while(1) { if(p != NULL) { if(p_temp->p_next == NULL) { break; } else { p_temp = p_temp->p_next; } } } if(p_temp->p_prev != NULL) { temp = p_temp->element; p_temp->p_prev->p_next = NULL; free(p_temp); p_temp = NULL; return temp; } else if(p_temp->element != -1) { temp = p_temp->element; Cell_Initialize(p_temp); return temp; } return -1; } void main() { Cell* p_list = NULL; p_list = (Cell*)malloc(sizeof(Cell)); Cell_Initialize(p_list); for(int i = 1; i < 7; i++) { int temp; printf("%d文字目入力してください：",i); scanf("%d",&temp); Push(p_list, temp); } while(1) { int temp = Pop(p_list); if(temp != -1) { printf("[%d]\n\n",temp); } else { break; } } } 長文になってしまいすみません。 どなたかよろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する