キューの実現方法

質問

配列によるキューの実現方法、リストによるキューの実現方法の二つのキューの実現方法について教えてください。
またその二つの長所、短所等もできればお願いします。
自分は大学院生ですが、化学が専攻なためパソコンやプログラムに関してあまり知識がありません。
文献等見てみたのですが、あまり意味がわかりません。
わかりやすく教えてもらえればうれしいです。
すいませんがよろしくお願いします。

回答No.4

ymmasayan

「キュー」は待ち行列です。先入れ先出し（ＦＩＦＯ：First In First Out）
が特徴です。配列とリストをご存知のようなので、それをベースに説明します。
簡単のために、キューにはデータのキーだけを登録するものとします。
キューの最大数は一応１００個とします。

配列型（１）・・先頭から登録する。先頭から取り出していく。先頭部が空くと、
　　　　　　　前詰を行なう。　　　　　
配列型（２）・・先頭から登録する。先頭から取り出していく。先頭部が空いても放
　　　　　　　置する。後尾部の次の登録は先頭に行なう。

リスト型・・・・・配列はとらない。（とる方法もある。）キューが発生するごと
に１件分のメモリーをＯＳまたはメモリ管理サブに要求。
順番管理はアドレスチェーン（ポインタ）で行なう。配列番号でも出来る。

配列型は待つための椅子を１００席準備している。
（１型）は前に詰め合わせて待たせる。
（２型）は詰め合わせず、円形に使わせる。
リスト型は待つ場所の指定はない。チェーン番号を示す番号札を与える。

ここまでが概要説明です。

あとは長短。
配列１型・・・判りやすいが詰め合わせロスが多い。管理はキュー個数１個のみ。
配列２型・・・詰め合わせはないが、わかりにくい。管理は先頭と次の登録の２つ
　　　のポインタ。ラップアラウンド（最後尾から先頭への戻り処理）がポイント。
リスト型はキューの大きさは事実上無制限。途中で増減することだって出来る。

最後に、途中への割込み、途中からの離脱なども容易に処理できる、リスト型が万能のキュー実現形態だと言っても良い。（目的によることをお忘れなく）

回答No.3

taknt

＞またその二つの長所、短所等もできればお願いします。

プログラミングの仕方が違うだけだと思うので、どっちもどっちかなと思います。

回答No.2

imogasi

(1)Amazonなど本を注文するサイトで「データ構造」「アルゴリズム」等で書名検索をして、貴大学図書館で本を借りるか、購入して読むべし。
（２）同じく「データ構造」「アルゴリズム」でWEB検索するべし。沢山出てきますよ。
OKWEBなんて限られた短いスペースでは充分説明できるほど
の単純なテーマではないと思うので。
（３）モデル的考え方と特定の言語（例　C言語）でコンピュタ上で実現する方法と両方が必要です。
http://www.morikita.co.jp/soft/kiriyama/8399/

回答No.1

taknt

実現方法の前に キューというものを ちゃんと理解してるかどうかが問題ですね。
理解してればおのずとわかると思うのですが・・・。

ま、配列を使ったキューの説明をしましょう。

配列でたとえば、１００個の領域を確保したとしましょう。
その領域に１個キューが入ります。すると１番目になりますね。
で、どこまで取り出したかというポインタがあって、それが最初なので１番目になってます。取り出すほうは、そのポインタをもとに取り出してきます。
キューを入れるほうは、入れたポインタというのを参照して、今、一個入れたから、ポインタが ２になってて、次入れるときは、そのポインタを見て入れます。
２なので２番目に入れるということです。
取り出すほうが 取り出すポインタと入れるポインタが同じかチェックして
同じだと取り出すものがないと判断してキューがないと判断します。
んで、１００個を超えたときは、１に戻ります。
入れるときに取り出すポインタと入れるポインタが一緒になったら、入れる場所がないので、エラーとなって入れることができません。
一般的に、この領域のサイズをこのエラーが生じにくいぐらいの大きさに設定しておきます。
ま、こんな感じなんですけど、わかったかな？