スタック

先週書いた連結リストのコードをライブラリにして、スタックを実装してみた。

#include
#include

#include "linkedlist.h"

#define Stack Cell

Stack *Push(Stack *stack, int x);
int Pop(Stack **stack);

int main(void)
{
    Stack *stack;
    int n;

    stack = NULL;

    stack = Push(stack, 1);
    stack = Push(stack, 3);
    stack = Push(stack, 5);

    DisplayList(stack);

    n = Pop(&stack);
    printf("%d <- ", n);
    DisplayList(stack);
    FreeList(stack);

    return 0;
}

Stack *Push(Stack *stack, int x)
{
    Stack *list;
    list = Cons(x, stack);
    return list;
}

int Pop(Stack **stack)
{
    int x;
    x = Head(stack);
    return x;
}

typedef struct cell Cell;

Cell *NewCell(int val);
Cell *Cons(int val, Cell *list);
Cell *Insert(Cell *list, int pos, int val);
Cell *Delete(Cell *list, int pos);
int Head(Cell **list);
void DisplayList(Cell *list);
void FreeList(Cell *list);

#include

#include "linkedlist.h"

typedef struct cell {
    int value;
    struct cell *next;
} Cell;

Cell *NewCell(int val)
{
    Cell *data;

    data = (Cell *)malloc(sizeof(Cell));
    data->value = val;
    data->next = NULL;

    return data;
}

Cell *Cons(int val, Cell *list)
{
    Cell *data;

    data = NewCell(val);
    data->next = list;

    return data;
}

Cell *Insert(Cell *list, int pos, int val)
{
    Cell *cell1, *cell2;
    int i = 1;

    if (pos == 0) {
        list = Cons(val, list);
    } else {
        cell1 = list;
        while (i < pos) {
            cell1 = cell1->next;
            i++;
        }
        cell2 = NewCell(val);
        cell2->next = cell1->next;
        cell1->next = cell2;
    }

    return list;
}

Cell *Delete(Cell *list, int pos)
{
    Cell *cell1, *cell2;
    int i = 1;

    if (pos == 0) {
        cell2 = list;
        list = cell2->next;
        free(cell2);
    } else {
        cell1 = list;
        cell2 = cell1->next;
        while (i < pos) {
            cell1 = cell2;
            cell2 = cell1->next;
            i++;
        }
        cell1->next = cell2->next;
        free(cell2);
    }

     return list;
}

int Head(Cell **list)
{
    int val;

    val = (*list)->value;
    *list = Delete(*list, 0);

    return val;
}

void DisplayList(Cell *list)
{
    printf("%d", list->value);
    if (list->next == NULL) {
        printf("\n");
    } else {
        printf(", ");
        DisplayList(list->next);
    }
}

void FreeList(Cell *list)
{
    Cell *next = list->next;

    free(list);
    if (next != NULL) {
        FreeList(next);
    }
}

linkedlist.h で

typedef struct cell Cell;

とあるのは、構造体の中身を隠蔽して、その存在だけを公開する書き方。こうすることで、ライブラリを利用する側からは構造体を直接操作することはできなくなる（操作用の関数を使って操作する）。

実行結果：

takatoh@nightschool $ gcc -Wall main.c -c
takatoh@nightschool $ gcc -Wall linkedlist.c -c
takatoh@nightschool $ gcc -Wall main.o linkedlist.o -o stack
takatoh@nightschool $ ./stack
5, 3, 1
5 <- 3, 1

出力の１行目は値（整数）を３つ push したあとのスタックの状態。２行目の <- の左側は pop して取出した値で、右側がそのあとのスタックの状態。 期待通りに動いてるようだ。