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

Question

書籍やサイトに書かれている内容は分かる（見た目）のですが、
だから何なのでしょうか？

どういったことに応用が効きますか？
難しい事はわからないので具体例を示していただけると助かります。


宜しくお願いします。

Interest · Accepted Answer

> スタックを使う、とありますが、これは概念なのでしょうか？

そのとおりです。なので、実装の仕方は必要に応じて変わります。

> 言葉より絵（コード）で。

そうですね。ではリクエストにお答えします。以下、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;

noname#144013 · Answer

すみません。　#11です。

前記事 #11 に以下の訂正があります。（細かいことですが。。。）

【訂正前】
■キュー処理
１）#7さん と #10さん も書かれていますが、～～～～～

【訂正後】
■キュー処理
１）#7、#10の回答者さん も書かれていますが、～～～～～

※#7さんと#10さんは同じ方でしたね。すみませんでした。

noname#144013 · Answer

こんにちは。私も他の回答者さんと似たような意見になってしまいますが、コメントさせていただきます。以下長文、失礼致します。 > スタックを使う、とありますが、これは概念なのでしょうか？ならびに、 > では、ポイントのようにC言語で表わされる形としては存在しない、 > と考えてよいのでしょうか？ > > それとも、スタックやキューはこういうふうに使うもの、とある > のでしょうか？（概念だけなら無い事になりますね。）の件ですが、確かに「スタックとキュー」は処理の「やり方・考え方」になりますので "概念"になると思います。しかし「やり方・考え方」なので、それを「プログラム」という形にすることは可能だと思います。 > どういったことに応用が効きますか？どういったことに使えるかというよりは、プログラムの設計者が、これから作成すべきプログラムを実現化する際に、ある処理において、ここは「スタック処理」または「キュー処理」を使った方が妥当だと考えた場合に、その方法を用いるといったような使い方になるのではないかと思います。ですので、その使用用途は様々だと思います。スタック＆キューとは別の話ですが、例えばコンソールプログラムを作成する上で画面に文字列を出力したい場合に、printf関数を用いるのが妥当だと考える事と同様な事ではないかと思います。（まあ、printfはその使用用途がハッキリしていますが．．．）強いて具体例を上げるとすれば、 ■スタック処理１）アセンブリ言語でプログラミングする場合に、サブルーチンとの引数のやり取りに　スタック領域を介して行なう。（スタックエリアへのレジスタのPush＆Popなど）２）カードゲーム（トランプなど）をプログラム化するにあたり、場札へのカードの積み　上げ及び場札からカードを引く操作をシミュレーションする場合。　※場札がスタックの箱に相当し、最後に積み上げたカードからカードを引く場合。　．．．など ■キュー処理１）#7さんと #10さんも書かれていますが、通信プログラムにおいて、送受信データを　　貯めておく領域としてキューバッファを使用することがあります。　　メリットとしては、「データ編集処理」と「送信処理」及び「受信処理」を切り分けて　　設計でき単純化できる。そのためデバッグおよびメンテナンスもし易くなる。　　※タイミングとか処理渋滞などをあまり気にしなくても済む。２）上記１）と似ていますが、複数のスレッド（またはタスクとかウィンドウとか）を使用　　するプログラムにおいて、スレッド間（またはウィンドウ間）のメッセージのやり取り　　にキューを使用する。　　．．．など私も参考までに、スタック及びキューを使用した簡単なサンプルプログラムを組んでみたので下記に載せてみます。・C言語のコンソールプログラムです。（当方は、Visual C++ 5.0で作成しました）・C++ にすればもっとスマートで単純化（クラス化するとか、動的でサイズ可変なバッファ　の確保など）できると思いますが、私の力量ではこの程度しかできませんでした。(^^;) ※また、下記サンプルはあくまでスタック操作及び、キュー操作の具体的なコード記述例　を示しただけのものなので、実用上なんの役にも立たないことを御了承下さい。　それでも多少のヒントになれば幸いに思います。 ※また、下記サンプルにおいておかしな点等があればご指摘下されば有り難く思います。 ■スタック＆キューを使用したサンプルプログラム /* * tsq.c : スタック＆キューのテストプログラム */ #include #include /* Define Const */ #define STACK_NUM 20 //スタックデータの最大登録数 #define QUEUE_NUM 20 //キューデータの最大登録数 /* typedef */ typedef struct { //スタック構造体の型定義 int nPos; //スタック内の現在データ位置 int nData[STACK_NUM]; //スタックの登録データ } T_STACK; typedef struct { //キュー構造体の型定義 int nNum; //キュー内のデータ登録数 int nWtPos; //キュー内のデータ書込み位置 int nRdPos; //キュー内のデータ読込み位置 int nData[QUEUE_NUM]; //キューの登録データ } T_QUEUE; /* Global data */ T_STACK va_tStack; //スタックバッファ(実体) T_QUEUE va_tQueue; //キューバッファ(実体) /* Define Function */ int InitStack( T_STACK *pStack ); int PushStack( int *pData, T_STACK *pStack ); int PopStack( int *pData, T_STACK *pStack ); int InitQueue( T_QUEUE *pQueue ); int PutQueue( int *pData, T_QUEUE *pQueue ); int GetQueue( int *pData, T_QUEUE *pQueue ); /* * main */ int main(void) { int result; int nCnt; int nData1, nData2; /* スタックバッファとキューバッファの初期化 */ result = InitStack( &va_tStack ); result = InitQueue( &va_tQueue ); /*== スタックのデータ処理 ==*/ /* スタックへデータを登録して表示 */ /* ※関数の動作チェックのため、データが登録できなくなるまで[Push]している */ printf("Stack Data[Push]: "); for(nCnt=0; nCnt<(STACK_NUM+2); nCnt++){ nData1 = (nCnt + 1); result = PushStack(&nData1, &va_tStack); if(result != 0) break; printf("% 3d%s", nData1, ((((nCnt+1)%10)&&((nCnt+1)nPos = STACK_NUM; return 0; } /* * PushStack : スタックへのデータ登録 */ int PushStack( int *pData, T_STACK *pStack ) { if ( pStack->nPos <= 0 ) return -1; pStack->nData[--(pStack->nPos)] = *pData; return 0; } /* * PopStack : スタックからデータ取得 */ int PopStack( int *pData, T_STACK *pStack ) { if ( pStack->nPos >= STACK_NUM ) return -1; *pData = pStack->nData[(pStack->nPos)++]; return 0; } /* * InitQueue : キューの初期化 */ int InitQueue( T_QUEUE *pQueue ) { memset( pQueue, 0, sizeof(T_QUEUE) ); pQueue->nNum = 0; pQueue->nWtPos = 0; pQueue->nRdPos = 0; return 0; } /* * PutQueue : キューへのデータ登録 */ int PutQueue( int *pData, T_QUEUE *pQueue ) { if( pQueue->nNum >= QUEUE_NUM ) return -1; pQueue->nData[pQueue->nWtPos] = *pData; pQueue->nWtPos = ((pQueue->nWtPos + 1) % QUEUE_NUM); if( pQueue->nNum < QUEUE_NUM ) pQueue->nNum++; return 0; } /* * GetQueue : キューからデータ取得 */ int GetQueue( int *pData, T_QUEUE *pQueue ) { if( pQueue->nNum <= 0 ) return -1; *pData = pQueue->nData[pQueue->nRdPos]; pQueue->nRdPos = ((pQueue->nRdPos + 1) % QUEUE_NUM); if( pQueue->nNum > 0 ) pQueue->nNum--; return 0; } ■実行結果 Stack Data[Push]: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 Stack Num [Push]: 20 Stack Data[Pop.]: 20, 19, 18, 17, 16, 15, 14, 13, 12, 11 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 Stack Num [Pop.]: 20 Queue Data[Put.]: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 Queue Num [Put.]: 20 Queue Data[Get.]: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 Queue Num [Get.]: 20

