ホーム » スタッフ » 斉藤徹 » リストを用いたスタックとキュー

2011年7月
« 6月   8月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

リストを用いたスタックとキュー

リスト操作の演習中だけど、残り授業もあと(今日を入れて)あと2回ということで、 リスト関連のネタが未消化にならないように、スタックとキューについて説明。

スタック

配列を用いた、LIFO(Last In First Out)=スタックであれば、一般的に 以下のようなコードになる。

int stack[ 100 ] ;
int sp = 0 ;
void push( int x ) {
stack[ sp++ ] = x ;
}
int pop() {
return stack[ --sp ] ;
}

しかし、この方法では、配列サイズ以上のデータは保存できない。 これをリストを使うことでサイズを気にしないスタックを実現できる。

struct List* stack = NULL ;
void push( int x ) {
stack = cons( x , stack ) ;
}
int pop() {
int ans = stack->data ;
struct List* del = stack ;
stack = stack->next ;
free( del ) ;
return ans ;
}

キュー

待ち行列(Queue)は、FIFO(First In First Out)を配列で実装する場合、 一般的には、以下のようになる。ただしエラー対策は記載していないので、要注意。

int que[ 100 ] ;
int wp = 0 ; // 書き込み用ポインタ
int rp = 0 ; // 読み出し用ポインタ
void put( int x ) {
que[ wp ] = x ;
wp = (wp + 1) % 100 ; // 循環させる
}
int get() {
int ans = que[ rp ] ;
rp = (rp + 1) % 100 ; // 循環させる
return ans ;
}

このような配列の領域を使い切ったら、先頭から再利用するような方法は、 リングバッファなどと呼ばれる。 このような待ち行列は、キー入力バッファや、プロセス待ち行列などに よく利用される。しかし、このプログラムでも、配列サイズ以上の データは保存できないので、リストを用いる。

struct List* top = NULL ;
struct List** tail = &top ;
void put( int x ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
int get() {
int ans = top->data ;
struct List* del = top ;
top = top->next ;
free( del ) ;
return ans ;
}

ただし、このプログラムは、常に1件以上データがリストに入っている場合は 問題がないが、get() を実行して、データ件数が0件になると、tail の指す先が おかしくなるので注意が必要。

また、待ち行列では、先頭ポインタと末尾ポインタの2つが必要であるが、 リスト構造の末尾のNULLを、先頭データを指すようにする循環リストと する場合も多い。特に、プロセス待ち行列を実装するときのラウンドロビン方式 などでは、末尾まで処理が及んだ次は先頭に戻って処理を行うため、 循環リストは都合がいい。