C言語のきほん「スタック」

本ブログでは、これまでに「配列」を扱っている。

配列では、格納したデータに対して、インデックスを指定してアクセスできた。

この「インデックスを指定してアクセスする」以外の方法で、データの追加や削除を行うデータ管理方法のひとつに、「スタック」がある。

スタックには、pushという操作でデータを追加し、popという操作でデータを取り出す。
push操作では、それまでに格納されたデータの先頭に新しいデータが追加され、pop操作では、先頭にあるデータが取り出される。

このように、後で入れたものを先に取り出すことを「後入れ先出し（LIFO:Last in First Out)」と呼ぶ。

このようなデータ管理の方法を配列を使って実現できる。

それでは、この例をプログラムでみてみよう。

なお、本プログラムは、Windows 11 Home（23H2）上で、 
 Visual Studio Code（1.91.1）を使用して作成し、gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0で コンパイルしている。

//スタック

#include <stdio.h>

#define STACK_SIZE 5

//スタックとして利用する配列
int stack[STACK_SIZE];
int head_index = -1;

void push(int value)
{
    head_index++;
    stack[head_index] = value;
}

int pop()
{
    int value = stack[head_index];
    head_index--;
    return value;
}

void printout()
{
    for (int i = 0; i <= head_index; i++)
    {
        printf("[%d]",stack[i]);
    }
    printf("\n");
    
}

void main()
{
    push(5);printout();
    push(9);printout();
    push(3);printout();
    printf("pop %d\n",pop()); printout();
    printf("pop %d\n",pop()); printout();
    printf("pop %d\n",pop()); printout();

    
}

実行結果

[5]
[5][9]
[5][9][3]
pop 3
[5][9]
pop 9
[5]
pop 5

このプログラムでは、配列をスタックとして使用している。
push関数で、配列に値を入れるが、このとき、先頭の場所を覚えておくための変数head_indexの値を１だけ増やす。
pop関数では、先頭の要素の値を返すとともに、head_indexの位置を１つだけ減らす。

実行結果をみて、スタックの動作を確認しよう。

（参考）「C言語 新版 ゼロからはじめるプログラミング」 三谷 純 （著） 翔泳社