プログラミング技法とデータ構造

スタックとキューとは

データの配列に対し，読み書きできる要素に一定のルールに従ってアクセスさせるようにプログラム内容を制限することで，機械的に分かりやすい機能を実現することもできる．スタック(stack)は，配列の末尾だけにデータを追加削除できるように制限したものである．キュー(queue)は，配列の末尾だけにデータを追加できるようにし，先頭だけからデータを取り出すことができるようにしたものである．

スタックの利用は，プログラミング言語で一般に利用されている関数呼び出しなど，特に再帰呼び出しの手法を実現するために用いられる．現代の代表的なプログラミング言語では関数呼び出しの機能を有しているため，現代のCPUはすべてスタックを実現補助するためのハードウェア機構を有している．

キューは，その名のとおり待ち行列を用いた処理を実現するためのデータ構造である．

スタックの動作

スタックにデータを登録することをプッシュ(push)，スタックからデータを取り出すことをポップ(pop)と呼ぶ．スタックはデータをプッシュした逆順に取り出すことができる．

動作例としては，スタックに「333」をプッシュする．次に「222」をプッシュする．

222

333

次にデータを一つポップすると，最後にプッシュされた「222」が取り出される．

333

そして「444」と「666」をプッシュする．

666

444

333

データを順にポップすると，プッシュされた逆順に「666」「444」「333」が取り出される．このように，データのプッシュとポップは途中不揃いの回数で行われるため，いろいろと複雑な動きをすることもある．

スタックの実現

スタックは，配列データと最後のデータが保存されている位置を示すスタックポインタにより管理される．

#define SIZE 100
typedef struct {
  int data[SIZE];
  int sp;
} STACK;

STACK stack;
stack.sp=0; //初期化

スタックポインタはポインタ変数として実現されることも，配列に対する添字を覚えておくための整数型であることもある．

push動作とpop動作は次のようになる．

void push(int val)
{
  if(stack.sp>=SIZE)
    エラー処理
  stack.data[stack.sp++] = val; //valをpush
}

int pop(void)
{
  if(stack.sp!=0)
    return stack.data[--stack.sp];
  else
    エラー処理
}

再帰呼び出し

実はC言語の関数呼び出し機能は，機械語に翻訳されるときにCPUのスタック機能を利用して実現されている．ここでは機械語の詳細については触れずに概念的な説明を行う．

例えば，次のように関数funcAの中で別の関数を呼び出すことを考える．

void funcA(void)
{
   funcB();//(1)
   funcC();//(3)
}

void funcB(void)
{
   funcD();//(2)
}

(1)を実行すると，CPUのスタックには「funcA」と「funcB」が積まれる．

funcB

funcA

次にfuncBの中でさらに(2)でfuncDが呼び出されるため，「funcC」がつまれる．

funcD

funcB

funcA

そしてfuncDが終了すると，funcDがpopされてfuncBに戻り，それからfuncBも終了するとfuncAに戻る．そして続きとして(3)でfuncCが呼び出される．

funcC

funcA

このように関数呼び出しによる動作は，論理的にスタック動作と同一である．

特に，次のように関数の中から自分自身を呼び出す再帰呼び出しを実現する際に有効である．次の関数は，再帰によりフィボナッチ数を計算する関数である．

int Fibo(int n)
{
    if(n==1 || n==2)
      return 1;
    else
      return Fibo(n-1)+Fibo(n-2);
             /* (a) */ /* (b) */
} 

例えば，Fibo(4)を計算するとすると，これもスタックを使って説明できる．先ほどとは異なり関数名Fiboは共通なので引数nの値をスタックに積むような表記とする．まず，最初のFibo(4)を計算するためにn=4がつまれ，その中で(a)の方で子にあたるFibo(3)が呼び出される．この時点ではスタックにn=3が積まれる．

n=3

n=4

次にFibo(3)を計算するために，その中で(1)のFibo(2)が呼び出される．Fibo(2)は，そのままreturn 1される．

