2 スタックとキュー

2.1 スタック

2.1.1 スタックのイメージ

図1のようなデータ構造である．データ構造であるから，データを蓄える ことと，それを取り出すことができる．スタックの特徴は，最後に入れたデータが一番最 初に取り出されることにある．取り出されるデータは，格納されている最新のデータで， 最後に入れられたものが最初に取り出されることから，LIFO(last in first out, 後入れ 先出し)と呼ばれる．スタックの途中のデータを取り出すことは許されない．スタックに データを積むことをプッシュ(push)と，スタックからデータを取り出すことをポップ (pup)と呼ぶ．

図 1: スタック

2.1.2 スタックの実装

スタックを実装する関数をリスト1に示す．これは，教科書のList 4-1(p.100)のプログラムである(転載について)．スタックを実装するために必要な記憶領域は，スタック そのものの記憶領域とスタックの頂上を表す記憶領域である．スタックのための記憶領域 として配列stack[]を使っている．また，スタックの頂上を表すために，変数 stack_topを使っている²．

スタックのために必要な記憶領域が確保されたならば，それを操作しなくてはならない． スタックに必要な操作は2つで，データを積む(push)ことと，データを取り出す(pop)こと である．リスト1では，次の2つの関数でそれを行っている．

void stack_push(double val)

スタックへデータvalをプッシュする関 数である．データを積み重ねたならば，スタックの頂上を表す変数 stack_topを1加算している．スタックがいっぱいで，さらにデータを プッシュしようとするとプログラムは終了するようになっている．

double stack_pop(void)

スタックからデータを取り出す関数で，戻り値が取り 出されたデータである．データを取り出したならば，スタックの頂上を表す 変数stack_topを1減算している．スタックが空の状態でデータをポッ プしようとするとプログラムは終了するようになっている．

リスト1 スタックの 実装(転載について)

   1 #define STACK_MAX 10
   2 
   3 /* ※この例では，double型のデータを格納するスタックを作成 */
   4 double stack[STACK_MAX];
   5 /* スタック頂上の位置（最下部からのオフセット） */
   6 int stack_top=0;
   7 
   8 /* スタックへpush */
   9 void stack_push(double val)
  10 {
  11     if(stack_top==STACK_MAX)
  12     {
  13         /* スタックが満杯になっている */
  14         printf("エラー:スタックが満杯です(Stack overflow)\n");
  15         exit(EXIT_FAILURE);
  16     }
  17     else
  18     {
  19         /* 渡された値をスタックに積む */
  20         stack[stack_top]=val;
  21         ++stack_top;
  22     }
  23 }
  24 
  25 /* スタックからデータをpop */
  26 double stack_pop(void)
  27 {
  28     if(stack_top==0)
  29     {
  30         /* スタックには何もない */
  31         printf("エラー:スタックが空なのにpopが呼ばれました"
  32                                         "(Stack underflow)\n");
  33         exit(EXIT_FAILURE);
  34         return 0;
  35     }
  36     else
  37     {
  38         /* いちばん上の値を返す */
  39         --stack_top;
  40         return stack[stack_top];
  41     }
  42 }

2.2 キュー

2.2.1 キューのイメージ

待ち行列と呼ばれるキュー(queue)と呼ばれるデータ構造がある．これは，queueとは窓口に並ぶ順 番待ちの行列の意味で，図2のような構造である．スタックではデータの 挿入と取り出しが列の一方からのみであったの対して，キューは列の両端から行う．一方 がデータの追加で一方がデータの取り出しとして使われる．キューでは，最初に入れたデー タが一番最初に取り出されることにある．取り出されるデータは格納されている最古のデー タで，最初に入れられたものが最初に取り出されることから，FIFO(first in first out, 先入れ先出し)と呼ばれる．スタック同様，スタックの途中のデータを取り出すことは許 されない．

図 2: キュー

キューはスタックに比べて少しばかり，構造が複雑になっている．実際，それを直線的な イメージのメモリーにデータを追加しようとすると，以下のような問題が生じる．

• FIFOを続けると，いずれはメモリーの端に到達して，データの追加が出来なくな る．
• データを追加したり取り出したりする毎に，データの列を移動させることも考え られる．こうすると計算量が増加して不経済である．

これを防ぐために，図3のようなリングバッファと言うものが考えられた．

図 3: リングバッファー

2.2.2 キューの実装

キューを実装する関数をリスト2に示す．これは，教科書の List 4-4(p.120-121)と同じである(転載について)．

