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

質問

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

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

宜しくお願いします。

回答No.10

Interest · ベストアンサー

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

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

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

そうですね。ではリクエストにお答えします。以下、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;

回答No.12

noname#144013

すみません。　#11です。

前記事 #11 に以下の訂正があります。（細かいことですが。。。）

【訂正前】
■キュー処理
１）#7さん と #10さん も書かれていますが、～～～～～

【訂正後】
■キュー処理
１）#7、#10の回答者さん も書かれていますが、～～～～～

※#7さんと#10さんは同じ方でしたね。すみませんでした。

回答No.11

noname#144013

こんにちは。

私も他の回答者さんと似たような意見になってしまいますが、コメントさせていただきます。
以下長文、失礼致します。

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

ならびに、

> では、ポイントのようにC言語で表わされる形としては存在しない、
> と考えてよいのでしょうか？
>
> それとも、スタックやキューはこういうふうに使うもの、とある
> のでしょうか？（概念だけなら無い事になりますね。）

の件ですが、確かに「スタックとキュー」は処理の「やり方・考え方」になりますので
"概念"になると思います。

しかし「やり方・考え方」なので、それを「プログラム」という形にすることは可能だと
思います。

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

どういったことに使えるかというよりは、プログラムの設計者が、これから作成すべき
プログラムを実現化する際に、ある処理において、ここは「スタック処理」または「キュ
ー処理」を使った方が妥当だと考えた場合に、その方法を用いるといったような使い方
になるのではないかと思います。
ですので、その使用用途は様々だと思います。

スタック＆キューとは別の話ですが、例えばコンソールプログラムを作成する上で画面
に文字列を出力したい場合に、printf関数を用いるのが妥当だと考える事と同様な事
ではないかと思います。（まあ、printfはその使用用途がハッキリしていますが．．．）

強いて具体例を上げるとすれば、
■スタック処理
１）アセンブリ言語でプログラミングする場合に、サブルーチンとの引数のやり取りに
　スタック領域を介して行なう。（スタックエリアへのレジスタのPush＆Popなど）
２）カードゲーム（トランプなど）をプログラム化するにあたり、場札へのカードの積み
　上げ及び場札からカードを引く操作をシミュレーションする場合。
　※場札がスタックの箱に相当し、最後に積み上げたカードからカードを引く場合。
　．．．など
■キュー処理
１）#7さん と #10さん も書かれていますが、通信プログラムにおいて、送受信データを
　　貯めておく領域としてキューバッファを使用することがあります。
　　メリットとしては、「データ編集処理」と「送信処理」及び「受信処理」を切り分けて
　　設計でき単純化できる。そのためデバッグおよびメンテナンスもし易くなる。
　　※タイミングとか処理渋滞などをあまり気にしなくても済む。
２）上記１）と似ていますが、複数のスレッド（またはタスクとかウィンドウとか）を使用
　　するプログラムにおいて、スレッド間（またはウィンドウ間）のメッセージのやり取り
　　にキューを使用する。
　　．．．など

私も参考までに、スタック及びキューを使用した簡単なサンプルプログラムを組んでみた
ので下記に載せてみます。
・C言語のコンソールプログラムです。（当方は、Visual C++ 5.0で作成しました）
・C++ にすればもっとスマートで単純化（クラス化するとか、動的でサイズ可変なバッファ
　の確保など）できると思いますが、私の力量ではこの程度しかできませんでした。(^^;)
※また、下記サンプルはあくまでスタック操作及び、キュー操作の具体的なコード記述例
　を示しただけのものなので、実用上なんの役にも立たないことを御了承下さい。
　それでも多少のヒントになれば幸いに思います。
※また、下記サンプルにおいておかしな点等があればご指摘下されば有り難く思います。

■スタック＆キューを使用したサンプルプログラム
/*
* tsq.c : スタック＆キューのテストプログラム
*/
#include <stdio.h>
#include <string.h>

/* 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]:\n");
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)<STACK_NUM))? ", ":"\n"));
}

/* スタックへ登録できたデータ個数を表示 */
printf("Stack Num [Push]: %d\n", nCnt);

/* スタックからデータを取得して表示 */
/* ※関数の動作チェックのため、データが取得できなくなるまで[Pop]している */
printf("\nStack Data[Pop.]:\n");
for(nCnt=0; nCnt<(STACK_NUM+2); nCnt++){
result = PopStack(&nData2, &va_tStack);
if(result != 0) break;
printf("% 3d%s", nData2, ((((nCnt+1)%10)&&((nCnt+1)<STACK_NUM))? ", ":"\n"));
}

/* スタックから取得できたデータ個数を表示 */
printf("Stack Num [Pop.]: %d\n", nCnt);

/*== キューのデータ処理 ==*/

/* キューへデータを登録して表示 */
/* ※関数の動作チェックのため、データが登録できなくなるまで[Put]している */
printf("\nQueue Data[Put.]:\n");
for(nCnt=0; nCnt<(QUEUE_NUM+2); nCnt++){
nData1 = (nCnt + 1);
result = PutQueue(&nData1, &va_tQueue);
if(result != 0) break;
printf("% 3d%s", nData1, ((((nCnt+1)%10)&&((nCnt+1)<QUEUE_NUM))? ", ":"\n"));
}

/* キューへ登録できたデータ個数を表示 */
printf("Queue Num [Put.]: %d\n", nCnt);

/* キューからデータを取得して表示 */
/* ※関数の動作チェックのため、データが取得できなくなるまで[Get]している */
printf("\nQueue Data[Get.]:\n");
for(nCnt=0; nCnt<(QUEUE_NUM+2); nCnt++){
result = GetQueue(&nData2, &va_tQueue);
if(result != 0) break;
printf("% 3d%s", nData2, ((((nCnt+1)%10)&&((nCnt+1)<QUEUE_NUM))? ", ":"\n"));
}

/* キューから取得できたデータ個数を表示 */
printf("Queue Num [Get.]: %d\n", nCnt);

return 0;
}

/*
* InitStack : スタックの初期化
*/
int InitStack( T_STACK *pStack )
{
memset( pStack, 0, sizeof(T_STACK) );
pStack->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

お礼

＃１０さん、＃１１さんをはじめとした多くの皆さん
ありがとうございました。

何かしらの標準関数などが用意してあるのではなく、
考え方としてそれら（スタック＆キュー）があり、
その考え方によってコーディングするものであり、
そのコードは人によって異なる、ということなのですね。
今までずっと疑問のまま放置していましたがよくわかりました。

回答No.9

hidebun

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

回答No.8

hidebun

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

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

補足

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

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

回答No.7

Interest

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

補足

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

回答No.6

hidebun

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

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

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

回答No.5

annyG

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

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

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

補足

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

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

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

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

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

回答No.4

asuncion

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

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

補足

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

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

回答No.3

Tacosan

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

補足

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

回答No.2

Tasuke22

パソコンのファイルはOSがHDD上でキューで持って
いますね。ですから、何箇所に分かれたりしても
続けて読み書きが出来ます。ちと、こじつけ？

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

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

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

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

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