キューとスタック

Copyright(C) 14May2007 coskx TNCT

複数のデータを一時的に保存する方法には２つの方法がある。１つは，先に格納したデータから先に取り出す（ＦＩＦＯ　First In First Out）方法で，その保存場所はキューと呼ばれている。これは，通信データの一時保存や，印刷データの一時保存の方法である。もう１つは後から入れたデータから先に取り出す（ＦＩＬＯ　First In Last Out）方法で，その保存場所はスタックと呼ばれる。これは，アセンブリプログラムなどでサブルーチンコールの際の戻りアドレスを覚えておく場合や，ある種の電卓（逆ポーランド記述）などに用いられている。

	１．キュー　（ＦＩＦＯ）

キュー構造を実現する時にはリングバッファという手法が用いられる。配列の最後を配列の先頭にくっつけて，大きさは有限だが，無限に続く配列のように見せかける。たとえば次の例は部屋が８個しかないが，9個目のデータをしまう頃には部屋1があいているはずなので（あいていなかったら困るが，その心配は後にすることにする）部屋1にしまい，その次は部屋2にしまい，・・・を繰り返す。

次の模式図は，データを５つ入力した後，５つ取り出し，再び５つ入力して，また５つ取り出すところを見せている。
putpointerは次にデータを格納する場所を指しており，getpointerは次にデータを取り出す場所を指している。

初期状態 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　 　 　 　 　 　 　 　 putpointer 　↑ 　 　 　 　 　 　 　 getpointer 　↑

データ31を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　 　 　 　 　 　 　 putpointer 　 　↑ 　 　 　 　 　 　 getpointer 　↑

データ32を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　 　 　 　 　 　 putpointer 　 　 　↑ 　 　 　 　 　 getpointer 　↑

データ33を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　 　 　 　 　 putpointer 　 　 　 　↑ 　 　 　 　 getpointer 　↑

データ34を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　 　 　 　 putpointer 　 　 　 　 　↑ 　 　 　 getpointer 　↑

データ35を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 putpointer 　 　 　 　 　 　↑ 　 　 getpointer 　↑

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 putpointer 　 　 　 　 　 　↑ 　 　 getpointer 　 　↑ 　 　 　 　 　 　 31が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 putpointer 　 　 　 　 　 　↑ 　 　 getpointer 　 　 　↑ 　 　 　 　 　 32が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 putpointer 　 　 　 　 　 　↑ 　 　 getpointer 　 　 　 　↑ 　 　 　 　 33が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 putpointer 　 　 　 　 　 　↑ 　 　 getpointer 　 　 　 　 　↑ 　 　 　 34が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 putpointer 　 　 　 　 　 　↑ 　 　 getpointer 　 　 　 　 　 　↑ 　 　 35が取り出せた

データ36を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　36 　 　 putpointer 　 　 　 　 　 　 　↑ 　 getpointer 　 　 　 　 　 　↑

データ37を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　36 　37 　 putpointer 　 　 　 　 　 　 　 　↑ getpointer 　 　 　 　 　 　↑

データ38を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　36 　37 　38 putpointer 　↑ 　 　 　 　 　 　 　 getpointer 　 　 　 　 　 　↑ 　 　 （使用済の空き部屋が再利用されている）

データ39を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　39 　32 　33 　34 　35 　36 　37 　38 putpointer 　 　↑ 　 　 　 　 　 　 getpointer 　 　 　 　 　 　↑

データ40を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　39 　40 　33 　34 　35 　36 　37 　38 putpointer 　 　 　↑ 　 　 　 　 　 getpointer 　 　 　 　 　 　↑

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　39 　40 　33 　34 　35 　36 　37 　38 putpointer 　 　 　↑ 　 　 　 　 　 getpointer 　 　 　 　 　 　 　↑ 　 36が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　39 　40 　33 　34 　35 　36 　37 　38 putpointer 　 　 　↑ 　 　 　 　 　 getpointer 　 　 　 　 　 　 　 　↑ 37が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　39 　40 　33 　34 　35 　36 　37 　38 putpointer 　 　 　↑ 　 　 　 　 　 getpointer 　↑ 　 　 　 　 　 　 　 38が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　39 　40 　33 　34 　35 　36 　37 　38 putpointer 　 　 　↑ 　 　 　 　 　 getpointer 　 　↑ 　 　 　 　 　 　 39が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　39 　40 　33 　34 　35 　36 　37 　38 putpointer 　 　 　↑ 　 　 　 　 　 getpointer 　 　 　↑ 　 　 　 　 　 40が取り出せた

