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

書籍やサイトに書かれている内容は分かる（見た目）のですが、
だから何なのでしょうか？

どういったことに応用が効きますか？
難しい事はわからないので具体例を示していただけると助かります。


宜しくお願いします。

No.1 回答者： Situgyosya 回答日時： 2008/10/27 15:35

高度に抽象的なコードや、ハードウエアの

近隣のコード、構文解析以外ではほとんど使いません。

>どういったことに応用が効きますか？

スタックはUndoやブラウザの履歴(戻るボタン処理)
等に応用可能ですが、別にスタックでなくては
ならないというほどのことではありません。
キューは、単一の出力に対して複数の
アクセスが想定できる場合などに使いますが、
プロでないかぎり必要となる機会は、まずないでしょう。

この回答への補足

よく図入りの説明を見ると、なるほどとは思うのですが、
実際のプログラムは特殊なのでしょうか？
書籍見ても本見てもスタックやキューのプログラムを見ないので
どういったものが、スタックやキューを用いているプログラムなのか
わかりません。初級者でもわかるようなプログラムで教えてください。

補足日時：2008/10/27 15:51

No.2 回答者： Tasuke22 回答日時： 2008/10/27 15:58

パソコンのファイルはOSがHDD上でキューで持って

いますね。ですから、何箇所に分かれたりしても
続けて読み書きが出来ます。ちと、こじつけ？

スレッドがCPUの空き待ちはキューイングされます。
優先順位の高いスレッドが来たら、それより優先
順位が高いか同じスレッドの待ちの後ろに付けま
す。キューだと割り込みも簡単です。

QAM/QAMSというキューアクセスメソッド/キューア
クセスメソッドサービスというデータ管理が三菱の
制御用コンピュータにあります。
制御系には大いに役に立つ場面があるでしょう。

シミュレーションなどにも役に立ちそうですね。

今はデータベースといえばRDB（リレーショナルデー
タベース）が花盛りですが、NDB（ネットワークデー
タベース）もやはり制御系には多いですね。
NDBの構造はキューとしての利用も簡単です。
QAMには負けますが。

実際、工場では、例えば製鉄ですと、圧延する鉄の
塊が圧延待ちでキューイングされて、圧延されると、
リアルタイムで形状がデータベース上で形状が変わ
り、伸びた長さによって、全オーダから無駄が無い
ようにかつ納期に間に合うようにカットし、１つの
データが複数のデータになり、不良品は修理にキュー
イングされ、いいものは仕上げ工程にキューイング
され・・・・・とキューイングこそ制御といえる
かもしれません。

No.3 回答者： Tacosan 回答日時： 2008/10/27 17:05

C で関数を呼び出したときの情報は (言語使用には書いてないけど実質的に) スタックで管理されます. だから, プログラム上で意識することはないとしても事実上常にスタックのお世話になっているということができます.

キューは.... ウィンドウシステムにおけるユーザの操作はいったんキューに入り, そこからしかるべきプログラムに送られるのが普通です. このようにして, (基本的に) ユーザが操作した順番に処理が行われることを保証しています.

この回答への補足

なるほど・・
では知らず知らずに配列使ったプログラムを書いているだけで
実は裏でスタックを意図した動きをしている、っていうことなんですね？

補足日時：2008/10/27 17:32

No.4 回答者： asuncion 回答日時： 2008/10/27 18:14

> 本見てもスタックやキューのプログラムを見ないので

そうですか？
アルゴリズムの入門書で、
スタックやキューについて解説している本は
いくらでもあります。

この回答への補足

読んだ本は初心者向けのC言語の本1冊でFIFOとLIFOの図入り説明が計1ページあった程度ですよ。

そりゃどこかにあるかもしれませんね。
あるある言っても、該当書を挙げなければ回答にすらなりません。

補足日時：2008/10/28 09:03

No.5 回答者： annyG 回答日時： 2008/10/27 21:14

簡単な話で、

「スタックやキューを使わないと面倒なとき」に「スタックやキューは
便利」です。

　例えば、ファイルから読み込んだ文字列をいったんため込んでおき、
先頭行から処理をするような場合。
　各行の内容を配列に格納すると、ループカウンタが必要になります。

　ですが、キューに保存しておけば、キューの先頭から1行ずつ
取り出して処理をしていけばいいので、ループカウンタとか、
今配列のどこを指しているのかなどは一切考えなくてもよいので
気楽です。
　スタックもキューも、別にそれを使わなければ処理ができない
わけではないので、使いたいと思わない人は使わなければいいだけの
話です。私はスタックやキューが好きですから使いますが、使わない、
使ったことがないという人はプロでも多いと思います。

この回答への補足

スタックを使う、とありますが、これは概念なのでしょうか？

実際に本（C言語の入門書）を見てもFIFO,LIFOの図入り説明程度でして、
じゃあ実際にどういうものなの？と気になってもそれに対する説明が
ないものです。

広義に見て、メモリのように意図して使えるものなのか、
それとも、概念であり、意図せずに使わざるを得ない状態にあるのか、
使っているとはどういう状況を言うのかが明示的に説明されておらず、
さっぱりわかりません。

ですので、実際にコードを見て、これがスタック＆キューを用いている
と解るようなものがあれば・・・と思っているのです。

言葉より絵（コード）で。

補足日時：2008/10/28 09:07

No.6 回答者： hidebun 回答日時： 2008/10/27 21:51

応用ですか。

