第４回
基本データ構造１
配列、スタック、キュー と その操作
４－１．配列とその操作
配列型
同じ型の変数を並べたもの。
配列にする型は、基本型・配列型・構造体・ポインタ いずれでもよい。
要素の並べ方を「次元」という。
・・・
１次元配列
（直線状）
２次元配列
（平面状）
３次元配列
（立体状）
・・・
a[5]
a[4][5]
a[3][4][5]
a[2][3][4][5]・・・
表４-１ 配列の次元
４－２．スタックとその操作
４－２-１．スタック（stack）
データの 追加、取り出し ともに 最後（最近）のデータで行なう。
最初に追加したものを最後に取り出すので、
FILO（First In Last Out）と表現したり、
最後に追加したものを最初に取り出すので、
LIFO（Last In First Out）と表現したりする。
日常でのイメージ
スタック
（作業の一時退避場所）
４－２-２．スタックを実現するデータ構造
スタックポインタ ： 最後に積まれているデータの場所を指し示すポインタ
スタックエリア ： スタックとして使用する空間（メモリの場所）
レポート レポート レポート レポート レポート
調べ物
調べ物
調べ物
メール
D
C
B
A
D
C
B
A
レポートを書く
調べ物をする
メールを読む
電話をする
わからないことに遭遇
メール着信
電話着信
４－２-３．スタックへの追加
スタックへデータを追加する操作は、
「積む」
「PUSH する」
「退避する」「載せる」と表現されることもある。
スタックに D を追加する操作
４－２-４．スタックからの取り出し
スタックからデータを取り出す操作は、
「降ろす」
「POP する」
「復帰する」と表現されることもある。
スタックから取り出す操作
C
B
A
スタック
ポインタ
SP
元のデータ
C
B
A
SP
SP を
これから積む場所を
指すように更新する
D
C
B
A
SP
SP の場所へ D を入れる
D
C
B
A
スタック
ポインタ
SP
元のデータ
D
C
B
A
SP
SP の場所から
データを取り出す
C
B
A
SP
SP を
次に取り出す場所へ更新する
D
４－３．キューとその操作
４－３-１．キュー（queue）
データの 追加は 最後（最近）
、取り出しは先頭（最古）のデータで行なう。
最初に追加したものを最初に取り出すので、
FIFO（First In First Out）と表現したり、
何かの順番を待って並んでいる列のようなので
待ち行列 と表現したりする。
日常でのイメージ
４－３-２．キューを実現するデータ構造
A
B
C
D
E
F
G
rp はデータを取り出すごとに右に移動する。wp はデータを追加するごとに右に移動する。
データがない場合（空の場合）
、rp と wp は同じ場所を指し、キューは、下図のようになる。
D
C
B
A
D
C
B
A
レジ
列の最後尾に並ぶ
列の先頭からレジにつく
読み出し
ポインタ
rp
書き込み
ポインタ
wp
データを取り出す
位置を示す
データを追加する
位置を示す
rp wp
４－３-３．リングバッファ
キューバッファとして確保した領域で、格納する場所が最後の位置まで来たとき、
次の格納場所をキューバッファの先頭にすることで、効率よく使用できる。
このように、バッファの末尾と先頭をつないで連続させたものを「リングバッファ」という。
４－３-４．キューへの追加
キューへデータを追加する操作は、
「enqueue（エンキュー）
」と表現されることもある。
キューに D を追加する操作
0
１
ｎ
n-1
D
E
F
G
C
B
A
rp
wp
C
B
A
rp
wp
D
C
B
A
rp
wp
D
C
B
A
rp
wp
リングバッファ
リングバッファによるキュー
４－３-５．キューからの取り出し
キューからデータを取り出す操作は、「dequeue（デキュー）」と表現されることもある。
キューから取り出す操作
C
B
A
rp
wp
元のデータ
C
B
A
rp
wp
rp の場所からデータを取り出す
A
rp を次の場所へ更新する
C
B
rp
wp
４－４．Appendix
４－４-１．配列操作のプログラム「array.c」
#include <stdio.h>
#define DATA_SIZE 10 /* データを格納する配列のサイズ */ #define LAST_DATA (DATA_SIZE - 1) /* 配列の最後 */
unsigned char g_array[DATA_SIZE+1]; /* データを格納する配列の宣言 */
/* +1 は、この例のプログラムで終端記号を入れるために追加 */ void init( void );
void insert( int insert_point , unsigned char data ); void delete( int delete_point );
int main( void ) {
printf( " 0123456789\n" ); init(); printf( "init %s\n" , g_array );
insert( 3 , 'A' ); printf( "insert 3,'A' %s\n" , g_array ); insert( 4 , 'B' ); printf( "insert 4,'B' %s\n" , g_array ); insert( 5 , 'C' ); printf( "insert 5,'C' %s\n" , g_array ); insert( 4 , 'D' ); printf( "insert 4,'D' %s\n" , g_array ); insert( 6 , 'E' ); printf( "insert 6,'E' %s\n" , g_array ); delete( 5 ); printf( "delete 5 %s\n" , g_array ); delete( 6 ); printf( "delete 6 %s\n" , g_array ); insert( 6 , 'F' ); printf( "insert 6,'F' %s\n" , g_array ); delete( 2 ); printf( "delete 2 %s\n" , g_array ); insert( 7 , 'G' ); printf( "insert 7,'G' %s\n" , g_array ); insert( 7 , 'H' ); printf( "insert 7,'H' %s\n" , g_array ); insert( 7 , 'I' ); printf( "insert 7,'I' %s\n" , g_array );
return ( 0 ); }
void insert( int insert_point , unsigned char data ) {
int i;
for ( i = LAST_DATA ; i > insert_point ; i-- ) {
g_array[i] = g_array[i-1]; /* データの移動 */ }
g_array[insert_point] = data; /* データ挿入 */ }
void delete( int delete_point ) {
int i;
for ( i = delete_point ; i < LAST_DATA ; i++ ) {
g_array[i] = g_array[i+1]; /* データの移動 */ }
}
４－４-２．スタック操作のプログラム「stack.c」
#include <stdio.h> #include <stdlib.h> #define STACK_SIZE 10 /* スタックのサイズ */ struct stack { /* スタック管理の構造体定義 */ unsigned char *sp; /* スタックポインタ */ int remain; /* スタックの残量 */ };struct stack stack_memory; /* スタック管理の構造体宣言 */
unsigned char *g_stack_limit; /* この例のプログラムでスタックを表示するために追加 */ void push( unsigned char data );
unsigned char pop( void ); void init( void );
int main( void ) {
unsigned char data;
printf( " 0123456789\n" ); init(); printf( "init %s\n" , g_stack_limit );
push( 'A' ); printf( "push 'A' %s\n" , g_stack_limit ); push( 'B' ); printf( "push 'B' %s\n" , g_stack_limit ); push( 'C' ); printf( "push 'C' %s\n" , g_stack_limit ); push( 'D' ); printf( "push 'D' %s\n" , g_stack_limit );
data = pop(); printf( "pop %s pop data=%c\n" , g_stack_limit , data ); data = pop(); printf( "pop %s pop data=%c\n" , g_stack_limit , data ); push( 'E' ); printf( "push 'E' %s\n" , g_stack_limit );
data = pop(); printf( "pop %s pop data=%c\n" , g_stack_limit , data );
return ( 0 ); }
void push( unsigned char data ) { if ( stack_memory.remain > 0 ) { /* スタック残量があれば */ stack_memory.sp--; /* スタックポインタ更新 */ *(stack_memory.sp) = data; /* データを追加 */ stack_memory.remain--; /* スタック残量を減らす */ } }
unsigned char pop( void ) {
unsigned char data;
if ( stack_memory.remain < STACK_SIZE ) { /* スタックの底でなければ */ data = *(stack_memory.sp); /* データを取り出す */ *(stack_memory.sp) = '.'; /* この例のプログラムでデータの取り出しを明示するために追加 */ stack_memory.sp++; /* スタックポインタ更新 */ stack_memory.remain++; /* スタック残量を増やす */ } else { data = '\0'; /* スタックが空なら 返すデータを空にする */ } return ( data ); }
void init( void ) /* スタックメモリの確保と初期設定 */ {
unsigned char *tmp;
stack_memory.sp = malloc( sizeof(unsigned char) * STACK_SIZE + 1 ); /* スタックメモリの確保 */
４－４-３．キュー操作のプログラム「queue.c」
#include <stdio.h> #include <stdlib.h> #define QUEUE_SIZE 10 /* キューのサイズ */ struct queue { unsigned char *rp; /* 読み出しポインタ */ unsigned char *wp; /* 書き込みポインタ */ unsigned char *top; /* キューバッファの先頭 */ unsigned char *end; /* キューバッファの末尾 */ int remain; /* キューの残量 */ };struct queue queue_buffer; /* キュー管理の構造体宣言 */ void enqueue( unsigned char data );
unsigned char dequeue( void ); void init( void );
int main( void ) {
unsigned char data;
printf( " 0123456789\n" );
init(); printf( "init %s\n" , queue_buffer.top );
enqueue( 'A' ); printf( "enqueue 'A' %s\n" , queue_buffer.top ); enqueue( 'B' ); printf( "enqueue 'B' %s\n" , queue_buffer.top ); enqueue( 'C' ); printf( "enqueue 'C' %s\n" , queue_buffer.top ); enqueue( 'D' ); printf( "enqueue 'D' %s\n" , queue_buffer.top );
data = dequeue(); printf( "dequeue %s dequeue data=%c\n" , queue_buffer.top , data ); data = dequeue(); printf( "dequeue %s dequeue data=%c\n" , queue_buffer.top , data ); enqueue( 'E' ); printf( "enqueue 'E' %s\n" , queue_buffer.top );
enqueue( 'F' ); printf( "enqueue 'F' %s\n" , queue_buffer.top ); enqueue( 'G' ); printf( "enqueue 'G' %s\n" , queue_buffer.top ); enqueue( 'H' ); printf( "enqueue 'H' %s\n" , queue_buffer.top );
data = dequeue(); printf( "dequeue %s dequeue data=%c\n" , queue_buffer.top , data ); data = dequeue(); printf( "dequeue %s dequeue data=%c\n" , queue_buffer.top , data ); tmp = g_stack_limit = stack_memory.sp; /* この例のプログラムでスタックの内容を初期化するために追加 */ stack_memory.remain = STACK_SIZE; /* スタックの残量初期化 */ stack_memory.sp += STACK_SIZE; /* スタックポインタ初期化 */ while ( tmp != stack_memory.sp ) { /* この例のプログラムでスタックの内容を初期化 */ *tmp++ = '.'; /* すべての領域を'.'で埋める */ } *tmp = '\0'; /* 最後を文字列終端記号に設定する */ }
void enqueue( unsigned char data ) { if ( queue_buffer.remain > 0 ) { /* キュー残量があれば */ *(queue_buffer.wp) = data; /* データを追加 */ if ( queue_buffer.wp == queue_buffer.end ) { /* 書き込みポインタ更新 */ queue_buffer.wp = queue_buffer.top; } else { queue_buffer.wp++; } queue_buffer.remain--; /* キュー残量を減らす */ } }
unsigned char dequeue( void ) {
unsigned char data;
if ( queue_buffer.rp != queue_buffer.wp ) { /* キューが空でなければ */ data = *(queue_buffer.rp); /* データを取り出す */ *(queue_buffer.rp) = '.'; /* この例のプログラムでデータの取り出しを明示するために追加 */ if ( queue_buffer.rp == queue_buffer.end ) { /* 読み出しポインタ更新 */ queue_buffer.rp = queue_buffer.top; } else { queue_buffer.rp++; } queue_buffer.remain++; /* キュー残量を増やす */ } else { data = '\0'; /* キューが空なら 返すデータを空にする */ } return ( data ); }
void init( void ) /* キューバッファの確保と初期設定 */ {
unsigned char *tmp;
queue_buffer.top = malloc( sizeof(unsigned char) * QUEUE_SIZE + 1 );
/* キューバッファの確保 */
/* +1 は、この例のプログラムで終端記号を入れるために追加 */ queue_buffer.end = queue_buffer.top + (QUEUE_SIZE -1);
/* キュー末尾ポインタ設定 */ queue_buffer.remain = QUEUE_SIZE; /* キューの残量初期化 */ queue_buffer.rp = queue_buffer.top; /* 読み出しポインタ初期化 */ queue_buffer.wp = queue_buffer.top; /* 書き込みポインタ初期化 */ tmp = queue_buffer.top; while ( tmp != queue_buffer.end ) { /* この例のプログラムでスタックの内容を初期化 */ *tmp++ = '.'; /* すべての領域を'.'で埋める */ } *tmp++ = '.'; *tmp = '\0'; /* 最後を文字列終端記号に設定する */ }
