Subsections

2 スタックとキュー

2.1 スタック

2.1.1 スタックのイメージ

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

2.1.2 スタックの実装

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

スタックのために必要な記憶領域が確保されたならば,それを操作しなくてはならない. スタックに必要な操作は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: キュー
\includegraphics[keepaspectratio,scale=0.9]{figure/queue.eps}

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

これを防ぐために,図3のようなリングバッファと言うものが考えられた.
図 3: リングバッファー
\includegraphics[keepaspectratio,scale=1.0]{figure/ring_buffer.eps}

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
著者: 山本昌志
Yamamoto Masashi
2006-02-27


no counter