あくまで一例ですが…。
たとえば、ソフトを使っていて、
「あ、操作間違えた。元の状態に戻そう。」なんてこと、ありませんか？
操作をしたら、その都度、ソフトの内部状態をスタックにpushしておき、
ユーザーが「元に戻す」を押したら、スタックからpopして、１つ前の状態に戻す、なんてことをするのに使えます。

プリンターなんかは、キューを使ってるんじゃないかな。
プリンターが、プリントする速度はコンピュータのデータ転送速度に比べれば、
ずいぶん遅いですが、コンピュータがデータ送信をして印字が終わるのを待っていたら、
まったく仕事できません。というわけで、プリンターは、
コンピュータからデータが送られてきたら、データを一旦キューに
溜め、「印字を承りました」といって、処理をコンピュータに
返します。その後、プリンターは、キューからデータを取り出して印字を続けます。

まあ、感覚的にはこんな感じでしょうか。

No.7 回答者： Interest 回答日時： 2008/10/28 01:18

キュー（FIFO)を使う例として、通信を例にあげて説明します。

PC1の上で動作しているアプリケーションAP1からPC2の上で動作しているアプリケーションAP2に対してデータを送信することを考えてみましょう。

(1) AP1は通信速度がどれくらいか知らないけれどとにかく順番通りにデータを送信したい。そこでAP1はPC1の通信手段の送信バッファに「送りたい順番で」データを書き込みます。
(2) PC1の通信手段は送信バッファに書き込まれたデータを「先頭から順に取り出して」AP2に送信します。
(3) PC2の通信手段はPC1から送られてきたデータを受信して、受信バッファに「受信した順に」書き込み、AP2に対してデータを受信したことを知らせます。
(4) AP2はPC2の受信バッファの「先頭から順に」データを取り出します。

これで、AP1からAP2に順番通りにデータを送信することができました。
ここで登場した送信バッファ、受信バッファはデータ構造で見るとキュー構造でできています。ここで、キューだと何が嬉しいか考えてみましょう。

送信バッファがキュー構造（FIFO)ならば、アプリケーション側はこれまでデータをいくつ書いたか覚えていなくても、とにかく最後尾にデータを書き込めば通信手段がデータを順番通りに送り出してくれます。
受信バッファがキュー構造（FIFO)ならば、アプリケーション側が受信バッファにたまっているデータがいくつあるか知らなくても、とにかく先頭から読み出せば受信した順番通りにデータを取り出すことができます。

このような通信は、USBやRS-232Cのようなシリアル通信だけでなく、ハードウェアを制御する場合やプログラムとプログラムが通信する場合でもほぼ同様の仕組み（FIFO)を使用してデータのやり取りを行います。

この回答への補足

なるほど、コンビニのジュースの棚と同じ原理ですね。

補足日時：2008/10/28 09:47

No.8 回答者： hidebun 回答日時： 2008/10/28 10:15

>スタックを使う、とありますが、これは概念なのでしょうか？

あ、そうです。
原理が last-in-first-out (LIFO) であれば、それはスタック。
原理が first in first outであれば、それはキューです。
中に何を入れるかは、あなた次第。

この回答への補足

では、ポイントのようにC言語で表わされる形としては存在しない、
と考えてよいのでしょうか？

それとも、スタックやキューはこういうふうに使うもの、とある
のでしょうか？（概念だけなら無い事になりますね。）

補足日時：2008/10/28 11:47

No.9 回答者： hidebun 回答日時： 2008/10/28 13:01

C言語の文法に、stackとかqueueみたいなものはないですね。

C++なら、標準ライブラリにstackやqueueはありますけど。

No.10 ベストアンサー 回答者： Interest 回答日時： 2008/10/28 22:17

> スタックを使う、とありますが、これは概念なのでしょうか？

そのとおりです。なので、実装の仕方は必要に応じて変わります。

> 言葉より絵（コード）で。

そうですね。ではリクエストにお答えします。以下、SH2マイコンのシリアル通信に関するソースコードの一部です。SH2がシリアル通信(UART)でデータを受信する際に呼び出される受信割り込みハンドラと、受信割り込みハンドラがため込んだ受信データを読み出すための関数です。

/**
*SCI1受信割り込みハンドラ
*/
#pragma interrupt( SCI1_rxi_int_handler )
void SCI1_rxi_int_handler(void)
{
　char　data;
　data = SCI1.SCRDR;　　　　　// 受信データを取り出す
　SCI1.SCSSR.BIT.RDRF = 0;　　// 次の受信に備える

　FIFO_put( (rxBuffer + 1) , data);　// 受信バッファに貯め込む
}

/**
*SCI から受信データを読み込む。
*/
int SCI_read(char ch, char *buf, int len)
{
（中略）
　for(i=0; i<len; i++){
　　ret = FIFO_get( (rxBuffer + ch), &c ); 　// 受信バッファから１つずつ取りだす
　　if( FIFO_OK == ret ){
　　　　*buf = c;
　　　　buf++;
　　}
　　else if( FIFO_ERROR_EMPTY == ret )// これ以上読み込むデータがない
　　　break;
　　else{
　　　　i = SCI_ERROR_FATAL;　　// FIFOの初期化ができていない場合など
　　　　break;
　　}
　}
　
　set_imask( mask );　　　　// 割り込みマスクを戻す
　return i;　　　　　　　　　// 読み込んだデータ数を返す。
}

ついでにFIFOはこのような構造を使いました。

/// データ構造の定義
typedef struct{
　int　　rp;　　　　　// 書き込み位置
　int　　wp;　　　　　// 読み出し位置
　char　*buffer;　　　// データ保存領域へのポインタ
　short　bufferSize;　// データ保存領域の大きさ
}FIFO;