（答案提出）C言語教室第23回 - スタックとキュー（スタック編）

Akio van der Meer

2023年4月30日 12:13

前回のキュー編に引き続き、今回はスタック編。
これで第23回の課題はクリア！？

課題

1. 配列を使って、スタックを書いてください。スタックを初期化する関数で配列の大きさを指定してください。

https://note.com/kazushinakamura/n/n6eab5a1b1870

配列を使って、スタックを構成する

【設計方針】

配列を用意する（初期化する関数を設定する）
stack_pointerを用意しておく。
配列の上限値(Stack_MAX)を設定しておく。
push()関数では、stack_pointerがStack_MAXに達していない場合において、引数をstackにセットし、stack_pointerをインクリメントする。
push()実行時点でstack_pointerがStack_MAXに達したら、エラー表示して実行結果をfalseとする。
pop()関数では、stack_pointerが0でない場合において、(stack_pointer - 1) が指し示す配列の要素を戻り値として返す。
pop()実行時点でstack_pointerが既にゼロを指す場合は、エラー表示して実行結果をfalseとする。

int * init_stack(int stack_size)

引数；　スタックのサイズを与える
戻り値；関数内で生成したスタック用配列を返す

bool push(int * stack, int val) ;

引数；スタック用の配列、スタックに保管する整数
戻り値；スタックが満タンでpush()できない場合は、エラー表示して実行結果をfalseとする。

bool pop(int stack, int val)

引数；スタック用の配列、スタックから取得した整数
戻り値；スタックが空でpop()できない場合は、エラー表示して実行結果をfalseとする。

ソースコード

