計算処理中に一時的なデータの保存として、stackとqueueがよく利用されるが、 それを配列を使って記述したり、任意の大きさにできるリストを用いて記述する。

スタック

一時的な値の記憶によく利用されるスタックは、一般的にLIFO( Last In First out )と呼ばれる。 配列を使って記述すると以下のようになるであろう。

#define STACK_SIZE 32
int stack[ STACK_SIZE ] ;
int sp = 0 ;
void push( int x ) {
stack[ sp++ ] = x ;
}
int pop() {
return stack[ --sp ] ;
}
void main() {
push( 1 ) ; push( 2 ) ; push( 3 ) ;
printf( "%d\n" , pop() ) ;
printf( "%d\n" , pop() ) ;
printf( "%d\n" , pop() ) ;
}

しかし、この中にSTACK_SIZE以上のデータは貯えられない。 同じ処理をリストを使って記述すれば、ヒープメモリを使い切るまで使うことができるだろう。

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

キュー(QUEUE)

２つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、 待ち行列(キュー)がよく利用される。 FIFO(First In First Out)

配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、 配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いる リングバッファは以下のようなコードで示される。

#define QUEUE_SIZE 32
int queue[ QUEUE_SIZE ] ;
int wp = 0 ;
int rp = 0 ;
void put( int x ) {
queue[ wp++ ] = x ;
if ( wp >= QUEUE_SIZE )
wp = 0 ;
}
int get() {
int ans = queue[ rp++ ] ;
if ( rp >= QUEUE_SIZE )
rp = 0 ;
return ans ;
}
void main() {
put( 1 ) ; put( 2 ) ; put( 3 ) ;
printf( "%d\n" , get() ) ;
printf( "%d\n" , get() ) ;
printf( "%d\n" , get() ) ;
}

このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。

そこで、このプログラムもリストを使って記述すると以下のようになる。

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

ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、 tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。

また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リスト法が使われることが多い。