Cでスタックを実装したよ
どうも.
暇すぎてCでスタックを実装するか〜となって実装したので,そのときのメモです.
ネットに転がってるサンプルコードなどを見てると,int型のデータしか格納できないものが多かったので,それはつまらんということで「なんでも入る」スタックを作りました.
TL;DR
汎用ポインタ(void *
)を使ってスタックを実装した.
何でも入る型
お分かりの方は多いと思いますが,そうです,あのvoid *
くん(別名汎用ポインタ)です.こいつには,どんなポインタでも代入することができます.型キャストを使えば,どんな型にも化けることができます.勿論,危険です.
結構身近な所にいる
この汎用ポインタですが,結構身近な所に潜んでいます.例えば,みなさん大好きなNULL
.C言語のNULLは,
#define NULL ((void *)0)
のように定義されています.void *
にキャストされた0
ということですね.
また,あなたの隣にいつも寄り添ってくれている,みなさんの大好きなmalloc
にもこいつは潜んでいます.glibc(GNUのCライブラリ実装)のmalloc
を見てみましょう.ここを参照.
void * __libc_malloc (size_t bytes) {
戻り値がvoid *
です.mallocの戻り値がどの型にもなるのは,こういう訳です.
というわけで,void *
を使って何でも入るスタックを作っていこうと思います.
実装
サンプルコードです.
#include <stdio.h> #include <stdlib.h> #define MAX 1000 #define CHECK(n) do { if(n == 0) { puts("no data"); exit(1); } } while(0) typedef struct stack { void *elem[MAX]; int stacktop; } stack; stack *init(stack *self) { self = malloc(sizeof(stack)); self->stacktop = 0; return self; } stack *push(stack *self, void *data) { if(self->stacktop > MAX) { fprintf(stderr, "stack error\n"); return NULL; } self->elem[self->stacktop++] = data; return self; } void *top(stack *self) { CHECK(self->stacktop); return self->elem[self->stacktop - 1]; } void *pop(stack *self) { CHECK(self->stacktop); return self->elem[--self->stacktop]; } int main(void) { stack *s; stack *is; s = init(s); is = init(is); push(s, (void *)"string"); push(s, (void *)"i am a"); push(s, (void *)"tensai"); for(int i = 0; i < 3; ++i) printf("%s\n", (char *)pop(s)); push(is, (void *)150); push(is, (void *)323); push(is, (void *)114514); for(int i = 0; i < 3; ++i) printf("%d\n", (int)pop(is)); }
なんの変哲もない普通なスタックの実装になってます.注目して欲しいのはmain関数の部分です.
push(s, (void *)"string"); push(s, (void *)"i am a"); push(s, (void *)"tensai"); for(int i = 0; i < 3; ++i) printf("%s\n", (char *)pop(s)); push(is, (void *)150); push(is, (void *)323); push(is, (void *)114514); for(int i = 0; i < 3; ++i) printf("%d\n", (int)pop(is));
文字列や数字が格納できています.今回はprintf周りのことが面倒くさかったんで一つのスタックに一種類の型のデータしか格納していませんが,勿論動的型付け言語のarrayのように複数の型のデータを格納することができます.
実行結果は以下の通りです.
tensai i am a string 114514 323 150
ちゃんとスタックしてます. ちなみに,
push(s, NULL);
のようなことも出来ます.