第1週 スタックとキューと配列
INDEX

目標

  • スタック、キューなどのデータ構造の機能を理解することができる。
  • スタックやキューなどのデータ構造を配列を使って実現することできる。
  • 対象となるデータをスタックやキューなどのデータ構造を使って利用することができる。

予習・復習

 以下のスライドを利用して、予習と復習をしよう。復習では、自分の理解度を確認するために、実際にプログラムを作成し、意図する結果が得られるか確認しよう。
  1. スタックとキュー

本日の講義・演習予定

  1. スタック
  2. 逆ポーランド記法
  3. キュー
  4. リングバッファ
  5. 演習問題
  6. 提出課題
内 容
  1. データ構造
  2. スタック
  3. 逆ポーランド記法
  4. キュー
  5. リングバッファ

データ構造

データ構造とは

 学内のすべての学生の中から特定の学生の情報を探し出すこと考えてみます。無作為に並んだ大量のデータの中から、氏名だけを頼りに先頭からしらみつぶしに探さなければならないとすると、その処理の負荷の大きさはどの程度になるでしょうか。一日かかっても見つけ出すことはできないかもしれません。しかし、各学生ごとに、学部(J)、学科(X)、入学年度(2019)といった情報で整理して、50音順に並べて格納しておけば、大量のデータの中から対象の学生の情報を効率よく探し出すことができます。対象となる情報をプログラムが効率良く取り出したり、追加したりできる仕組みのことをデータ構造と言います。

データ構造の種類

 プログラムで利用するデータ構造には多くの種類があります。以下に代表的なデータ構造を挙げておきます。
  1. 配列
  2. スタック
  3. キュー(待ち行列)
  4. リスト
  5. ツリー(木構造)

スタック

 スタック (Stack)とは、逐次データを追加したり取り出したりするためのデータ構造の一つです。データは下から積み上げられていき、上から取り出されていきます。後入れ先き出し(LIFO: Last In - First Out)と言って最後に格納したデータが最初に取り出される構造を指します。データをスタックに格納する操作をPUSH、スタックから取り出す操作をPOPと呼びます。この2つの基本操作だけでデータの出し入れを制御します。また、次に取り出すデータを参照する操作をPEEKと言います。

stack1
Fig1-1. スタックへのデータ追加

stack2
Fig1-2. スタックからのデータ取り出し


プログラム例

 スタック本体を配列を使って実現するプログラムを考えます。データをPOPもしくはPUSHする時には、その配列の何番目の要素が対象になるかを示す必要があります。ここでは、操作の対象となる配列の要素の位置を示す変数の名前をtopとします。このような役割を持った変数はスタックポインタとも呼ばれます。変数topの値はスタックが空の状態では0を示します。PUSH操作ではFig1-1に示すように、データが追加された後に、変数topが+1されて次のデータを格納する位置を示します。POP操作ではFig1-2に示すように、変数topが−1された後に、そのデータが取り出されます。
 配列の要素数は有限であるため、PUSH操作を続けるといつかは満杯になってしまいます。そのため、PUSH操作をする前に満杯かどうかを知る必要があります。ここでは、満杯ならば真を、そうでないなら偽を返す関数is_full()を定義して利用することにします。また、C言語では真偽値をそれぞれ整数値の0と1ので扱いますが、論理値であることを明確するために、名前trueを整数1で、名前falseをtrueの否定として定義します。さらに、int型もbool型として再定義することとします。
 スタックが空の時はPOP操作はできないため、POP操作をする前に、空ならばtrueを、そうでないならfalseを戻り値とする関数is_empty()も定義して利用することにします。
例 stack.c
#include <stdio.h>
#include <stdlib.h>
#define true 1		//真
#define false (!true)	//偽	
#define STACKSIZE 10

//typedef int bool;		//int型をbool型として再定義 
#define bool int   //boolをtypedefできない場合

