Super Technique 講座

スタック

「スタック」の本質は「操作」である。一応データ構造ではあるのだが、操作を制限することによって、非常に有用な結果を得ることができる。「コンピュータ科学最大の発明」とまでの最大級の賛辞を述べる人もいるくらいである。

プロセスのメモリレイアウトで「スタック」あるいは特に「システムスタック」などの言葉が使われるが、これもやはり「スタックの操作」を基本としてすることから、そういう名前がついているだけであり、このページの説明とは直接関係しない。このページでは、プログラマがデータ構造として作るスタックの使い方を中心に述べていく。 → Java 講座の「スタック」




スタックの定義

比較的難しめの言語の本格的教科書(K&Rとかストロウストラップとか)には、まず確実にその言語で書かれたスタックがあったりする。しかし、初級者レベルではプログラムとしては理解できても、「それをどう使うの???」という疑問しか浮かばないだろう。実はスタックは「使い方」である。データ構造としては、別に順序的にアクセスできれば何でも良いのだが、簡単に説明するために配列を例にしよう。

#define STACKSIZE  1024
static int Stack[STACKSIZE];
static int sp = 0;

void push( int v ) 
{
    Stack[sp++] = v;
    if( sp >= STACKSIZE ) {
        fprintf( stderr, "Stack overflow!!!\n" );
	/* ホントの実装では、realloc を使って自動的に伸びる配列にする */
    }
}

int pop( void ) 
{
    if( sp > 0 ) {
         return Stack[--sp];
    } else {
         fprintf( stderr, "Stack underflow!!!\n" );
	 return -1;
    }
}

/* これは要求されるわけではないが、あるとエラー処理を考えなくて良い */
int isEmpty( ) 
{
   if( sp > 0 ) return 0;
   return 1;
}

基本的にこれがスタックである。これでは何の説明にもなっていないが、とにかく push という操作と、pop という操作が定義されていることを理解されてたい。つまり、スタックではこの2つの操作しか定義されず、他のアクセス方法によっていじられない、という保証があるのである。だから、通常 Stack と sp は static で宣言して、他のファイルからは見えないようにするのが普通である。

操作を見てみると、要するにこれは次の操作が実装されているのである。

push
スタックの一番上に新しくデータを「乗せる」。
pop
スタックの一番上からデータを「取り去る」。

よくスタックについて、「これはキャフェテリアの皿である... 皿の上に皿が重なるが、一番上の皿を取るか、一番上に新しく皿を乗せるかどちらかしかできない」というような説明をする。この2つの操作をよくイメージして欲しい。

入れ子構造の処理〜HTMLの解析

ではこれをどう使うのか。実はスタックは、「入れ子構造」を扱うのに最も適した方法論なのである。コンピュータの世界(あるいは実世界でも)では、「入れ子構造」は頻繁に現われる。Cの「{}」だってちゃんと「{」と「}」とが対応の取れた入れ子構造を作り上げるし、HTMLだって開きタグと閉じタグで入れ子構造が作り上げられる。このような「入れ子構造」を合理的に扱う手法がこのスタックであるのだ。

サンプルとして、HTMLの構造を理解するプログラムを考えてみよう。ただし、ちょっとXMLがかったHTMLであり、必ず開きタグと閉じタグが対応しているものとする。例えば次の通り。

<html>
   <head>
      <title>test</title>
   </head>
   <body>
      <h1>test</h1>
      <p>これが
         <b>内容</b>
      だ!</p>
   </body>
</html>

こういう風にインデントをつけると、入れ子の関係が見えやすい。つまり、全体は html タグの中に入っており、html タグの中には head タグとbodyタグがあり、head タグの中には title タグがあり、body タグの中には...という入れ子の構造は誰にでも理解できよう。これをコンピュータに理解させるのに、使われるデータ構造がスタックなのである。つまり、操作は次のようになる。

  1. テキストの順にタグを1つづつ得ていく。
  2. そのタグが開きタグならば、スタックに push する。
  3. そのタグが閉じタグならば、スタックから pop し、閉じタグと pop したタグが同一の種類に属していることを確認する。
  4. 入力が終った時に、スタックには何も入っていない。

これがHTMLの入れ子構造が正当であることの検証なのである。これで必要かつ充分であることを、頭の中 or 紙に書いて確認されたい。ではこれを実装してみよう。

/* プロトタイプ宣言 */
/* 次のタグを得る。戻り値はタグ名、引数kindに開きタグ(==0) or 閉じタグ(==1) の
区別が入る。EOF の時には戻り値が NULL である。*/
char *get_nextTag( int *kind );  

void push( char *s ); /* char * を保持するスタックの push */
char *pop( void ); /* char * を保持するスタックの pop。 */
int isEmpty( void ); /* スタックが空か? */

/* プログラム本体 */

/* HTMLが正当であれば 0、構造がおかしければ -1 を返す */
int isValid( ) 
{
    int ret;
    char *tag;
    
    while( (tag = get_nextTag( &ret )) != NULL ) {
       if( ret == 0 ) {  /* 開きタグの場合 */
           push( tag );
       } else {          /* 閉じタグの場合 */
           char *poped;
           if( isEmpty() ) {  /* すでに空ならば、閉じタグが余分 */
	       return -1;
	   }
           poped = pop();
           if( strcmp( tag, poped ) != 0 ) { 
	       return -1;  /* 開き〜閉じ関係がおかしい */
           }
      }
   }
   if( isEmpty() == 1 ) {
      return 0;
   } else {  /* 入力が終っても空でなければ、閉じタグが不足 */
      return -1;
   }
}

上の例だと、get_nextTag() の戻り値は次の系列で発生する。

html(0), head(0), title(0), title(1), head(1), body(0), h1(0), h1(1), p(0), 
b(0), b(1), p(0), body(1), html(1)

この系列のデータが読み込まれた時、スタックがどう変化していくのかを追って見よう。

タグ種別spStack(下から順に)
html開き1html
head開き2html,head
title開き3html,head,title
title閉じ2html,head
head閉じ1html
body開き2html,body
h1開き3html,body,h1
h1閉じ2html,body
p開き3html,body,p
b開き4html,body,p,b
b閉じ3html,body,p
p開き2html,body
body閉じ1html
html閉じ0

と、このように正しくHTMLの検証ができるのである。つまり、開き〜閉じの関係にある入れ子構造は、スタックを使えば検証できるのである(例題として、回文を検証するプログラムを書いてみると良かろう)。

それだけではない。いわゆるプログラミング言語は、現在では普通はBNFという形式的記述法によって定義される。このBNFを処理するツールとして、yacc(あるいは GNU bison)があるが、このような文法記述(難しく言うと「文脈自由文法」の一種である LR-LA(1)文法)も、スタックを使って処理される。だから、プログラムがコンパイルできることも、実はスタックのおかげなのであり、複雑度は違っても先程のHTML解析と同じような処理をしているのである。いかにスタックが偉大なものであるか、ご理解いただけたかな? このスタックを使って自然算術式を処理する例を「ungetcってどう使う?」に書いてある。興味あるかたは参考にされたい。

再帰構造の回避〜ディレクトリの再帰ファイルリスト

また、スタックは再帰構造(これも入れ子だ)を処理できるのは当然である。一般に「ディレクトリ→ファイル構造」を処理するのに再帰を使うのは御承知のことと思う。が、再帰が「深すぎて」トラブルが起きる時には(懐かしのMS-DOS時代)、再帰構造をスタックに直して処理するのが普通だった。まず、再帰で書いてみよう。

/* 引数はディレクトリ名(未オープンのフルパス)*/
void chaseDirectory( char *dirc ) 
{
    struct dirent *ent;
    struct stat stat;
    DIR *dir;
    char buff[NAME_MAX+1];  /* フルパス名を作る */

    dir = opendir( dirc );
    if( dir == NULL ) {
        fatal( "cannot open directory %s", dirc );
    }
    while( (ent = readdir( dir )) ) {
        /* . と .. は取り扱わない */
        if( strcmp( ent->d_name, "." ) == 0 
            || strcmp( ent->d_name, ".." ) == 0 ) {
             continue;
        }
        sprintf( buff, "%s/%s", dirc, ent->d_name ); 
        if( lstat( buff, &stat ) == -1 ) {
            fatal( "cannot get stat %s", buff );
        }
        if( stat.st_mode & S_IFDIR ) {  /* ディレクトリ判定 */
            chaseDirectory( buff );    /* 再帰 */
        } else {                       /* 非ディレクトリ */
            printf( "FILE: %s\n", buff );
        }
   }
   closedir( dir );
}

ひょっとしてこれは、同時にオープンできるファイルハンドル数を越えるかも知れない。つまり、再帰の深みに入って行くにつれて、現在開いているディレクトリの数がどんどんと増えて行くのである(もちろん回避手段として、あらかじめ配列にディレクトリだけを保存しておく手がある)。これで再帰せずに処理するプログラムは次の通りである。

void pushSubdir( char *dirc ) 
{
    struct dirent *ent;
    struct stat stat;
    DIR *dir;
    char buff[NAME_MAX+1];  /* フルパス名を作る */

    dir = opendir( dirc );
    if( dir == NULL ) {
        fatal( "cannot open directory %s\n", dirc );
    }
    while( (ent = readdir( dir )) ) {
        /* . と .. は取り扱わない */
        if( strcmp( ent->d_name, "." ) == 0 
            || strcmp( ent->d_name, ".." ) == 0 ) {
             continue;
        }
        sprintf( buff, "%s/%s", dirc, ent->d_name ); 
        if( lstat( buff, &stat ) == -1 ) {
            fatal( "cannot get stat %s\n", buff );
        }
        if( stat.st_mode & S_IFDIR ) {  /* ディレクトリ判定 */
            /* 一旦置いておくので、文字列の複製が必要 */
            push( (char *)strdup( buff ) );  /* PUSH */
        } else {                       /* 非ディレクトリ */
            printf( "FILE: %s\n", buff );
        }
   }
   closedir( dir );
}

void chaseDirectory( char *dirc ) 
{
    char *at;

    push( dirc );       /* 最初の出発点を push  */
    while( ! isEmpty() ) {  /* このループですべて処理されることを確認! */
        at = pop();    /* 1つづつ pop して処理 */
        pushSubdir( at );  /* この中で push がなされる */
    }
}

勿論、再帰とスタックでは、表示順は違うが、それでもすべてのファイルを表示することには違いがない。このように、スタックを使えば再帰を普通のループに直すことができるのである。ということは、COBOL だってクィックソートを実現できないわけではないのである(恐ろしい...)。

このように偉大なスタックについて、御理解が頂けたのではないかと思う。実にスタックこそは、理解すればするほど、応用の広い手法なのである。ぜひ使いなれて欲しい。



copyright by K.Sugiura, 1996-2006