C言語の基礎 - キューとスタック

配列を簡易的なキューとして使用する

C言語で、キュー(queue)を実装するには様々な方法があるが、ここでは、配列を簡易的なキューとして扱えるようにする。

キューの構造

キューのデータ構造をそのまま配列で実装しようとすると、膨大なサイズの配列が必要になる。 そこで、リングバッファと呼ばれる手法で実装する。

リングバッファとは、配列を(配列の)末尾と先頭がつながっている環状の循環構造のことである。(下図) キューに格納されたデータを管理するために、以下の2つの変数を使用する。

• head : キューの先頭要素を指し示す変数
• tail : キューの末尾要素を指し示す変数

図. リングバッファのイメージ図

キューには、エンキュー(enqueue)操作とデキュー(dequeue)操作の2種類の動作が存在する。
これらの動作を行う関数を作成することで配列を簡易的なキューとして使用可能にする。

エンキュー操作の実装

エンキュー操作は、以下の2つの手順が必要となる。

• キューにデータを追加する
• tailをインクリメントする

図. エンキュー操作のイメージ図

データを追加する場合、tailをそのまま配列の添え字にするのではなく、tailと配列の最大要素数の余剰を計算して、添え字にするのがポイントである。
また、実用上、配列の最大要素数を超えるデータがエンキューされたときのことを考えて，場合分けを行う必要がある。

以下に、エンキュー操作を行う関数の実装例を示す。
headとtailは引数として受け取り、ポインタ渡しで返すようにしている。(値が更新されるのは、tailのみである)

<syntaxhighlight lang="c">
/* 配列にエンキューする                     */
/* @param[in,out] queue 配列                */
/* @param[in] data データ                    */
/* @param[in,out] head キューの先頭要素      */
/* @param[in,out] tail キューの末尾要素      */
/* @param[in] n 配列の要素数                 */
/* @retval >=1 配列に格納されている要素の数 */
/* @retval 0 配列へのエンキューに失敗       */
int ArrayEnqueue(int *queue, int data, int *head, int *tail, size_t n)
{
   if (*head % n != (*tail + 1) % n)
   {
      queue[(*tail)++ % n] = data;
      return *tail - *head;
   }
   else
   {
      return 0;
   }
}
</source>

デキュー操作の実装

デキュー操作は、以下の2つの手順が必要になる。

• キューからデータを取り出す
• head をインクリメントする

図. デキュー操作のイメージ図

エンキュー操作と同じように、tailと配列の最大要素数の余剰を計算して、添え字にするのがポイントである。
headとtailは引数として受け取り、ポインタ渡しで返すようにしている。(値が更新されるのは、headのみである)

<syntaxhighlight lang="c">
/* 配列からデキューする                 */
/* @param[in,out] queue 配列            */
/* @param[in,out] head キューの先頭要素 */
/* @param[in,out] tail キューの末尾要素 */
/* @param[in] n 配列の要素数            */
/* @return デキューしたデータ           */
int ArrayDequeue(int *queue, int *head, int *tail, size_t n)
{
   if (*head != *tail)
   {
      return queue[(*head)++ % n];
   }
   else
   {
      return 0;
   }
}
</source>

上記で例に挙げた関数を使用して、配列を簡易的なキューとして使用する例を以下に示す。

<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>

#define N 8

int ArrayEnqueue(int *queue, int data, int *head, int *tail, size_t n);
int ArrayDequeue(int *queue, int *head, int *tail, size_t n);

int main(void)
{
   int queue[N] = {0};
   int head = 0,
       tail = 0;
   int data = 0;

   /* 配列にエンキューする */
   ArrayEnqueue(queue, 10, &head, &tail, N);
   printf("Enqueue: %d\n", 10);

   ArrayEnqueue(queue, 20, &head, &tail, N);
   printf("Enqueue: %d\n", 20);

   ArrayEnqueue(queue, 30, &head, &tail, N);
   printf("Enqueue: %d\n", 30);

   ArrayEnqueue(queue, 40, &head, &tail, N);
   printf("Enqueue: %d\n", 40);

   /* 配列からデキューする */
   while ( tail - head )
   {
      data = ArrayDequeue(queue, &head, &tail, N);
      printf("Dequeue: %d\n", data);
   }

   return EXIT_SUCCESS;
}

/* 配列にエンキューする                     */
/* @param[in,out] queue 配列                */
/* @param[in] data データ                   */
/* @param[in,out] head キューの先頭要素     */
/* @param[in,out] tail キューの末尾要素     */
/* @param[in] n 配列の要素数                */
/* @retval >=1 配列に格納されている要素の数 */
/* @retval 0 配列へのエンキューに失敗       */
int ArrayEnqueue(int *queue, int data, int *head, int *tail, size_t n)
{
   if (*head % n != (*tail + 1) % n)
   {
      queue[(*tail)++ % n] = data;

      return *tail - *head;
   }
   else
   {
      return 0;
   }
}

/* 配列からデキューする                 */
/* @param[in,out] queue 配列            */
/* @param[in,out] head キューの先頭要素 */
/* @param[in,out] tail キューの末尾要素 */
/* @param[in] n 配列の要素数            */
/* @return デキューしたデータ           */
int ArrayDequeue(int *queue, int *head, int *tail, size_t n)
{
   if (*head != *tail)
   {
      return queue[(*head)++ % n];
   }
   else
   {
      return 0;
   }
}
</source>

配列を簡易的なスタックとして使用する

C言語で、スタック(stack)を実装するには様々な方法があるが、ここでは、配列を簡易的なスタックとして扱えるようにする。

スタックには、PUSH操作とPOP操作の2種類の動作が存在する。
これらの動作を行う関数を作成すれば、配列を簡易的なスタックとして使用することができる。

PUSH操作の実装

PUSH操作は、以下の2つの手順が必要になる。

• スタックにデータを積む
• スタックポインタをインクリメントする

図. PUSH操作のイメージ図

また、実用上、配列の最大要素数を超えるデータがPUSHされた場合のことを考えて、場合分けをする必要がある。
以下に、PUSH操作を行う関数の実装例を示す。
スタックポインタspは、次の値を格納する位置情報を保持する必要があるため、引数として受け取り、ポインタ渡しで返している。

<syntaxhighlight lang="c">
/* 配列にプッシュする                       */
/* @param[in,out] stack 配列                */
/* @param[in] data 配列にプッシュする値     */
/* @param[in,out] sp スタックポインタ       */
/* @param[in] n 配列の最大要素数            */
/* @retval >=1 配列に格納されている要素の数 */
/* @retval 0 配列にプッシュに失敗           */
int ArrayPush(int *stack, int data, int *sp, size_t n)
{
   if ( *sp < n )
   {
      stack[(*sp)++] = data;

      return *sp;
   }
   else
   { /* 配列の要素数を超えるデータが PUSH されたとき */
      return 0;
   }
}
</source>

POP操作の実装

POP操作は、以下の2つの手順が必要になる。

• スタックポインタをデクリメントする
• スタックからデータを取り出す

図. POP操作のイメージ図

実際にはデータを取り出す(スタック上からデータを消去する)わけではなく、スタックポインタをずらすことにより、
PUSH操作が行われた時に上書き可能にするのがポイントである。
以下の例では、POP操作を行う関数の実装例を示す。

<syntaxhighlight lang="c">
/* 配列からポップする                 */
/* @param[in] stack 配列              */
/* @param[in,out] sp スタックポインタ */
/* @return ポップした値               */
int ArrayPop(int *stack, int *sp)
{
   if ( *sp > 0 )
   {
      return stack[--(*sp)];
   }
   else
   {
      return 0;
   }
}
</source>

上記で例に挙げた関数を使用して、配列を簡易的なスタックとして使用する例を以下に示す。

<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>

#define N 8

int ArrayPush(int *stack, int data, int *sp, size_t n);
int ArrayPop(int *stack, int *sp);

int main(void)
{
   int data = 0;
   int stack[N] = {0};  /* 配列 (スタック) */
   int sp = 0;          /* スタックポインタ */

   /* 配列にプッシュする */
   ArrayPush(stack, 10, &sp, N);
   printf("Push: %d\n", 10);

   ArrayPush(stack, 20, &sp, N);
   printf("Push: %d\n", 20);

   ArrayPush(stack, 30, &sp, N);
   printf("Push: %d\n", 30);

   ArrayPush(stack, 40, &sp, N);
   printf("Push: %d\n", 40);

   /* 配列からポップする */
   while ( sp )
   {
      data = ArrayPop(stack, &sp);
      printf("Pop: %d\n", data);
   }

   return EXIT_SUCCESS;
}

/* 配列にプッシュする                       */
/* @param[in,out] stack 配列                */
/* @param[in] data 配列にプッシュする値     */
/* @param[in,out] sp スタックポインタ       */
/* @param[in] n 配列の最大要素数            */
/* @retval >=1 配列に格納されている要素の数 */
/* @retval 0 配列にプッシュに失敗           */
int ArrayPush(int *stack, int data, int *sp, size_t n)
{
   if ( *sp < n )
   {
      stack[(*sp)++] = data;

      return *sp;
   }
   else
   {
      return 0;
   }
}

/* 配列からポップする                 */
/* @param[in] stack 配列              */
/* @param[in,out] sp スタックポインタ */
/* @return ポップした値               */
int ArrayPop(int *stack, int *sp)
{
   if ( *sp > 0 )
   {
      return stack[--(*sp)];
   }
   else
   {
      return 0;
   }
}
</source>