/* プロトタイプ宣言 */
bool push(int data);	//追加
int pop(void);			//取出し
int peek(void);			//参照
bool is_full(void);		//満杯か?
bool is_empty(void);	//空か?
void print_stack(void);	//スタックの表示

/* スタック */
int stack[STACKSIZE];		//スタック本体
int top=0;

/* 追加 */
bool push(int data)
{
	if(is_full())	return false;	//スタックが満杯なら
	stack[top] = data;
	top++;
	return true;
}

/* 取出し */
int pop(void)
{
	if(is_empty()){	//スタックが空なら
		fprintf(stderr,"Error: stack is empty.");
		return -1;
	}
	top--;
	return stack[top];
}

/* 最上位要素の確認 */
int peek(void)
{ 
	if(is_empty()){	//スタックが空なら
		fprintf(stderr,"Error: stack is empty.");
		return -1;
	}
	else {
		return stack[top-1];
	}
}

/** 満杯? */
bool is_full(void)
{
	return top==STACKSIZE;
}
/** 空? */
bool is_empty(void)
{
	return top==0;
}

/** スタックの表示 */
void print_stack(void)
{
	int i=top-1;

	puts(" ");
	while(i>=0){
		printf("%d| %d\n",i,stack[i]);
		i--;
	}
	puts("-+-------");
}
[演習] 上記のプログラム例のスタックの働きを確認するためのmain関数を追加しなさい。

逆ポーランド記法

逆ポーランド記法とは

 普段、私たちが利用する数式は、筆算にしても電卓を利用する場合にしても、数値と数値の間に+や-などの演算子を配置した形式をしています。この記述法のことを中置記法(ポーランド記法)と呼びます。しかし、コンピュータの世界では演算の対象となる数値の後に演算子を配置する方法が利用されることがあります。これを逆ポーランド記法と言います。例えば、
 2+3
という計算ならば、逆ポーランド記法では
 23+
となります。また、
 (6+2)÷ ((5−3)× 2)
ならば、
 62+53−2×÷ と記述できます。慣れていないので、面倒な書き方だなぁと思うかもしれません。しかし、言葉で置き換えてみると「6と2を足した結果を、5から3を引いて2をかけた結果で割る」となり、意外と自然な記述であることに気がつくかもしれません。さらに、電卓を使って計算してみることを考えてみてください。もし、逆ポーランド記法で入力できれば、カッコも使わず、面倒なメモリー計算なしで結果が求められます。(実際に逆ポーランド記法で入力できる電卓も存在します。)

数式の記法
 記 法  例  説 明 
中置記法(ポーランド記法) 2+3 演算子を数値の中に配置する
後置記法(逆ポーランド記法) 23+ 演算子を数値の後に配置する
前置記法  +23 演算子を前に数値の前に配置する

プログラム例

 逆ポーランド記法を使った計算は、スタックを使うことで簡単に実現することができます。以下にその手順とプログラムの例を示します。ただし、プログラムに空欄がありそのままでは実行できません。次の手順を参考にしてプログラムを完成させてください。
rpn
Fig1-3.スタックを使った逆ポーランド記法
  1. 逆ポーランド記法で入力した文字列から1文字を読み込み
  2. 数字ならば、scanfで整数としてスタックへPUSHする
  3. 空白ならば、1)に戻る(区切り文字)
  4. 記号{+,-,/,*}ならば、スタックから2つの整数をPOPして演算する。さらに演算結果をスタックへPUSHする
  5. 改行文字(\n)ならば、スタックから演算結果をPOPして、それを表示する。
  6. 上記以外の文字ならば、エラー表示してスタックポインタを初期化する。
例 rpn.c
#include <stdio.h>
#include <ctype.h>
#define true 1		//真
#define false (!true)	//偽	
#define STACKSIZE 30

typedef int bool;

bool is_empty(void);
bool is_full(void);
void push(int data);
int pop(void);