実際のプログラミングでは，
（１）データをしまう配列（グローバル変数であるが，データ格納関数とデータ取り出し関数からしか操作されない）
（２）次のデータをどこの部屋にしまうかを覚えている変数
　　　（グローバル変数であるが，データ格納関数とデータ取り出し関数からしか操作されない）
（３）次にデータを取り出すとしたらどこの部屋から取り出すのかを覚えている変数
　　　（グローバル変数であるが，データ格納関数とデータ取り出し関数からしか操作されない）
（４）データ格納関数
（５）データ取り出し関数
で実現される。

次のプログラムは，1つのキュー構造の例である。main()は動作確認のためである。
この例では。キューを構成する配列サイズが８であるため，キューに保存されるデータ個数が８を超えないようにしている。

List 1.1 キューの例

#include <stdio.h> /********************queue構造の記述のはじまり***************/ #define SIZE 8 int queue_buffer[SIZE]; /*格納のための配列*/ int queue_putpointer=0; /*次に格納する場所を示す*/ int queue_getpointer=0; /*次に取り出す場所を示す*/ void enqueue(int var) /*格納関数*/ {     queue_buffer[queue_putpointer++]=var;     if (queue_putpointer==SIZE) queue_putpointer=0; } int dequeue(void) /*取り出し関数*/ {     int var;     var=queue_buffer[queue_getpointer++];     if (queue_getpointer==SIZE) queue_getpointer=0;     return var; } /********************queue構造の記述のおわり*****************/ int main() {     enqueue(31);     enqueue(32);     enqueue(33);     enqueue(34);     enqueue(35);     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     enqueue(36);     enqueue(37);     enqueue(38);     enqueue(39);     enqueue(40);     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     return 0; }

実行結果

31 32 33 34 35 36 37 38 39 40

次の例では。キューを構成する配列サイズが８であるが，キューに保存するデータ個数が８を超えてしまった例である。これでは正しく動作していることを保障できない。

List 1.2 動作不良のキューの例

#include <stdio.h> /********************queue構造の記述のはじまり***************/ #define SIZE 8 int queue_buffer[SIZE]; /*格納のための配列*/ int queue_putpointer=0; /*次に格納する場所を示す*/ int queue_getpointer=0; /*次に取り出す場所を示す*/ void enqueue(int var) /*格納関数*/ {     queue_buffer[queue_putpointer++]=var;     if (queue_putpointer==SIZE) queue_putpointer=0; } int dequeue(void) /*取り出し関数*/ {     int var;     var=queue_buffer[queue_getpointer++];     if (queue_getpointer==SIZE) queue_getpointer=0;     return var; } /********************queue構造の記述のおわり*****************/ int main() {     enqueue(31);     enqueue(32);     enqueue(33);     enqueue(34);     enqueue(35);     enqueue(36);     enqueue(37);     enqueue(38);     enqueue(39);     enqueue(40);     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     printf("%d\n",dequeue());     return 0; }

実行結果

39 40 33 34 35 36 37 38 39 40

次のプログラムはキューサイズに対する検査を行って，保存しすぎや，取り出しすぎをチェックできるようにした例である。

List 1.3 動作チェック機能を持つキューの例

#include <stdio.h> /********************queue構造の記述のはじまり***************/ #define SIZE 8 int queue_buffer[SIZE]; /*格納のための配列*/ int queue_putpointer=0; /*次に格納する場所を示す*/ int queue_getpointer=0; /*次に取り出す場所を示す*/ void enqueue(int var,int *flag) /*格納関数 flag=0：成功,　1：失敗*/ {     int diff;     diff=queue_getpointer-queue_putpointer;     if (diff==1||diff==-(SIZE-1)) {         *flag=1;         return;     }     queue_buffer[queue_putpointer++]=var;     if (queue_putpointer==SIZE) queue_putpointer=0;     *flag=0; } int dequeue(int *flag) /*取り出し関数 flag=0：成功,　1：失敗*/ {     int var;     if (queue_getpointer-queue_putpointer==0) {         *flag=1;         return 0;     }     var=queue_buffer[queue_getpointer++];     if (queue_getpointer==SIZE) queue_getpointer=0;     *flag=0;     return var; } /********************queue構造の記述のおわり*****************/ int main() {     int flag;     int var;     enqueue(31,&flag);     if (flag) puts("over flow");     enqueue(32,&flag);     if (flag) puts("over flow");     enqueue(33,&flag);     if (flag) puts("over flow");     enqueue(34,&flag);     if (flag) puts("over flow");     enqueue(35,&flag);     if (flag) puts("over flow");     enqueue(36,&flag);     if (flag) puts("over flow");     enqueue(37,&flag);     if (flag) puts("over flow");     enqueue(38,&flag);     if (flag) puts("over flow");     enqueue(39,&flag);     if (flag) puts("over flow");     enqueue(40,&flag);     if (flag) puts("over flow");     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=dequeue(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     return 0; }