n=2

n=3

n=4

スタックのn=2がpopされ，n=3のFibo(3)に戻り，その中の(b)にあたるFibo(1)が呼び出される．

n=1

n=3

n=4

Fibo(1)もすぐにreturn 1されて終了する．これでFibo(3)は1+1で2になって終了する．Fibo(3)すなわちFibo(4)の(a)が終了したので，今度は(b)のFibo(2)が計算される．

n=2

n=4

Fibo(2)はすぐにreturn 1されるので終了し，Fibo(4)は，2+1となり3で終了する．

キュー

キューの実現

キューは，スタックと異なり，最初に入れたデータから順に取り出していく．このため，配列を使用して実現するとデータを配列先頭から埋めていき，先頭から順に取り出していくことになる．読み出し位置と書き込み位置が，それぞれ別に存在するためポインタも二つ必要となる．

また，配列先頭から順にデータを使用していくため，使用が進むと配列末尾へ書き込み・読み込みポインタ共に一方向に配列後方へ移動していき，そのうち末尾に達することになる．このため，末尾に達したところで先頭に戻るような，リングバッファとして実現することが多い．

リングバッファの実現として，データの書き込み意味を示すtailと，読み出し位置を示すheadを用意する．初期状態では両者とも配列先頭の0を指している．この両者の大小関係だけでは，このデータが空の初期状態と，リングバッファが全部埋まってしまった状態を区別することができないため，要素数numも設定しておく．

#define SIZE 100
typedef struct 
{
  int data[SIZE];
  int head,tail;
  int num;       //登録されている数
} QUEUE;

QUEUE q;
q.tail=q.head=q.num=0; //初期化

void enqueue(int val)
{
  if(num==SIZE)
    エラー処理
  q.data[q.tail]=val;
  q.tail=(q.tail+1)%SIZE;
  q.num++;
}

int dequeue(void)
{
  int ret;
  if(num==0)
    エラー処理
  ret=q.data[q.head]
  q.head = (q.head+1)%SIZE;
  q.num--;
  return ret;
}

再帰プログラム

ユークリッドの互除法

再帰を用いたプログラム例ととしては，C言語入門でも課題になった，最大公約数を求める計算で有名なユークリッドの互除法があげられる．

二つの整数a,b(a>bとする)の最大公約数dを求める．

• Step 1. もしb=0であればd=|a|として終了
• Step 2. aをbで割った余りをrとする
• Step 3. a=b, b=rとして、Step 1.へ

このプログラムはループを使って実現することもできるが，再帰を使用すると分かり易い．

int gcd(int a, int b)
{
  int r;
  if(b==0)
    return a;
  else
    return gcd(b,a%b);
}

ハノイの塔

有名なハノイの塔を解くプログラムも，再帰で書くと分かり易い．ハノイの塔は大きさが異なる複数の輪を，大きさ順に棒に通してある．棒は3本あり，輪がつんである棒と，残り2本の空の棒からスタートする．一度に一つの輪だけ別の棒に移動できるし，3本の棒は常に大きさ順で輪が積んでである状態を保ちつつ，初期につんである棒から，別の棒に輪を全部移動するパズルである．実際のところこの解法は，単純であり，一回やれば手順は決まっていてすぐ解ける．

ハノイの塔をプログラムで解く場合，次のように考えて再帰を使う．全部でn個の輪を移動するとすれば，それはn-1個の輪をまず隣の棒に移動する．残った一番大きな輪を目的の棒に移動する．そうすればn-1個の輪を目的の棒に移動すればよい．1個しか輪がなければ直接目的の棒に移動するだけである．

  void move(int no, int src, int dest)
  {
     if(no>1)
       move(no-1, src, 6-src-dest);  
     printf("サイズ%dを，軸%dから軸%dへ移動\n",no,src,dest); 
     if(no>1)
       move(no-1, 6-src-dest, dest);
  }