スタックの実装

目次

C言語にはないデータ構造

キューの実装と同様にここでもC言語では実装されていないデータ構造を再現していきます。

スタックとは

スタックは先入れ後出し(LIFO:Last In First Out)のデータ構造です。
下から上にデータを積み上げていき、上から取り出していくイメージです。

データの挿入を行うPUSHとデータを取り出すPOPという操作があります。

具体的に例を見ていきましょう。

2
8
4

下から順に4,8,2とデータが格納されています。

ここに3をPUSHすると以下のようになります。

3
2
8
4

これにPOPをすると3が取り出されスタックは以下のようになります。

2
8
4

スタックの実装

#include <stdio.h>

#define MAX_DATA 32

struct stack
{
	int arr[MAX_DATA];
	int top;	//末尾のデータのある配列の要素番号
};

int push(struct stack *stk, int input)
{
	if (stk->top <= MAX_DATA)
	{
		stk->top++;
		stk->arr[stk->top] = input;
		return 0;
	}
	else
	{
		printf("データを追加できません。\n");
		return -1;
	}
}

int pop(struct stack *stk)
{
	if (stk->top != 0)
	{
		int temp = stk->top;
		stk->top--;
		return stk->arr[temp];
	}
	else
	{
		printf("データがありません。\n");
		return -1;
	}
}

void init_stack(struct stack *stk)
{
	int i;

	for (i = 0; i < MAX_DATA; i++)
		stk->arr[i] = 0;
	stk->top = 0;
}

void show_stack(struct stack *stk)
{
	int i;
	for (i = 0; i < MAX_DATA; i++)
		printf("%d ", stk->arr[i]);

	printf("\ntop:%d\n\n", stk->top);
}

int main(void)
{
	int i;
	int d;
	struct stack stk;

	init_stack(&stk);
	for (i = 1; i <10; i++)
	{
		push(&stk, i * 3);
		show_stack(&stk);
	}

	d = pop(&stk);
	printf("\n%d\n", d);
	show_stack(&stk);

	return 0;
}

上から順に構造体stack、関数push()、関数pop()、関数init_stack()、関数show_stack()、main()関数の定義となっています。

構造体stackはデータを格納する配列arr[]と、末尾を表す変数topを持っています。
関数push()、pop()はそれぞれPUSH、POPの操作を実装しています。
関数init_stack()で構造体stackを初期化し、show_stack()で構造体stackの中身を表示しています。
これらの関数をmain()関数で使用しています。

キューのソースコードもそうですがint型で0はデータがない状態を表しています。
char型のプログラムに改変するのも良いでしょう。



コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です