実行結果

over flow over flow over flow 31 32 33 34 35 36 37 out of data out of data out of data

ここに3つの例を示したが，場合によってはList 1.3のようにチェック機能つきのキューを使うことがあるが，List 1.1のままで，キューに用いる配列サイズに余裕を持たせて使うことも多い。

	２．スタック（FILO)

初期状態 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　 　 　 　 　 　 　 　 stackpointer 　↑

データ31を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　 　 　 　 　 　 　 stackpointer 　 　↑

データ32を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　 　 　 　 　 　 stackpointer 　 　 　↑

データ33を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　 　 　 　 　 stackpointer 　 　 　 　↑

データ34を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　 　 　 　 stackpointer 　 　 　 　 　↑

データ35を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 stackpointer 　 　 　 　 　 　↑

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 stackpointer 　 　 　 　 　↑ 　 　 　 35が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 stackpointer 　 　 　 　↑ 　 　 　 　 34が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 stackpointer 　 　 　↑ 　 　 　 　 　 33が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 stackpointer 　 　↑ 　 　 　 　 　 　 32が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　31 　32 　33 　34 　35 　 　 　 stackpointer 　↑ 　 　 　 　 　 　 　 31が取り出せた

データ36を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　32 　33 　34 　35 　 　 　 stackpointer 　 　↑

データ37を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　33 　34 　35 　 　 　 stackpointer 　 　 　↑

データ38を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　38 　34 　35 　 　 　 stackpointer 　 　 　 　↑ 　 　 　 　 （使用済の空き部屋が再利用されている）

データ39を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　38 　39 　35 　 　 　 stackpointer 　 　 　 　 　↑

データ40を格納 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　38 　39 　40 　 　 　 stackpointer 　 　 　 　 　 　↑

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　38 　39 　40 　 　 　 stackpointer 　 　 　 　 　↑ 　 　 　 40が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　38 　39 　40 　 　 　 stackpointer 　 　 　 　↑ 　 　 　 　 39が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　38 　39 　40 　 　 　 stackpointer 　 　 　↑ 　 　 　 　 　 38が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　38 　39 　40 　 　 　 stackpointer 　 　↑ 　 　 　 　 　 　 37が取り出せた

データの取り出し 部屋 部屋0 部屋1 部屋2 部屋3 部屋4 部屋5 部屋6 部屋7 データ 　36 　37 　38 　39 　40 　 　 　 stackpointer 　↑ 　 　 　 　 　 　 　 36が取り出せた

次の例はスタック領域からデータがはみ出さないようにチェック機能を持ったスタックの例である。

List 22 動作チェック機能を持つスタックの例

#include <stdio.h> /********************stack構造の記述のはじまり***************/ #define SIZE 8 int stack_buffer[SIZE]; /*格納のための配列*/ int stack_pointer=0; /*次に格納する場所を示す*/ void push(int var,int *flag) /*格納関数 flag=0：成功,　1：失敗*/ {     if (stack_pointer==SIZE) {         *flag=1;         return;     }     stack_buffer[stack_pointer++]=var;     *flag=0; } int pop(int *flag) /*取り出し関数 flag=0：成功,　1：失敗*/ {     int var;     if (stack_pointer==0) {         *flag=1;         return 0;     }     *flag=0;     return stack_buffer[--stack_pointer]; } /********************stack構造の記述のおわり*****************/ int main() {     int flag;     int var;     push(31,&flag);     if (flag) puts("over flow");     push(32,&flag);     if (flag) puts("over flow");     push(33,&flag);     if (flag) puts("over flow");     push(34,&flag);     if (flag) puts("over flow");     push(35,&flag);     if (flag) puts("over flow");     push(36,&flag);     if (flag) puts("over flow");     push(37,&flag);     if (flag) puts("over flow");     push(38,&flag);     if (flag) puts("over flow");     push(39,&flag);     if (flag) puts("over flow");     push(40,&flag);     if (flag) puts("over flow");     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     var=pop(&flag);     if (flag) puts("out of data");     else printf("%d\n",var);     return 0; }

実行結果

over flow over flow 38 37 36 35 34 33 32 31 out of data out of data