アルゴリズムとデータ構造編【データ構造】 第5章 スタック

この章の概要

この章の概要です。

スタック

この章では、スタックというデータ構造を説明します。 これは非常に重要なデータ構造なので、確実に理解しましょう。

データ構造なので、複数のデータを格納できる訳ですが、データの入れ方と取り出し方に特徴があります。
スタックでは、常に、一番最後に格納したデータしか取り出せません。 このような特徴を、後入れ先出しとか、LIFO (Last In First Out) と呼びます。

後入れ先出しのイメージとして、机の上に積み重ねた本という例えがよく使われます。 本をどんどん積んでいくとすれば、上へ上へ重ねていくことになるでしょう。 逆に、積み重なった本を手に取るとすれば、一番上にある本から順番に取っていきます。 このとき、1冊1冊の本が、スタックに格納されたデータであるという訳です。
実際、スタックにデータを格納することを、積む(push) と表現し、 また、データを取り出すことを、降ろす(pop) と表現します。

スタックを使う場面は、「一旦データを退避させておきたいとき」です。 実例は、別に章を割いて紹介します。


スタックというデータ構造にとって、最低限必要な機能は以下のものです。

データを降ろそうにも、既にデータが存在しないこともあるので、空かどうか調べる手段も必要です。

空であれば、pop がエラーを返すようにすればいいと思われるかも知れません。 しかし、スタックが管理しているデータの型にとって、確実にエラー値として使える値が存在している保証がありません。

これらの機能を持ってさえいれば、スタックが内部的にどのような形でデータを管理していても構わないといえます。 このように、必要な機能の要件だけが定義されているようなデータ構造を、抽象データ構造と呼びます。
スタックは、抽象データ構造なので、内部のデータの管理方法には自由度があります。 本章では、データ管理に配列を使う実装方法を見た後、連結リストを利用した実装方法も取り上げます。

配列による実装

まずは配列を使った実装を確認します。

/* main.c */

#include <stdio.h>
#include <string.h>
#include "stack.h"


/* コマンド */
enum Cmd_tag {
	CMD_PUSH,
	CMD_POP,
	CMD_EXIT,

	CMD_NUM
};

/* コマンド文字列の種類 */
enum CmdStr_tag {
	CMD_STR_SHORT,
	CMD_STR_LONG,

	CMD_STR_NUM
};

/* コマンドの戻り値 */
enum CmdRetValue_tag {
	CMD_RET_VALUE_CONTINUE,
	CMD_RET_VALUE_EXIT,
};

/* コマンド文字列 */
static const char* CMD_STR[CMD_NUM][CMD_STR_NUM] = {
	{ "u", "push" },
	{ "o", "pop" },
	{ "e", "exit" }
};


static void create_stack(void);
static void delete_stack(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_push(void);
static enum CmdRetValue_tag cmd_pop(void);
static enum CmdRetValue_tag cmd_exit(void);
static void push_elem(int value);
static int pop_elem(void);


/* コマンド実行関数 */
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
	cmd_push,
	cmd_pop,
	cmd_exit
};


Stack gStack;


int main(void)
{
	create_stack();

	while( 1 ){
		print_explain();

		if( get_cmd() == CMD_RET_VALUE_EXIT ){
			break;
		}

		print_blank_lines();
	}

	delete_stack();

	return 0;
}

/* スタックを作成 */
void create_stack(void)
{
	gStack = stack_create( 128 );
}

/* スタックを削除 */
void delete_stack(void)
{
	stack_delete( gStack );
	gStack = NULL;
}

/*
	説明文を出力
*/
void print_explain(void)
{
	puts( "コマンドを入力して下さい。" );
	printf( " スタックに要素を積む: %s (%s)\n", CMD_STR[CMD_PUSH][CMD_STR_SHORT], CMD_STR[CMD_PUSH][CMD_STR_LONG] );
	printf( " スタックから要素を降ろす: %s (%s)\n", CMD_STR[CMD_POP][CMD_STR_SHORT], CMD_STR[CMD_POP][CMD_STR_LONG] );
	printf( " 終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
	puts( "" );
}

/*
	空白行を出力
*/
void print_blank_lines(void)
{
	puts( "" );
	puts( "" );
}

/*
	コマンドを受け付ける
*/
enum CmdRetValue_tag get_cmd(void)
{
	char buf[20];
	size_t len;
	enum Cmd_tag cmd;
	int i;

	fgets( buf, sizeof(buf), stdin );

	len = strlen( buf );
	buf[len - 1] = '\0';  /* fgets関数が受け取った改行文字を消す */

	for( i = 0; i < CMD_NUM; ++i ){
		if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
		 || strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
		){
			cmd = i;
			break;
		}
	}

	if( 0 <= cmd && cmd < CMD_NUM ){
		return CMD_FUNC[i]();
	}
	else{
		puts( "そのコマンドは存在しません。" );
	}

	return CMD_RET_VALUE_EXIT;
}

/*
	pushコマンドの実行
*/
enum CmdRetValue_tag cmd_push(void)
{
	char buf[40];
	int value;

	puts( "積む数値データを入力して下さい。" );
	fgets( buf, sizeof(buf), stdin );
	sscanf( buf, "%d", &value );

	push_elem( value );
	
	return CMD_RET_VALUE_CONTINUE;
}

/*
	popコマンドの実行
*/
enum CmdRetValue_tag cmd_pop(void)
{
	if( stack_is_empty( gStack ) ){
		puts( "スタックは空です。" );
	}
	else{
		printf( "%d を降ろしました。\n", pop_elem() );
	}
	
	return CMD_RET_VALUE_CONTINUE;
}

/*
	exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
	puts( "終了します。" );
	
	return CMD_RET_VALUE_EXIT;
}

/*
	要素を積む

	引数:
		value:	積む要素の数値データ。
*/
void push_elem(int value)
{
	stack_push( gStack, value );
}

/*
	要素を降ろす

	戻り値:
		降ろされた要素。
*/
int pop_elem(void)
{
	return stack_pop( gStack );
}
/* stack.c */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "stack.h"

static void* xmalloc(size_t size);


struct Stack_tag {
	int*    data;    /* 要素を格納する動的配列 */
	int     size;    /* data の要素数 */
	int     top;     /* 最上段の添字 */
};


/* スタックを作る */
Stack stack_create(int size)
{
	struct Stack_tag* stack;

	assert( size > 0 );
	
	stack = xmalloc( sizeof(struct Stack_tag) );
	stack->data = xmalloc( sizeof(int) * size );
	stack->size = size;
	stack->top = 0;

	return stack;
}

/* スタックを削除する */
void stack_delete(Stack stack)
{
	free( stack->data );
	free( stack );
}

/* スタックに要素を積む */
void stack_push(Stack stack, int value)
{
	assert( stack->top < stack->size );

	stack->data[stack->top] = value;
	stack->top += 1;
}

/* スタックから要素を降ろす */
int stack_pop(Stack stack)
{
	int pop_value;

	assert( !stack_is_empty(stack) );

	stack->top -= 1;
	pop_value = stack->data[stack->top];

	return pop_value;
}

/* スタックが空かどうか調べる */
int stack_is_empty(Stack stack)
{
	return stack->top <= 0;
}


/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
	void* p = malloc( size );
	if( p == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( EXIT_FAILURE );
	}
	return p;
}
/* stack.h */

#ifndef STACK_H
#define STACK_H


typedef struct Stack_tag* Stack;


/*
	スタックを作る

	引数:
		size:	格納できる要素数
	戻り値:
		作成されたスタック。
		使い終わったら、stack_delete関数に渡して削除する。
*/
Stack stack_create(int size);

/*
	スタックを削除する

	引数:
		stack:	スタック
*/
void stack_delete(Stack stack);

/*
	スタックに要素を積む

	引数:
		stack:	スタック
		value:	積む要素
*/
void stack_push(Stack stack, int value);

/*
	スタックから要素を降ろす

	引数:
		stack:	スタック
	戻り値:
		降ろされた要素
*/
int stack_pop(Stack stack);

/*
	スタックが空かどうか調べる

	引数:
		stack:	スタック
	戻り値:
		スタックが空であれば 0以外を返し、空でなければ 0 を返す。
*/
int stack_is_empty(Stack stack);


#endif

スタック本体の実装は、stack.h と stack.c に分離させました。 このようにする理由は、この後で連結リスト版を実装するときに分かります。
main.c は、これまでの章と同様、実際の動作を確認するために、標準入力からコマンドを受け付けて実行するスタイルになっています。

