データ構造/スタック - nkym_memo @ ウィキ

スタック(stack)

• スタック(LIFO;last-in first-out) 挿入と削除がともにリストの先頭でのみ行われるもの。

• 頂上(top)/底(bottom) スタックにおける最初/最後

• 積む(push,push down)/降ろす,取り出す(pop,pop up) スタックへのデータを挿入/削除

例)
プログラムの実行中、サブルーチンを呼び出すときに使用。

サンプルプログラム(配列を用いたスタック）

基本的には、スタックを積む時

x[stack_pointer++] = data; 

スタックからデータを降ろす時

data = x[--stack_pointer];

とする。

#define STACK_SIZE 100

typedef long ELEM; 

ELEM stack[STACK_SIZE];
int stack_pointer;

void error(char *s)
{
	fprintf(stderr,s);
	exit(1);
}

void init()
{
	stack_pointer = 0;
}

void push(ELEM x)
{
	if(n >= STACK_SIZE){
		error("stack overflow\n");
	}
	stack[stack_pointer++] = x;
}

void pop(ELEM x)
{
	if(n <= 0){
		error("stack underflow\n");
	}
	return stack[--stack_pointer];
}

int empty()
{
	return stack_pointer == 0;
}

---

参考文献

• 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)