目標
- スタック、キューなどのデータ構造の機能を理解することができる。
- スタックやキューなどのデータ構造を配列を使って実現することできる。
- 対象となるデータをスタックやキューなどのデータ構造を使って利用することができる。
予習・復習
以下のスライドを利用して、予習と復習をしよう。復習では、自分の理解度を確認するために、実際にプログラムを作成し、意図する結果が得られるか確認しよう。本日の講義・演習予定
- スタック
- 逆ポーランド記法
- キュー
- リングバッファ
- 演習問題
- 提出課題


#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;
}