13,002
回編集
「C言語の基礎 - キューとスタック」の版間の差分
ナビゲーションに移動
検索に移動
編集の要約なし
(ページの作成:「== 配列を簡易的なキューとして使用する == C言語で、キュー(queue)を実装するには様々な方法があるが、ここでは、配列を簡易…」) |
編集の要約なし |
||
| 156行目: | 156行目: | ||
{ | { | ||
return queue[(*head)++ % n]; | return queue[(*head)++ % n]; | ||
} | |||
else | |||
{ | |||
return 0; | |||
} | |||
} | |||
</source> | |||
<br><br> | |||
== 配列を簡易的なスタックとして使用する == | |||
C言語で、スタック(stack)を実装するには様々な方法があるが、ここでは、配列を簡易的なスタックとして扱えるようにする。<br> | |||
<br> | |||
スタックには、PUSH操作とPOP操作の2種類の動作が存在する。<br> | |||
これらの動作を行う関数を作成すれば、配列を簡易的なスタックとして使用することができる。<br> | |||
<br> | |||
===== PUSH操作の実装 ===== | |||
PUSH操作は、以下の2つの手順が必要になる。<br> | |||
* スタックにデータを積む | |||
* スタックポインタをインクリメントする | |||
<br> | |||
[[ファイル:C Queue Stack 4.jpg|フレームなし|中央]] | |||
<center>'''図. PUSH操作のイメージ図'''</center> | |||
<br> | |||
また、実用上、配列の最大要素数を超えるデータがPUSHされた場合のことを考えて、場合分けをする必要がある。<br> | |||
以下に、PUSH操作を行う関数の実装例を示す。<br> | |||
スタックポインタspは、次の値を格納する位置情報を保持する必要があるため、引数として受け取り、ポインタ渡しで返している。<br> | |||
<source 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> | |||
<br> | |||
===== POP操作の実装 ===== | |||
POP操作は、以下の2つの手順が必要になる。<br> | |||
* スタックポインタをデクリメントする | |||
* スタックからデータを取り出す | |||
<br> | |||
[[ファイル:C Queue Stack 5.jpg|フレームなし|中央]] | |||
<center>'''図. POP操作のイメージ図'''</center> | |||
<br> | |||
実際にはデータを取り出す(スタック上からデータを消去する)わけではなく、スタックポインタをずらすことにより、<br> | |||
PUSH操作が行われた時に上書き可能にするのがポイントである。<br> | |||
以下の例では、POP操作を行う関数の実装例を示す。<br> | |||
<source 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> | |||
<br> | |||
上記で例に挙げた関数を使用して、配列を簡易的なスタックとして使用する例を以下に示す。<br> | |||
<source 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 | else | ||