hidebun · Answer

C言語の文法に、stackとかqueueみたいなものはないですね。
C++なら、標準ライブラリにstackやqueueはありますけど。

hidebun · Answer

>スタックを使う、とありますが、これは概念なのでしょうか？

あ、そうです。
原理が last-in-first-out (LIFO) であれば、それはスタック。
原理が first in first outであれば、それはキューです。
中に何を入れるかは、あなた次第。

Interest · Answer

キュー（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)を使用してデータのやり取りを行います。

hidebun · Answer

応用ですか。あくまで一例ですが…。
たとえば、ソフトを使っていて、
「あ、操作間違えた。元の状態に戻そう。」なんてこと、ありませんか？
操作をしたら、その都度、ソフトの内部状態をスタックにpushしておき、
ユーザーが「元に戻す」を押したら、スタックからpopして、１つ前の状態に戻す、なんてことをするのに使えます。

プリンターなんかは、キューを使ってるんじゃないかな。
プリンターが、プリントする速度はコンピュータのデータ転送速度に比べれば、
ずいぶん遅いですが、コンピュータがデータ送信をして印字が終わるのを待っていたら、
まったく仕事できません。というわけで、プリンターは、
コンピュータからデータが送られてきたら、データを一旦キューに
溜め、「印字を承りました」といって、処理をコンピュータに
返します。その後、プリンターは、キューからデータを取り出して印字を続けます。

まあ、感覚的にはこんな感じでしょうか。

annyG · Answer

簡単な話で、
「スタックやキューを使わないと面倒なとき」に「スタックやキューは
便利」です。

　例えば、ファイルから読み込んだ文字列をいったんため込んでおき、
先頭行から処理をするような場合。
　各行の内容を配列に格納すると、ループカウンタが必要になります。

　ですが、キューに保存しておけば、キューの先頭から1行ずつ
取り出して処理をしていけばいいので、ループカウンタとか、
今配列のどこを指しているのかなどは一切考えなくてもよいので
気楽です。
　スタックもキューも、別にそれを使わなければ処理ができない
わけではないので、使いたいと思わない人は使わなければいいだけの
話です。私はスタックやキューが好きですから使いますが、使わない、
使ったことがないという人はプロでも多いと思います。

asuncion · Answer

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

Tacosan · Answer

C で関数を呼び出したときの情報は (言語使用には書いてないけど実質的に) スタックで管理されます. だから, プログラム上で意識することはないとしても事実上常にスタックのお世話になっているということができます.
キューは.... ウィンドウシステムにおけるユーザの操作はいったんキューに入り, そこからしかるべきプログラムに送られるのが普通です. このようにして, (基本的に) ユーザが操作した順番に処理が行われることを保証しています.

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

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

すみません。

こんにちは。

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

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

この回答への補足

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

この回答への補足

応用ですか。

簡単な話で、

この回答への補足

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

この回答への補足

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

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング