C言語の基礎 - キューとスタック
配列を簡易的なキューとして使用する
C言語で、キュー(queue)を実装するには様々な方法があるが、ここでは、配列を簡易的なキューとして扱えるようにする。
キューの構造
キューのデータ構造をそのまま配列で実装しようとすると、膨大なサイズの配列が必要になる。 そこで、リングバッファと呼ばれる手法で実装する。
リングバッファとは、配列を(配列の)末尾と先頭がつながっている環状の循環構造のことである。(下図)
キューに格納されたデータを管理するために、以下の2つの変数を使用する。
- head : キューの先頭要素を指し示す変数
- tail : キューの末尾要素を指し示す変数
キューには、エンキュー(enqueue)操作とデキュー(dequeue)操作の2種類の動作が存在する。
これらの動作を行う関数を作成することで配列を簡易的なキューとして使用可能にする。
エンキュー操作の実装
エンキュー操作は、以下の2つの手順が必要となる。
- キューにデータを追加する
- tailをインクリメントする
データを追加する場合、tailをそのまま配列の添え字にするのではなく、tailと配列の最大要素数の余剰を計算して、添え字にするのがポイントである。
また、実用上、配列の最大要素数を超えるデータがエンキューされたときのことを考えて，場合分けを行う必要がある。
以下に、エンキュー操作を行う関数の実装例を示す。
headとtailは引数として受け取り、ポインタ渡しで返すようにしている。(値が更新されるのは、tailのみである)
/* 配列にエンキューする */
/* @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;
}
}
デキュー操作の実装
デキュー操作は、以下の2つの手順が必要になる。
- キューからデータを取り出す
- head をインクリメントする
エンキュー操作と同じように、tailと配列の最大要素数の余剰を計算して、添え字にするのがポイントである。
headとtailは引数として受け取り、ポインタ渡しで返すようにしている。(値が更新されるのは、headのみである)
/* 配列からデキューする */
/* @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;
}
}
上記で例に挙げた関数を使用して、配列を簡易的なキューとして使用する例を以下に示す。
#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;
}
}
配列を簡易的なスタックとして使用する
C言語で、スタック(stack)を実装するには様々な方法があるが、ここでは、配列を簡易的なスタックとして扱えるようにする。
スタックには、PUSH操作とPOP操作の2種類の動作が存在する。
これらの動作を行う関数を作成すれば、配列を簡易的なスタックとして使用することができる。
PUSH操作の実装
PUSH操作は、以下の2つの手順が必要になる。
- スタックにデータを積む
- スタックポインタをインクリメントする
また、実用上、配列の最大要素数を超えるデータがPUSHされた場合のことを考えて、場合分けをする必要がある。
以下に、PUSH操作を行う関数の実装例を示す。
スタックポインタspは、次の値を格納する位置情報を保持する必要があるため、引数として受け取り、ポインタ渡しで返している。
/* 配列にプッシュする */
/* @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;
}
}
POP操作の実装
POP操作は、以下の2つの手順が必要になる。
- スタックポインタをデクリメントする
- スタックからデータを取り出す
実際にはデータを取り出す(スタック上からデータを消去する)わけではなく、スタックポインタをずらすことにより、
PUSH操作が行われた時に上書き可能にするのがポイントである。
以下の例では、POP操作を行う関数の実装例を示す。
/* 配列からポップする */
/* @param[in] stack 配列 */
/* @param[in,out] sp スタックポインタ */
/* @return ポップした値 */
int ArrayPop(int *stack, int *sp)
{
if ( *sp > 0 )
{
return stack[--(*sp)];
}
else
{
return 0;
}
}
上記で例に挙げた関数を使用して、配列を簡易的なスタックとして使用する例を以下に示す。
#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;
}
}