stack.h では、Stack という型を typedef(C言語編第26章参照)で作り出しています。 stack_create関数がこの型の動的な変数を生成し、そのポインタを返します。 使い終わったら、stack_delete関数に渡すことで、解放されます。
このような作りは、第3章で見たように、複数のスタックを同時に使えるようにするために必要になります。 stack_create関数を呼び出すたびに、新規のスタックが作られており、それは以前に作ったスタックとは別物である訳です。

stack_push関数、stack_pop関数にも、Stack型の引数があります。 こうすることで、指定したスタックに対して、push や pop の操作を行えるようになっています。 (main.c では、結局1つのスタックしか作っていませんが)


さて、配列によってスタックを実装する場合、指定された数の領域をまとめて確保することになります。 汎用的な作りを目指さなければ、固定配列でも構わないぐらいですが、普通は、必要なサイズは使用目的によって異なるでしょうから、動的に確保することになります。
1度配列を用意してしまえば、push も pop も非常に高速に行えます。 この高速さが、配列版の利点と言えます。

欠点としては、いつか満杯になってしまう可能性を考えておかねばならない点が挙げられます。 満杯になったときの対処として、今回のサンプルでは、assert(C言語編第28章参照)で停止させる道を選びましたが、 realloc関数(C言語編第35章参照)を使って領域を拡張するといった手段も考えられます。
また、スタックを作るときに指定したサイズが大きすぎると、ほとんどの領域が使われずじまいになる可能性がありますから、 メモリを無駄に浪費してしまうかも知れません。 適切なサイズの選択が難しい場合、これは大きな欠点になります。
なお、配列は、途中の要素の挿入や削除を苦手としていますが、スタックの実装に使う場合、 末尾だけの操作で済むため後続の要素をずらすような処理が起こらず、問題になりません。

連結リストによる実装

次に、連結リストによる実装を試してみます。

/* stack.c */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "stack.h"

static void* xmalloc(size_t size);


struct StackList_tag {
	struct StackList_tag*  next;    /* 次の要素へのポインタ */
	int                    value;   /* 要素の値 */
};

struct Stack_tag {
	struct StackList_tag*  head;    /* 先頭の要素へのポインタ */
};


/* スタックを作る */
Stack stack_create(int size)
{
	struct Stack_tag* stack;
	
	stack = xmalloc( sizeof(struct Stack_tag) );
	stack->head = NULL;

	return stack;
}

/* スタックを削除する */
void stack_delete(Stack stack)
{
	struct StackList_tag* p = stack->head;
	struct StackList_tag* tmp;

	/* 連結リストの要素を削除 */
	while( p != NULL ){
		tmp = p->next;
		free( p );
		p = tmp; 
	}

	free( stack );
}

/* スタックに要素を積む */
void stack_push(Stack stack, int value)
{
	struct StackList_tag* p;
	
	p = xmalloc( sizeof(struct StackList_tag) );
	p->value = value;

	/* 新たな要素を先頭に置く */
	p->next = stack->head;
	stack->head = p;
}

/* スタックから要素を降ろす */
int stack_pop(Stack stack)
{
	int pop_value;
	struct StackList_tag* tmp;

	assert( !stack_is_empty(stack) );

	tmp = stack->head;
	pop_value = stack->head->value;
	stack->head = stack->head->next;
	free( tmp );

	return pop_value;
}

/* スタックが空かどうか調べる */
int stack_is_empty(Stack stack)
{
	return stack->head == NULL;
}


/* エラーチェック付きの malloc関数 */
void* xmalloc(size_t size)
{
	void* p = malloc( size );
	if( p == NULL ){
		fputs( "メモリ割り当てに失敗しました。", stderr );
		exit( EXIT_FAILURE );
	}
	return p;
}

配列版を実装したときに使った stack.c だけを修正しています。 stack.h および main.c に変更はありません。
この状態で実行すると分かるように、もちろんコンパイルも通りますし、正しく実行できます。

抽象データ構造(抽象データ型)の利点がここにあります。 必要な機能の要件は stack.h に集められており、この形を壊さなければ、具体的な実装の書かれている stack.c を変更しても、使う側には影響を与えません。 配列版と連結リスト版とで、使い方を変える必要はないのです。
ここで、stack.h は内部実装と、外部の利用者との間に置かれる窓口のようにみなすことができます。 一般に、このような窓口をインタフェースと呼びます。
まとめると、インタフェースを変更しない限り、外部の利用者への影響は無いということになります。