int stack[STACKSIZE];
int sp=0;	//書き込み位置

void push(int data)
{
	if(is_full()){
		fprintf(stderr,"Error: stack overflow.\n");
		sp = 0;
	}
	stack[sp++] = data;
}
int pop(void)
{
	if(is_empty()){
		fprintf(stderr,"Error: stack is empty.\n");
		sp = 0;	
	}
	return stack[--sp];
}

bool is_empty(void){ return sp==0; }
bool is_full(void){ return sp==STACKSIZE; }

int main(void)
{
	int a,b,c,x;

	while((c=getchar()) != EOF){		//CTRL+Z/CRTL+Dが入力されるまで
		if (isdigit(c)) {		//先頭文字が10進数字ならば
			ungetc(c,stdin);	//標準入力へ戻し
			scanf("%d", &x); 	//xへ格納、スペースで区切れる
			[[空欄ア]]			//値をスタックへ
		}
		else {				//数字ではなく(記号ならば)
			switch (c) {
				case '+':
					b = [[空欄イ]];	//値の取り出し
					a = pop();
					[[空欄エ]];	//結果の格納
					break;
				case '-':
					b = pop();
					a = [[空欄オ]];
					[[空欄カ]];
					break;
				case '*':
					b = pop();
					a = pop();
					[[空欄キ]]
					break;
				case '/':
					b = [[空欄ク]];
					a = [[空欄ケ]];
					[[空欄コ]];
					break;
				case ' ':
					break;
				case '\n':
					if(!is_empty()) printf("answer: %d\n",[[空欄サ]]);
					break;
				default:
					fprintf(stderr,"unknown character\n");
					sp=0;
					break;
			}
		}
	}

	return 0;
}
関数int getchar(void); 関数ungetc(int c, FILE *stream)


[補]論理値を扱う
 C言語の規格C99以降では論理値を扱うための関数stdboolが標準で用意されています。このライブラリでは、論理値扱うための型boolとその真偽の値をそれぞれtruefalseとして定義されています。
 MS Visual Studio では、2013以降のバージョンでstdbool.hが利用可能です。以下に、プリプロセッサディレクティブを利用して、Visual Studioの複数のバージョンとApple OSXで共通で利用可能なヘッダーファイルの例を示します。
例 mystack.h
#include <stdio.h>
#include <stdlib.h>

#if _MSC_VER >= 1800 //VS2013以降C99
	#include <stdbool.h>	//論理値
#elif __APPLE__		//OSX
	#include <stdbool.h>
#else
	#define true 1
	#define false (!true)
	typedef int bool;
#endif

上記のヘッダファイルはそれを利用したいソースコードファイルと同じディレクトリに配置して、以下のようにソースコードに記述することでbool型のtrueとfalseを利用できるようになります。
例 sampel_stack.c
#include "mystack.h"

・・・


キュー

キュー

 買い物の精算をする時には、レジの最後尾に並び、先頭の人から精算を済ましていくの待ちます。このような、列の後ろへデータを追加して、列の前からデータを取り出すデータ構造をキュー(queue)と呼びます。キューは先入れ先出しFIFO(First-In First-Out)もしくは、「待ち行列」とも呼ばれます。
 配列を利用したキューは下図のように、データを書き込む位置と取り出す位置を示す2つ変数rearとfrontを組み合わせることで実現することができます。キューにデータを追加することをenqueue、取り出すことをdequeueと言います。enqueueでは、変数rearが示す位置にデータを格納し、その値を+1することで、次の書き込み位置に移動させます。dequeueでは、変数frontが示す位置のデータを取り出し、その値を+1することで次に取り出すデータの位置へ移動させます。
queue
Fig.1-4 キュー


