Ｃ言語でスタック構造（LIFO(Last In First Out) : 後入先出）を自作してみました。
stack.h
#ifndef STACK_H_
#define STACK_H_
/* スタック構造体 */
typedef struct stack* Stack;
/* コンストラクタ */
Stack newStack(void);
/* スタックに要素を追加する */
void push(Stack, void*);
/* スタックから要素を取り出す */
void* pop(Stack);
#endif /* STACK_H_ */
配列を用いる
（ヘッダファイルに#define CAPACITY (256)を追加。数字の部分は任意）
stack.c
/* スタック構造 */
struct Stack{
void* value[CAPACITY];
size_t size;
};
/*
* スタックのコンストラクタ
*/
Stack newStack(void){
//メモリ確保
Stack stack=(Stack)malloc(sizeof(struct Stack));
if(!stack){//メモリ確保失敗
abort();
}
//スタックのサイズを0にセットする
stack->size=0;
return stack;
}
/*
* スタックの先頭に要素を追加
* stack : スタック
* value : 追加するデータ
*/
void push(Stack stack, void* value){
//データが追加できない場合はエラー
if(stack->size>=CAPACITY){
abort();
}
//データをセット
stack->value[stack->size++]=value;
}
/*
* スタックから要素を取り出す
* stack : スタック
* 返却値 : 取り出すデータ
*/
void* pop(Stack stack){
if(stack->size){
return stack->value[--stack->size];
}else{
return NULL;
}
}
自己参照構造体を用いる
stack.c
#include <stdlib.h>
#include "stack.h"
/* ノード */
typedef struct node{
void* value; //データ
struct node* next; //次のデータの格納位置を示すポインタ
}Node;
/* スタック構造 */
struct stack{
Node* front; //先頭ノードへのポインタ
};
/*
* スタックのコンストラクタ
*/
Stack newStack(void){
//メモリ確保
Stack stack=(Stack)malloc(sizeof(struct stack));
if(!stack){//メモリ確保失敗
abort();
}
//スタックの先頭ノードをNULLにセットする
stack->front=NULL;
return stack;
}
/*
* スタックの先頭に要素を追加
* stack : スタック
* value : 追加するデータ
*/
void push(Stack stack, void* value){
//メモリ確保
Node* node=(Node*)malloc(sizeof(Node));
if(!node){//メモリ確保失敗
abort();
}
//ノードにデータをセット
node->value=value;
//新しいノードの次は現在の先頭ノード
node->next=stack->front;
//先頭ノードは新しいノード
stack->front=node;
}
/*
* スタックから要素を取り出す
* stack : スタック
* 返却値 : 取り出すデータ
*/
void* pop(Stack stack){
//要素が空ならNULLを返す
if(!stack->front){
return NULL;
}
//先頭ノードを取得
Node* node=stack->front;
//返却値を取得
void* value=node->value;
//スタックの先頭を繋ぎ替える
stack->front=node->next;
//旧先頭ノードを解放
free(node);
//取得した値を返す
return value;
}
サンプルプログラム：逆ポーランド記法
今回の仕様は
- 扱う数値：実数、負数も扱う。指数表記(1e+9等)は扱わない。
- 扱う演算子：+(加法), -(減法), "*"(乗法), /(除法), %(剰余), "^"(冪乗)
- これらをコマンドラインに入れて実行する。
- コマンドラインの最後には"="を入れる。
コマンドラインにアスタリスク(*)、ハット(^)を入力するときは、ダブルクォーテーションで囲まなけらばならない。
rpn.c
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"
/*
* オペランドを取得する
* stack : スタック
* x : (出力)左オペランド
* y : (出力)右オペランド
*/
void pop2(Stack stack, double* x, double* y){
//右オペランドを取得する（右オペランドから取り出されることに注意!!）
double* ptr=(double*)pop(stack);
if(!ptr)abort();
*y=*ptr;
free(ptr);
//左オペランドを取得する
ptr=(double*)pop(stack);
if(!ptr)abort();
*x=*ptr;
free(ptr);
}
/*
* 数値判定
* 今回は指数表記（1e+9）は扱わない。
*/
bool isNumeric(const char* s){
const char* c=s;
if(s[0]=='-'){//マイナスで始まる
if(strcmp(s,"-")){
c++;
}else{//先頭のマイナスのみ
return false;
}
}
if(s[0]=='+'){//プラスで始まる
if(strcmp(s,"+")){
c++;
}else{//プラスのみ
return false;
}
}
//小数点（ピリオド）の数
int p=0;
while(*c){//文字列末尾までチェック
if(*c=='.'){//小数点
if(++p>1){//小数点が2個以上
//非数値
return false;
}
}else if(!isdigit(*c)){//数字以外の文字が含まれる
//非数値
return false;
}
c++;
}
return true;
}
/*
* コマンドラインからオペランドと演算子を取得する
* 扱う数値：実数、負数も扱う。指数表記は扱わない。
* 扱う演算子：+(加法), -(減法), "*"(乗法), /(除法), %(剰余), "^"(冪乗)
* コマンドラインの最後は"="
*/
int main(int argc, char* argv[]){
//スタック初期化
Stack stack=newStack();
for(int i=1;i<argc;i++){
if(!strcmp(argv[i],"=")){//等号
//スタックから値を取り出す
double* z=(double*)pop(stack);
if(z){
//出力
printf("%lf\n",*z);
free(z);
}else{
abort();
}
//終了
break;
}else{
//メモリ領域確保
double* ptr=(double*)malloc(sizeof(double));
if(!ptr){
abort();
}
if(isNumeric(argv[i])){//数値
//数値をそのまま格納
*ptr=atof(argv[i]);
}else{
double x,y;
if(!strcmp(argv[i],"+")){//加法
pop2(stack,&x,&y);
*ptr=x+y;
}else if(!strcmp(argv[i],"-")){//減法
pop2(stack,&x,&y);
*ptr=x-y;
}else if(!strcmp(argv[i],"*")){//乗法
pop2(stack,&x,&y);
*ptr=x*y;
}else if(!strcmp(argv[i],"/")){//除法
pop2(stack,&x,&y);
if(y){
*ptr=x/y;
}else{//ゼロ除算
abort();
}
}else if(!strcmp(argv[i],"%")){//剰余
pop2(stack,&x,&y);
if(y){
*ptr=fmod(x,y);
}else{//ゼロ除算
abort();
}
}else if(!strcmp(argv[i],"^")){//冪乗
pop2(stack,&x,&y);
//(x==0 and y<=0) or (x<0 and yが整数でない) ときには領域エラーが起きる
*ptr=pow(x,y);
}else{//数値でも演算子でもない
free(ptr);
abort();
}
}
push(stack,(void*)ptr);
}
}
//スタック解放
free(stack);
//プログラム終了
return 0;
}