/**********************************************************************
	lesson23s　Configure a stack with an array
		by Akio van der Meer

[変更履歴]
 (無印)  記事初投稿時のコード
 r1.0	
**********************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define Stack_MAX 10
int stack_pointer = 0;

int * init_stack(int stack_size) {
  int *arry;
	arry = (int*)malloc(sizeof(int) * stack_size);
	if (arry == NULL) exit(0);

  for (int i = 0; i < stack_size; i++) {
    arry[i] = 0;
  }
  return arry;
}

bool push(int * stack, int val) {
  if (stack_pointer < Stack_MAX) {
    stack[stack_pointer++] = val;
    return true;
  } else {
    printf("stack is FULL! (%d has not been stacked.)\n", val);
    return false;
  }
}

bool pop(int *stack, int *val) {
  *val = 0;

  if (stack_pointer > 0) {
    *val = stack[stack_pointer - 1];
    stack[stack_pointer - 1] = 0;
    stack_pointer--;
    return true;
  } else {
    printf("stack is Empty!\n");
    return false;
  }
}

void dump_stack(int * stack) {
  printf("stack dump: ");
  for (int i = 0; i < Stack_MAX; i++) {
    printf("%02d ", stack[i]);
  }
  printf("\n");
  printf("(stack_pointer = %d)\n\n", stack_pointer);
}

int main() {
  int cnt = 0;
  int rst = 0;
  int sample = 1;
  int *stack;
  stack = init_stack(Stack_MAX);

  printf("初期状態--------------\n");
  dump_stack(stack);

  printf("３回 取り出し--------------\n");
  for (cnt = 0; cnt < 3; cnt++) {
    if (pop(stack, &rst) == true) printf("popped (%d)\n", rst);
  }
  dump_stack(stack);
    printf("stack_pointer = %d\n", stack_pointer);

  printf("4回追加--------------\n");
  for (cnt = 0; cnt < 4; cnt++) {
    if (push(stack, sample) == true) printf("pushed (%d)\n", sample++);
  }
  dump_stack(stack);


  printf("4回追加--------------\n");
  for (cnt = 0; cnt < 4; cnt++) {
    if (push(stack, sample) == true) printf("pushed (%d)\n", sample++);
  }
  dump_stack(stack);


  printf("4回追加--------------\n");
  for (cnt = 0; cnt < 4; cnt++) {
    if (push(stack, sample) == true) printf("pushed (%d)\n", sample++);
  }
  dump_stack(stack);


  printf("３回 取り出し--------------\n");
  for (cnt = 0; cnt < 3; cnt++) {
    if (pop(stack, &rst) == true) printf("popped (%d)\n", rst);
  }
  dump_stack(stack);


  printf("５回追加--------------\n");
  for (cnt = 0; cnt < 5; cnt++) {
    if (push(stack, sample) == true) printf("pushed (%d)\n", sample++);
  }
  dump_stack(stack);

  printf("6回取り出し--------------\n");
  for (cnt = 0; cnt < 6; cnt++) {
    if (pop(stack, &rst) == true) printf("popped (%d)\n", rst);
  }
  dump_stack(stack);

  printf("7回追加--------------\n");
  for (cnt = 0; cnt < 7; cnt++) {
    if (push(stack, sample) == true) printf("pushed (%d)\n", sample++);
  }
  dump_stack(stack);

  printf("11回取り出し--------------\n");
  for (cnt = 0; cnt < 11; cnt++) {
    if (pop(stack, &rst) == true) printf("popped (%d)\n", rst);
  }
  dump_stack(stack);

  printf("3回追加--------------\n");
  for (cnt = 0; cnt < 3; cnt++) {
    if (push(stack, sample) == true) printf("pushed (%d)\n", sample++);
  }
  dump_stack(stack);

  printf("4回取り出し--------------\n");
  for (cnt = 0; cnt < 4; cnt++) {
    if (pop(stack, &rst) == true) printf("popped (%d)\n", rst);
  }
  dump_stack(stack);


  //終了処理
  free(stack);
  return (0);
}

実行結果

jm3nrhMac-mini-:c akio$ gcc lesson23s.c
jm3nrhMac-mini-:c akio$ ./a.out
初期状態--------------
stack dump: 00 00 00 00 00 00 00 00 00 00 
(stack_pointer = 0)

３回 取り出し--------------
stack is Empty!
stack is Empty!
stack is Empty!
stack dump: 00 00 00 00 00 00 00 00 00 00 
(stack_pointer = 0)

stack_pointer = 0
4回追加--------------
pushed (1)
pushed (2)
pushed (3)
pushed (4)
stack dump: 01 02 03 04 00 00 00 00 00 00 
(stack_pointer = 4)

4回追加--------------
pushed (5)
pushed (6)
pushed (7)
pushed (8)
stack dump: 01 02 03 04 05 06 07 08 00 00 
(stack_pointer = 8)

4回追加--------------
pushed (9)
pushed (10)
stack is FULL! (11 has not been stacked.)
stack is FULL! (11 has not been stacked.)
stack dump: 01 02 03 04 05 06 07 08 09 10 
(stack_pointer = 10)

３回 取り出し--------------
popped (10)
popped (9)
popped (8)
stack dump: 01 02 03 04 05 06 07 00 00 00 
(stack_pointer = 7)

５回追加--------------
pushed (11)
pushed (12)
pushed (13)
stack is FULL! (14 has not been stacked.)
stack is FULL! (14 has not been stacked.)
stack dump: 01 02 03 04 05 06 07 11 12 13 
(stack_pointer = 10)

6回取り出し--------------
popped (13)
popped (12)
popped (11)
popped (7)
popped (6)
popped (5)
stack dump: 01 02 03 04 00 00 00 00 00 00 
(stack_pointer = 4)

7回追加--------------
pushed (14)
pushed (15)
pushed (16)
pushed (17)
pushed (18)
pushed (19)
stack is FULL! (20 has not been stacked.)
stack dump: 01 02 03 04 14 15 16 17 18 19 
(stack_pointer = 10)

11回取り出し--------------
popped (19)
popped (18)
popped (17)
popped (16)
popped (15)
popped (14)
popped (4)
popped (3)
popped (2)
popped (1)
stack is Empty!
stack dump: 00 00 00 00 00 00 00 00 00 00 
(stack_pointer = 0)

3回追加--------------
pushed (20)
pushed (21)
pushed (22)
stack dump: 20 21 22 00 00 00 00 00 00 00 
(stack_pointer = 3)

4回取り出し--------------
popped (22)
popped (21)
popped (20)
stack is Empty!
stack dump: 00 00 00 00 00 00 00 00 00 00 
(stack_pointer = 0)

jm3nrhMac-mini-:c akio$

ChatGPT様に聞いてみた

このコードには、次のような潜在的なバグがあります。

スタックが空の場合のpop操作によるエラー処理が不足しています。
pop操作が成功したかどうかを返すbool値だけを使用しているため、
スタックが空の場合、0を指すポインタをデリファレンスし、未定義の動作を起こす可能性があります。
そのため、pop操作が失敗した場合にも、エラーメッセージを出力する必要があります。

push操作によるスタックオーバーフローの処理が不適切です。
現在の実装では、Stack_MAXに達したときにスタックオーバーフローのメッセージを出力していますが、
スタックに新しい要素を追加せずに終了しているため、スタックポインターの値は更新されず、以降の操作で予期しない振る舞いを引き起こす可能性があります。
代わりに、オーバーフローが発生した場合には、スタックを自動的に拡張するか、エラーメッセージを出力するか、例外をスローするかする必要があります。

スタックが空の状態でのdump_stack操作によるエラー処理が不足しています。
dump_stackは、スタック全体を表示するため、スタックが空の場合にも正常に動作する必要があります。現在の実装では、stack_pointerが0の場合には特別な処理がされていないため、スタックが空の場合に不適切な表示を行う可能性があります。

スタック操作関数が外部でスタックポインタを変更できるため、スタックの整合性が破壊される可能性があります。
スタックポインタはグローバル変数として定義され、スタック操作関数で変更されています。
このため、複数のスレッドで使用する場合、スタックの整合性が破壊される可能性があります。
スレッドセーフにするためには、スタックポインタをローカル変数にするか、スレッドセーフな同期方法を使用する必要があります。

Regenerate response

仰る通りです。

でも、
「これは仕様です。」とお応えしておきます。（開き直り！）

追記

このコードは、stackが満杯になってもpush()し続けられるし、stackが空になってもpop()し続けられる"仕様"です。
このような状況になったときはエラーメッセージを表示し、実行結果を返していて、どのように対処するかは呼ぶ側に委ねています。

ここまで読んでいただき、有り難うございました。

この記事が参加している募集

#AIとやってみた

27,969件

これまでの収益は全て、それを必要としておられる方々へ、支援機関を通して寄付させていただきました。この活動は今後も継続したいと思っています。引き続きよろしくお願いいたします。