プログラム例

 配列を使って、文字を格納するためのキューを実現したプログラム例です。ただし、プログラムには空欄がありそのままでは実行できません。以下の各ヒントを参考にして空欄を埋めて正しい結果が得られるようにしてください。
  1. 空欄ア: 書き込み位置は変数rearが示す。書き込み後、変数rearは次の書き込み位置を示す。
  2. 空欄イ: 読み出し位置は変数frontが示す。読み出し後、変数frontは次の読み出し位置を示す。
  3. 空欄ウ: 変数rearと変数frontの値が...ならばキューは空を示していることになる。
  4. 空欄エ: 変数rearの値がキューのサイズQUESIZE...ならば書き込みすることはできない。
例 queue.c
#include <stdio.h>
#include <stdlib.h>
#define true 1		//真
#define false !true	//偽
#define QUESIZE 10	//キューのサイズ

typedef int bool;	//論理型

bool enqueue(char data);
char dequeue(void);
char peek(void);
bool is_empty(void);
bool is_full(void);
void print_queue(void);

char queue[QUESIZE];	//キュー
int rear=0,front=0;		//書き込み位置、読み出し位置

int main(void)
{
	enqueue('A');
	print_queue();
	enqueue('B');
	print_queue();
	enqueue('C');
	print_queue();

	dequeue();
	print_queue();
	dequeue();
	print_queue();
	dequeue();
	print_queue();
	dequeue();
	print_queue();

	return 0;
}

/** データを挿入する */
bool enqueue(char data)
{
    if(is_full()) return false;
    [[空欄ア]];
    return true;
}

/** データを取り出す */
char dequeue(void)
{
	char tmp;
	
    if(is_empty()){
        fprintf(stderr,"Error: queue is empty.\n");
        return -1;
    }
    [[空欄イ]];
    return tmp;
}

/** 先頭要素の参照 */
char peek(void)
{
	return queue[front];
}

/** キューは空か? */
bool is_empty(void)
{
    [[空欄ウ]]
}

/** キューは満杯か?*/
bool is_full(void)
{
	[[空欄エ]]
}

/* キューの表示 */
void print_queue(void)
{
    int i;
    for(i=front; i<rear; i++){
          printf("%c ",queue[i]);
    }
    printf("\n");
}
[解答]
ア. queue[rear]; rear++;
イ. tmp = queue[front]; front++;
ウ. front == rear;
エ. rear == QUESIZE;


リングバッファ

 配列を使ったキューは、データを追加していくとすぐに配列が満杯になり使えなくなってしまいます。データを取り出すことで配列の前部分が空いてきますが、この空き部分を再利用するためには格納されているデータ全て前へ移動しなければなりません。データ量によっては大変多くの処理時間を必要とします。
 この問題を解決するために、配列の先頭と最後尾をつないで環状にしてみます。すると、データを移動することなく有効利用出来るキューが実現します。これをリングバッファ(ring buffer)と呼びます。ただし、空の状態の時と満杯の状態の時とでデータの書き込み位置と取り出し位置が同じになってしまうため、新たにデータ数を格納する変数を別途用意します。これを利用することで、空なのかそうでないかが判断できるようになります。

ringbuffer
Fig.リングバッファ

プログラム例

 配列を使って、整数を格納するためのリングバッファを実現したプログラム例です。ただし、プログラムには空欄がありそのままでは実行できません。以下の各説明を参考にして空欄を埋めて正しい結果が得られるようにしてください。
  1. バッファが満杯でなければ、変数rearが示す書き込み位置にデータを格納する。書き込み後、書き込み位置rearの値を次の書き込み位置に移動する。ただし、その値がバッファの最大サイズMAXSIZEとなった場合は、書き込み位置を0にしなければならない。さらにデータ数を示す変数numの値を1増やす。
  2. バッファが空でなければ、変数frontが示す読み出し位置のデータを戻りとする。読み出し後、読み出し位置frontの値を次の読み出し位置へ移動する。ただし、その値がバッファの最大サイズMAXSIZEとなった場合は、読み出し位置を0にしなければならない。さらにデータ数を示す変数numの値を1減らす。
