C言語でスタック

はじめに

C言語は標準ライブラリにコンテナを扱う様な機能を持たないので、自作する必要があります。
本記事はC言語によるシンプルなスタックの実装です。

スタックの主な用途は以下の通りです。

• 空きリソース（メモリプール等）管理
• 深さ優先探索の探索先管理

PopもPushも定数オーダーなので気軽に使えます。

実装例

# include <stddef.h>
# include <stdint.h>
# include <limits.h>

# define MAX_ELEMENTS (255U)

# if UINT8_MAX < MAX_ELEMENTS
# error
# endif

typedef struct Stack_ {
    void* stack[MAX_ELEMENTS];
    uint8_t sp;
} Stack;

void Stack_Construct(Stack* stack_instance)
{
    stack_instance->sp = 0U;
}

int Stack_Push(Stack* stack_instance, void* element)
{
    uint8_t sp = stack_instance->sp;
    if (sp == MAX_ELEMENTS) {
        return 0;
    }
    stack_instance->stack[sp] = element;
    stack_instance->sp = sp + 1U;
    return (!0);
}

void* Stack_Pop(Stack* stack_instance)
{
    uint8_t sp = stack_instance->sp;
    void* element;
    if (sp == 0U) {
        return NULL;
    }
    stack_instance->sp = sp - 1U;
    element = stack_instance->stack[sp - 1U];
    return element;
}

備考

ペイロード型の値のうち、向こう値が存在するのであれば、要素数ゼロの時のStack_Popの戻り値を無効値とすることで「要素を取り出せなかった」事を表現できます。
一方、ペイロード型の値が全て有効値の場合、Stack_Popは値とは別に要素を取り出せたのか、取り出せなかったのかを表すブール値を返す必要があります。
もしくは、要素数ゼロの時のStack_Pop呼び出しを不正呼び出しとしてassertで保護し、代わりに要素数を取得するAPIを用意しても良いです。

# include <assert.h>

uint8_t Stack_GetNumberOfElements(Stack const* stack_instance)
{
    return stack_instance->sp;
}

void* Stack_Pop(Stack* stack_instance)
{
    uint8_t sp = stack_instance->sp;
    void* element;
    assert(0U < sp);
    stack_instance->sp = sp - 1U;
    element = stack_instance->stack[sp - 1U];
    return element;
}