目標
- スタック、キューなどのデータ構造の機能を理解することができる。
- スタックやキューなどのデータ構造を配列を使って実現することできる。
- 対象となるデータをスタックやキューなどのデータ構造を使って利用することができる。
予習・復習
以下のスライドを利用して、予習と復習をしよう。復習では、自分の理解度を確認するために、実際にプログラムを作成し、意図する結果が得られるか確認しよう。本日の講義・演習予定
- スタック
- 逆ポーランド記法
- キュー
- リングバッファ
- 演習問題
- 提出課題
#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("-+-------"); }
記 法 | 例 | 説 明 |
中置記法(ポーランド記法) | 2+3 | 演算子を数値の中に配置する |
後置記法(逆ポーランド記法) | 23+ | 演算子を数値の後に配置する |
前置記法 | +23 | 演算子を前に数値の前に配置する |
#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; }
#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
#include "mystack.h" ・・・
#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"); }
#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]); } }
#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) { /*---------------- ここを埋める ------------------*/ }
今週の確認テスト テスト(PDF)
#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; }