例 ringbuffer.c
#include <stdio.h>
#include <ctype.h>
#define true 1		//真
#define false (!true)		//偽	
#define MAXSIZE 7

typedef int bool;

bool enqueue(int data);
int dequeue(void);
int peek(void);
bool is_empty(void);
bool is_full(void);
int get_size(void);

int buff[MAXSIZE];
int front = 0;	//読み出し位置
int rear = 0;	//書き込み位置
int num = 0;	//格納したデータ数

/* 追加 */
bool enqueue(int data)
{
	if(is_max()){	//満杯
		fprintf(stderr,"Error: buffer is full.\n");
		return false;
	}
	else {
		/*---------------------------
			ここを埋める
		-----------------------------*/
		return true;
	}
}

/* 取り出し */
int dequeue(void)
{
	int index;

	if(is_empty()){	//空ならば
		fprintf(stderr,"Error: buffer is full.\n");
		return  -1;
	}
	else {
		/*---------------------------
			ここを埋める
		-----------------------------*/
	}
}
bool is_empty(void){ return num==0; }
bool is_full(void){ return num==MAXSIZE; }

/* 先頭要素の参照 */
int peek(void)
{
	if(is_empty()){	//空ならば
		fprintf(stderr,"Error: buffer is full.\n");
		return  -1;
	}
	else {
		return buff[front];
	}
}

/* データ数の取得 */
int get_size(void)
{
	return num;
}	

/* リングバッファの表示 */
void print_queue(void)
{
	int i;
	for(i=num; i>=0; i--){
		printf("%d ",buff[i]);
	}
}
[演習] リングバッファのプログラムに複数のデータを追加したり取り出したりするmain関数を追加して、正しい実行結果が得られることを確認しなさい。


expand_lessBack to TOP

演習問題

  1. スタックを利用して文字列を入力してその文字列を逆順に表示するプログラムです。正しい実行結果が得られるように、空欄を埋めて完成させなさい。
  2. 例 cstack.c
    #include <stdio.h>
    #include <stdlib.h>
    #define true 1		//真
    #define false (!true)		//偽	
    #define STACKSIZE 10
    
    typedef int bool;
    
    /* プロトタイプ宣言 */
    bool push(char data);
    char pop(void);
    char peek(void);
    bool is_full(void);
    bool is_empty(void);
    void print_stack(void);
    
    /* スタック */
    char stack[STACKSIZE];
    int top=0;
    
    int main(void)
    {
    	char ch;
    
    	while((ch=getchar()) != '\n'){	//1文字ずつ読み込み
    		if(!push(ch)) break;
    	}
    	print_stack();
    
    	while(!is_empty()){
    		printf("%c",pop());
    	}
    	printf("\n");
    
    	return 0;
    }
    
    /* 追加 */
    bool push(char data)
    {
    	/*----------------
    	   ここを埋める
    	------------------*/
    }
    
    /* 取出し */
    char pop(void)
    {
    	/*----------------
    	   ここを埋める
    	------------------*/
    }
    
    /* 最上位要素の確認 */
    char peek(void)
    { 
    	/*----------------
    	   ここを埋める
    	------------------*/
    }
    
    /** 満杯? */
    bool is_full(void)
    {
    	/*----------------
    	   ここを埋める
    	------------------*/
    }
    /** 空? */
    bool is_empty(void)
    {
    	/*----------------
    	   ここを埋める
    	------------------*/
    }
    
    /** スタックの表示 */
    void print_stack(void)
    {
    	/*----------------
    	   ここを埋める
    	------------------*/
    }
    

  3. 以下の配列データをスタックを利用して逆順に並べ換えるプログラムinverse.cを作成しなさい。
    data[5]={1,2,3,4,5}

  4. 逆ポーランド記法を使ったプログラム例rpn.cを小数点数にも対応できるように修正しなさい。

  5. リングバッファについて以下の設問に答えなさい。
    1. リングバッファにすべてのバッファの要素を値0で初期化する関数void clear(void)を追加しなさい。
    2. リングバッファに関数POP()と関数PUSH()を追加してスタックとしても利用できるようにしなさい。
    3. データを追加する際に同じデータが既に存在していないか調べて、なければ追加可能なリングバッファを実現しなさい。