このプログラムでは，配列queue[]を使ってキューを実現している．配列 queue[]とキューの先頭を表す変数queue_firstと末尾を表す queue_lastはグローバル変数と宣言されているので，以下のキューを操作する関数 で直にアクセスすることができる．

キューを実装するための記憶領域が確保されたならば，それを操作しなくてはならない． キューの操作は2つで，データを追加することと，データを取り出すこと である．リスト2では，次の2つの関数でそれを行っている．

void enqueue(int val)

キューへデータvalを追加する関 数である．データを追加したならば，キューの末尾を表す変数 queue_lastを1移動(加算)している．キューがいっぱいで，さらにデータを 追加しようとするとプログラムはメッセージを出すようになっている．

int dequeue(void)

キューからデータを取り出す関数で，戻り値が取り出し たデータである．データを 取り出したならば，キューの先頭を表す変数 queue_firstを1移動(加算)している．キューが空の状態でデータを 取り出そうとするとプログラムはQUEUE_EMPTYを返すようになっている．

リスト2 キューの実 装(転載について)

   1 #define QUEUE_MAX 5+1   /* キューのサイズ+1 */
   2 #define QUEUE_EMPTY -1
   3 
   4 /* 配列によるキュー構造 */
   5 int queue[QUEUE_MAX];
   6 /* キューの先頭位置（配列先頭からのオフセット） */
   7 int queue_first=0;
   8 /* キューの末尾位置（配列先頭からのオフセット） */
   9 int queue_last=0;
  10 
  11 /* キューにデータを追加する */
  12 void enqueue(int val)
  13 {
  14     /* lastの次がfirstならば */
  15     if((queue_last+1)%QUEUE_MAX ==queue_first)
  16     {
  17         /* 現在配列の中身は，すべてキューの要素で埋まっている */
  18         printf("ジョブが満杯です\n");
  19     }
  20     else
  21     {
  22         /* キューに新しい値を入れる */
  23         queue[queue_last]=val;
  24         /* queue_lastを1つ後ろにずらす。
  25            もし，いちばん後ろの場合は，先頭にもってくる */
  26         queue_last=(queue_last+1)%QUEUE_MAX;
  27     }
  28 }
  29 
  30 /* キューからデータを取り出す */
  31 int dequeue(void)
  32 {
  33     int ret;
  34 
  35     if(queue_first==queue_last)
  36     {
  37         /* 現在キューは1つもない */
  38         return QUEUE_EMPTY;
  39     }
  40     else
  41     {
  42         /* いちばん先頭のキューを返す準備 */
  43         ret=queue[queue_first];
  44         /* キューの先頭を次に移動する */
  45         queue_first=(queue_first+1)%QUEUE_MAX;
  46         return ret;
  47     }
  48 }

2.3 練習問題

[問1]

スタックと呼ばれるデータ構造を説明せよ．

[問2]

LIFOとは何か?

[問3]

スタックについて，以下の操作を定義する．

PUSH($n$ )	:スタックにデータ$n$ をプッシュする．戻り値は無し．
POP()	:スタックからデータをポップする．戻り値は，取り出した値．

空のスタックに対して，以下の操作を行ったとき，データ構造の様子を図で示せ．

PUSH(3) $\rightarrow$ PUSH(5) $\rightarrow$ POP() $\rightarrow$ PUSH(2) $\rightarrow$ PUSH(1) $\rightarrow$ POP() $\rightarrow$ POP() $\rightarrow$ PUSH(1) $\rightarrow$ POP() $\rightarrow$ PUSH(7)

[問4]

前問のPOP()で取り出される値を示せ．

[問5]

キューと呼ばれるデータ構造を説明せよ．

[問6]

FIFOとは何か?

[問7]

キューにリングバッファーが使われる理由を説明せよ．

[問8]

キューについて，以下の操作を定義する．

ENQ($n$ )	:キューにデータ$n$ を追加する．戻り値はなし．
DEQ()	:キューからデータを取り出す．戻り値は取り出した値．

空のスタックやキューに対して，以下の操作を行ったとき，データ構造の 様子を図で示せ．

ENQ(6) $\rightarrow$ ENQ(2) $\rightarrow$ DEQ() $\rightarrow$ ENQ(7) $\rightarrow$ DEQ() $\rightarrow$ ENQ(3) $\rightarrow$ ENQ(1) $\rightarrow$ ENQ(2) $\rightarrow$ DEQ() $\rightarrow$ DEQ()

[問9]

前問のDEQ()で取り出される値を示せ．

[転載について]
このページ中のリスト1とリスト2のプログラムは，教科書として使用している以下の書籍

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

ホームページ: Yamamoto's laboratory
著者: 山本昌志