外部の利用者への "影響" というのは、コードの変更が不要であるということです。 内部実装が変更されれば、性能に変化は起こりますから、その意味では影響が皆無であるという訳ではありません。

実装をよく観察すると、例えば、stack_create関数の引数size が実は使われていないことが分かりますが、 使わなくても、仮引数を void に変えてしまうのではなく、あえて残しておくことで、配列版との共通性を維持しています。 この考え方は行き過ぎると逆効果になりますが、この程度であれば許される範囲でしょう。

例えば、配列版で引数が 6個ある関数があったとして、連結リスト版では実は 1個も使っていないとなると、流石にやり過ぎでしょう。 そのような特定の実装に大きく依存している場合は、共通のヘッダの中に含めてしまうのではなく、専用のヘッダに拡張機能として定義するなどして、 実装依存であることを示した方が良いです。

なお、ここではスタックの最上段が、連結リストの先頭になるように実装しています。 単方向の連結リストを使っている場合、末尾を探すのは大変なので、push/pop の対象となる最上段が先頭に来る方が、実装が楽になります。


連結リストによってスタックを実装する場合、メモリが許す限りは幾らでも要素を追加していける点が利点となります

欠点としては、連結リストの実装のために、nextポインタを必要とするためにメモリの利用効率が劣ることや、 push のときに動的なメモリ確保を、pop のときに解放処理を行う必要があるため、push/pop の頻度が多い場合、 処理速度的に不利になることが挙げられます。

まとめ

スタックの実装を通じて、抽象データ構造という考え方を取り上げました。 この考え方を使えば、スタックの内部実装が、配列を使用したものでも、連結リストを使用したものであっても、利用者は同じコードのまま取り扱えます。

配列版と連結リスト版の長所と短所をまとめておきます。

実装方法 長所 短所
配列
  • push/pop ともに高速に行える。
  • スタックが満杯になる可能性を考慮しなければならない。
  • 事前に大きさを決めなければならず、決定を誤ると、多くの領域が無駄になってしまう。
連結リスト
  • メモリが許す限り、幾らでも push できる。
  • push/pop のたびに動的なメモリ確保および解放処理が発生するため、速度的に不利。
  • 次の要素を指し示すポインタを保持しなければならないので、メモリの使用効率が劣る。

それぞれに欠点がありますが、これらへの解決策も無いわけではありません。
配列版の欠点は、スタックが一杯になってきたときに領域を拡張させるような実装をすれば、 ある程度解決できます(ただし、拡張の起こる瞬間に処理速度が大きく低下する欠点が生まれます)
連結リスト版の欠点のうち、push/pop のたびに起こる動的なメモリ確保・解放については、 あらかじめ、別の場所に要素を複数個確保しておいて、push のときにその中から1つを取り出して連結リストへつなげることで効率化できます。 pop されたら、メモリを解放するのではなく、連結リストから取り外して、元の場所に返却します。 これは、フリーリストなどと呼ばれる手法で、様々な箇所で応用が利く考え方です。


練習問題

問題@ stack.c/h に、スタックの中身を標準出力へ出力する関数を追加して下さい。

問題A 要素を降ろすことなく、最上段にある要素を参照したいことがよくあります。 このような操作は peek あるいは top操作と呼ばれるのですが、これを実現する関数を stack.c/h に追加して下さい。

問題B 2つのスタックを作り、一方のスタックに適当なデータを積みます。 その後、空になるまで pop を繰り返し、そのつど、他方のスタックへ pop された要素を push していくことを繰り返すプログラムを作成して下さい。 この作業を終えた後、スタックの中身はどうなっていますか?

問題C この章の配列版のサンプルでは、stack_create関数に渡したサイズを超えたとき assert によって停止させています。 これをやめて、領域が不足したときには、領域を倍に自動的に拡張するように stack.c を書き換えて下さい。


解答ページはこちら


参考リンク

更新履歴

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2014/12/20 サンプルプログラムで、コマンド処理の方法を整理。

'2013/6/1 連結リスト版の stack_pop関数で、メモリの解放が行われていなかったのを修正。

'2011/9/30 新規作成。



前の章へ

次の章へ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