演習問題解答

OPEN ANSWER
  1. 回答例 string_reverse.c
  2. code/1/string_reverse.c

  3. 回答例 inverse.c
  4. code/1/inverse.c

  5. 回答例 rpn_float.c
  6. code/1/rpn_float.c

  7. 回答例 ringbuffer_stack.c
  8. code/1/ringbuffer_stack.c

expand_lessBack to TOP

今週の確認テスト テスト(PDF)

本日の提出課題

次のプログラムは1以上の10進整数を2進数に変換表示するプログラムkadai3-1.cの一部です。スタックを操作するための関数pushと関数pop、10進整数を渡して2進表示する関数binaryを追加してプログラムを完成させなさい。ただし、関数binaryにおいては下図に示すように関数pushと関数popを呼び出すことで10進2進数変換を実現すること。再帰処理は利用できないものします。
#include <stdio.h>
#define MAX 100

int stack[MAX];
int top = 0;

int push(int x);
int pop(void);
void binary(int x);

int main(void)
{
	printf("15d = ");
	binary(15);
	printf("64d = ");
	binary(64);
	printf("2019d = ");
	binary(2019);

	return 0;
}

[考え方]  10進整数を2進数へ変換するための方法の一つは、10進数を2で除算して商と剰余を求めます。その商をさらに2で除算してを繰り返して商が0になるまで続けます。その結果得られた剰余を、最後から順に並べることで2進数を求めることができます。これをプログラムで実現する場合、剰余を処理順とは逆の順序で表示する必要があリます。そのため、ここでは剰余を処理順にスタックにpushした上で、処理後に全てpopすることで逆順表示を実現します。 binary_stack


  • [提出方法]
    • 電子メールの添付ファイルとして提出してください。宛先は指定のアドレスです。
    • 表題は、課題1とします。
    • メール本文には、プログラムを完成させるまでに苦労した点などを記述すること。
    • 添付ファイルは下記の2点です。
    • 1) ソースコード・ファイル kadai3-1.c
      2) 実行結果画面(ウインドウのみ)のハードコピーの画像ファイル kadai3-1.jpg

  • [実行結果画面のハードコピーの取り方]
    1. [メニュー]→[アクセサリ]→Snipping Toolを起動する。ただし、Snipping Toolのウインドウが実行画面に重ならないように、必要に応じてウインドウを移動すること。
    2. タイトルバーを含めた実行結果画面をマウスドラッグして選択して、キャプチャする。
    3. メニューから「ファイル」→「名前をつけて保存」を選択する。ファイルの種類にはJPG形式を選択して、保存先フォルダを選び、ファイル名を付けて「保存」する。
    ※Windows10(creators update以降)では、Windows+Shift+S キーを押して、キャプチャしたい矩形領域をドラッグして、クリップボードにコピーします。アプリ「切り取り&スケッチ」が起動したら、画像をJPG形式で保存します。

  • [評価について]
  • プログラムの内容の評価とは別に以下の要件を満たすことを評価の前提とする。
    1. ソースコードがC言語で記述されていること。
    2. 提出されたソースコードファイルから生成される実行形式ファイルを実行した結果、所定の出力結果が得られること。
    3. 提出されたソースコードは、インデントや適当な改行が施された見やすい状態であること。
    4. 変数の利用目的、処理や判定の意味など必要と思われる解説を簡潔にコメント文として付けること。
    5. 提出された実行結果の画面コピーは、コマンドプロンプトのウインドウのみとすること。

  • [提出期限]
  • 2019年 9月25日(水)午後2時まで。