スタックと待ち行列

Algorithms and Data Structures on C
スタックと待ち行列
Algorithms and Data Structures on C
この回の要点
• スタック
– スタックの構造
• 最後に入れたものが、最初に取り出される（LIFO）
• 日常に良くある「ちょっと置いといて・・・」の概念
– C言語の配列による実装
• スタックオーバーフロー
• スタックアンダーフロー
– 逆ポーランド記法電卓
• 待ち行列
– 待ち行列の構造
• 最初に入れたものが、最初に取り出される（FIFO）
• 日常に良くある「行列」の概念
– C言語の配列による実装
• リングバッファの利用
Algorithms and Data Structures on C
スタック（棚）
• データの挿入と削除が、リストの先頭だけ
– 生協のトレイ
• 生協の人は、置き場の一番上に新しいトレイを置く
• 使う人は、置き場の一番上のトレイを取る
• ＬＩＦＯ（Last In First Out）
置く
取る
使う人
生協の人
置き場
スタック
Algorithms and Data Structures on C
身近なスタック
• 日常生活の中にもスタックがある
– とりあえず置いといて・・・、の概念
本を読む
辞書を引く
来客対応
電話に出る
心の中の
スタック
積む
本
積む
辞書
本
積む
来客
辞書
本
取る
辞書
本
取る
本
取る
Algorithms and Data Structures on C
スタックの構造
• 箱が上に積み上がっていく構造
–
–
–
–
最初の要素→スタックの底（bottom）
最後の要素→スタックの頂上（top）
データの挿入→スタックに積む（push）
データの削除→スタックから取り出す（pop）
Push
Pop
Top
Bottom
Algorithms and Data Structures on C
スタックの利用
• 機械語のPush・Pop命令
– スタックポインタ（SP）の示すアドレスにデータを保存・読
み出し
– サブルーチンコールの戻り値の自動保存・復元
• Cの関数やＪａｖａのメソッド呼び出し
– 引数をスタックに積んで渡す
スタック
Push (FF)
・
・
・
SP
SP
SP
FF
3A
24
4
3
Pop (3A)
・
・
・
int add(int a,int b){
return a+b;
}
int main(){
int ans=add(3,4);
}
Algorithms and Data Structures on C
配列によるスタックの実現
• 最大サイズは固定（＝M）
– stack[0]がスタックの底（bottom）
– stack[M-1]がスタックの最大
– stack[sp-1]がスタックの頂上（top）
•
•
•
•
sp ：スタックポインタ
最初は sp=0
Pushするたびに sp=sp+1（但し sp=M以外）
Popするたびに sp=sp-1（但し、sp=0以外）
stack[]
sp
spは常に空の箱を指す
# # # # # # # # # # #
0 1 2 3 4
M-1
Algorithms and Data Structures on C
SimpleStack.cc
/*** 簡単なスタック ***/
#include <stdio.h>
#include <stdlib.h>
// スタック用変数
const int size=100;
int stack[size];
int sp=0;
// スタックサイズ
// スタック
// スタックポインタ
// プッシュ
void push(int n){
if(sp==size){
fprintf(stderr,"Error: stack overflow.¥n");
exit(1);
}
代入してから
spを増やす
stack[sp++]=n;
}
Algorithms and Data Structures on C
SimpleStack.cc
// ポップ
int pop(){
if(sp==0){
fprintf(stderr,"Error: stack underflow.¥n");
exit(1);
}
return stack[--sp];
}
// 表示
void print(){
printf("%d:",sp);
for(int i=0;i<sp;i++)
printf("%d ",stack[i]);
printf("¥n");
}
spを減らしてから
取り出す
Algorithms and Data Structures on C
SimpleStack.cc
// メイン
int main(void){
print();
push(1); push(2); push(3); push(4); push(5);
print();
pop(); pop();
print();
push(6); push(7); push(8);
print();
pop(); pop(); pop(); pop(); pop();
print();
pop(); pop();
print();
}
Algorithms and Data Structures on C
簡単なスタックの例（結果）
$ ./SimpleStack
0:
5:1 2 3 4 5
3:1 2 3
6:1 2 3 6 7 8
1:1
Error: stack underflow.
$
1つしか要素が入っ
ていないスタックか
ら2つの要素を
取り出そうとした
Algorithms and Data Structures on C
ヘッダファイルを使った実装
• スタックだけを実装する
– 他のソースコードから利用可能にする
• 2つのファイルに分ける
– StackInt.h
• 整数スタック型の宣言
• 関数のプロトタイプ宣言
– StackInt.cc
• 関数の実装
• 利点
– スタックを使いたいとき、その都度実装する必要がない
– オブジェクト指向的な利用法
Algorithms and Data Structures on C
StackInt.h
#ifndef __StackInt__h
#define __StackInt__h
/***
*** 整数スタック
***/
#include <stdio.h>
#include <stdlib.h>
// 整数スタック型の宣言
typedef struct {
int *stack;
// スタック
int sp;
// スタックポインタ
int size;
// 要素数
} StackInt;
続く
Algorithms and Data Structures on C
StackInt.h
第1引数にスタック
サイズを指定する
// プロトタイプ宣言
StackInt *makeStackInt(int s);
void free(StackInt *si);
void push(StackInt *si,int n);
int pop(StackInt *si);
int peek(StackInt *si);
int getSize(StackInt *si);
void print(StackInt *si);
#endif // __StackInt__h
//
//
//
//
//
//
//
スタックの生成
スタックの解放
プッシュ
ポップ
ピーク
要素数
内部の表示
第1引数に必ず
StackInt* を指定する
（どのスタックを
操作するかを指定）
Algorithms and Data Structures on C
StackInt.cc
/*** StackIntの実装 ***/
#include "StackInt.h"
// スタックの生成
StackInt *makeStackInt(int s){
StackInt *si=(StackInt*)malloc(sizeof(StackInt));
si->size=s;
si->stack=(int*)malloc(si->size*sizeof(int));
si->sp=0;
StackInt*
StackInt
スタック実体
return si;
si
stack
}
// スタックの解放
void free(StackInt *si){
free(si->stack);
free((void*)si);
}
sp
size
si->size
続く
Algorithms and Data Structures on C
StackInt.cc
// プッシュ
void push(StackInt *si,int n){
if(si->sp==si->size){
fprintf(stderr,"Error: stack overflow.¥n");
exit(1);
}
si->stack[si->sp++]=n;
}
// ポップ
int pop(StackInt *si){
if(si->sp==0){
fprintf(stderr,"Error: stack underflow.¥n");
exit(1);
}
return si->stack[--si->sp];
}
続く
Algorithms and Data Structures on C
StackInt.cc
// ピーク
int peek(StackInt *si){
if(si->sp==0){
fprintf(stderr,"Error: stack underflow.¥n");
exit(1);
}
return si->stack[si->sp-1];
}
// 要素数
int getSize(StackInt *si){
return si->sp;
}
続く
Algorithms and Data Structures on C
StackInt.cc
// 内部の表示
void print(StackInt *si){
printf("%d:",si->sp);
for(int i=0;i<si->sp;i++)
printf("%d ",si->stack[i]);
printf("¥n");
}
Algorithms and Data Structures on C
利用法
• 整数スタックを使用したいソースコード
– #include “StackInt.h”
– StackInt型とプロトタイプ関数が使用可能
• リンク
– StackInt.oをリンクする
• CygwinのbashでのMakefile
CC = g++
all:StackTest SimpleStack
StackTest:StackTest.o StackInt.o
StackTest.o:StackTest.cc StackInt.h
StackInt.o:StackInt.cc StackInt.h
SimpleStack:SimpleStack.cc
Algorithms and Data Structures on C
StackTest.cc
/*** 配列によるスタックの実装例 ***/
#include "StackInt.h"
ヘッダの読み込み
// メイン
int main(int argc,char **argv){
StackIntの生成
StackInt *si=makeStackInt(100);
print(si);
push(si,1); push(si,2); push(si,3); push(si,4); push(si,5);
print(si);
pop(si); pop(si);
第1引数に必ず
print(si);
StackInt* を指定する
push(si,6); push(si,7); push(si,8);
print(si);
pop(si); pop(si); pop(si); pop(si); pop(si);
print(si);
pop(si); pop(si);
print(si);
StackIntの破棄
free(si);
}
Algorithms and Data Structures on C
逆ポーランド記法（RPN）
• Reverse Polish Notation
• 演算子を操作対象の後に書く記法
–
–
–
–
後置記法 (Postfix Notation)
括弧( ) が不要
デミリタ（区切り文字）が必要
計算機で演算を行う場合に便利
• スタックを利用すると簡単
1+2
(1+2)*(4+6)
(1+2)*(3+4*(2-3))
通常記法
1 2 +
1 2 + 4 6 + *
1 2 + 3 4 2 3 - * + *
逆ポーランド記法
Algorithms and Data Structures on C
スタックによる逆ポーランド電卓
• 入力トークンを1つずつ読み、
– 数字ならスタックに積む
– 演算子なら、スタックから2つ取り出して計算して、その結
果をスタックに積む
1 2 + 4 6 + *
（１＋２）＊（４＋６）＝？
1
2
+
4
6
+
*
6
2
1
1
3
4
4
10
3
3
3
30
Algorithms and Data Structures on C
NRPCalc.cc
/***
*** 逆ポーランド記法電卓
***/
#include "StackFloat.h"
floatを要素とするスタック
(StackIntを参考に）
// メイン
int main(int argc,char **argv){
// 起動メッセージ
printf("*** Reverse Polish Notation Calculator ***¥n");
// スタックを準備する
StackFloat *sf=makeStackFloat(100);
続く
Algorithms and Data Structures on C
NRPCalc.cc
// 入力待ちループ
int end_flag=0;
double n1,n2;
char buf[100];
while(!end_flag){
if(scanf("%s",buf)!=1) break;
switch(buf[0]){
case '+': n2=pop(sf); n1=pop(sf); push(sf,n1+n2);
case '-': n2=pop(sf); n1=pop(sf); push(sf,n1-n2);
case '*': n2=pop(sf); n1=pop(sf); push(sf,n1*n2);
case '/': n2=pop(sf); n1=pop(sf); push(sf,n1/n2);
case '=': printf("%f¥n",peek(sf)); break;
case 'p': print(sf); break;
case 'q': end_flag=1; break;
default : push(sf,atof(buf));
}
}
}
// スタックを開放する
free(sf);
break;
break;
break;
break;
Algorithms and Data Structures on C
逆ポーランド電卓の実行結果
1+2=?
$ ./RPNCalc
1 2 + =
3.0
4と5と6を追加 → リスト
4 5 6
p
4: 3.0 4.0 5.0 6.0
(5+6)*4 → リスト
+ *
p
2: 3.0 44.0
(0-1)*44+3 → リスト
0 1 - * +
p
1: -41.0
-41+？
+
1つしか要素が入っ
Error: stack underflow
ていないスタックか
$
ら2つの要素を
取り出そうとした
Algorithms and Data Structures on C
待ち行列（Queue）
• 挿入が一方の端、削除がもう一方の端
– 生協のレジの行列
• 客は行列の最後尾に並ぶ
• レジが終わると、行列の先頭の客が抜ける
• FIFO（First In First Out）
待ち行列
レジ
Algorithms and Data Structures on C
待ち行列の構造
• パイプに詰め込まれた積み木の構造
–
–
–
–
詰め込むの端→末尾（rear）
取り出す端→先頭（front）
要素の追加→待ち行列に入れる（enqueue）
要素の削除→待ち行列から取り出す（dequeue）
dequeue
enqueue
front
rear
Algorithms and Data Structures on C
待ち行列の利用
• マルチタスク処理
– 複数のタスクを1つのCPUで処理するには、それ
ぞれのタスクを待ち行列に入れて、CPUが1つず
つそれを取り出して処理する。
• 印刷処理
– 1つのプリンタで複数の印刷物を印刷する場合は、
各印刷データは印刷キューに入れられ、プリンタ
が1つずつ順番に取り出して印刷する。
Algorithms and Data Structures on C
配列による待ち行列の実現
先頭
front
末尾
こちらへ移動していく
rear
・・・
・・・
先頭が抜ける
たびに移動
無限に長い配列？
待ち行列
長さ＝待っている要素数
末尾に来る
たびに移動
Algorithms and Data Structures on C
リングバッファによる待ち行列の実現
• 無限に長い配列は現実には不可能
• リングバッファを使用する
– 有限長の配列の先頭と末尾をつないだもの
– 配列 q[] で、q[M-1] の次に q[0] があると考える
– 具体的には、配列サイズMの剰余をインデックスとする
q[M-2]
リング
バッファ
q[M-1]
q[0]
q[1]
待ち行列
q[2]
front
q[3]
rear
Algorithms and Data Structures on C
リングバッファの利用法
• 初期状態：front=1,rear=0
• 取り出し：
– frontの位置の要素を取り出してからfrontを移動→front++
– q[(front++)%M]にアクセス
• 詰め込み：
– rearを移動してからrear次の位置に入れる→++rear
– q[(++rear)%M]にアクセス
• %Mを行うことで、リングバッファになる
q[]
0
1
2 ・・・
・・・
q[front%M]
q[rear%M]
%M
M-1
Algorithms and Data Structures on C
リングバッファの注意
• front=rear+1の状態は空？、フル？
– 待ち行列の長さを保持することによって判断できる
– 追加・削除時の制限
0
1
2 ・・・
length=0
・・・
M-1
取り出せない！
front=rear+1
0
1
2 ・・・
front
length=M
rear
・・・
M-1
詰め込めない！
front=rear+1
Algorithms and Data Structures on C
QInt.h
#ifndef __QInt__h
#define __QInt__h
/***
*** 整数用キュー
***/
#include <stdio.h>
#include <stdlib.h>
// 整数キュー型の宣言
typedef struct {
int *q;
int size;
int front,rear;
int length;
} QInt;
//
//
//
//
キュー
キューサイズ
キューポインタ
キューに実際に入っているデータ数
続く
Algorithms and Data Structures on C
QInt.h
// プロトタイプ宣言
QInt *makeQInt(int s);
void free(QInt *qi);
void enq(QInt *qi,int n);
int deq(QInt *qi);
int peek(QInt *qi);
int getSize(QInt *qi);
void print(QInt *qi);
#endif // __QInt__h
//
//
//
//
//
//
//
整数キューの生成
キューの破棄
エンキュー
デキュー
ピーク
要素数
内部の表示
Algorithms and Data Structures on C
QInt.cc
/***
*** QIntの実装
***/
#include "QInt.h"
// 整数キューの生成
QInt *makeQInt(int s){
QInt *qi=(QInt*)malloc(sizeof(QInt));
qi->size=s;
qi->q=(int*)malloc(qi->size*sizeof(int));
qi->front=1;
qi->rear=0;
qi->length=0;
return qi;
}
続く
Algorithms and Data Structures on C
QInt.cc
0
// エンキュー
void enq(QInt *qi,int n){
if(qi->length==qi->size){
fprintf(stderr,"Error: ....¥n");
exit(1);
}
1
2 ・・・
num=0
rear front
enqueue
num=1
enqueue処理
}
// デキュー
int deq(QInt *qi){
if(qi->length==0){
fprintf(stderr,"Error: ....¥n");
exit(1);
}
dequeue処理
}
続く
enqueue
num=2
enqueue
num=3
dequeue
num=2
Algorithms and Data Structures on C
QInt.cc
// ピーク
int peek(QInt *qi){
if(qi->length==0){
fprintf(stderr,"Error: queue underflow.¥n");
exit(1);
}
return qi->q[qi->front];
}
// 要素数
int getSize(QInt *qi){
return qi->length;
}
続く
Algorithms and Data Structures on C
QInt.cc
// 内部の表示
void print(QInt *qi){
printf("%d:",qi->length);
for(int i=0;i<qi->length;i++)
printf("%d ",qi->q[(qi->front+i)%qi->size]);
printf("¥n");
}
// キューの解放
void free(QInt *qi){
free(qi->q);
free((void*)qi);
}
Algorithms and Data Structures on C
QTest.cc
/*** キューのテスト ***/
#include "QInt.h"
int main(int argc,char **argv){
QInt *qi=makeQInt(100);
print(qi);
enq(qi,1); enq(qi,2); enq(qi,3); enq(qi,4);
print(qi);
deq(qi); deq(qi);
print(qi);
enq(qi,5); enq(qi,6);
print(qi);
deq(qi); deq(qi); deq(qi);
print(qi);
deq(qi); deq(qi);
print(qi);
free(qi);
}
Algorithms and Data Structures on C
簡単な待ち行列の例（結果）
$ ./TestQueue
0:
4: 1 2 3 4
2: 3 4
4: 3 4 5 6
1: 6
Error: queue underflow
$
1つしか要素が入っ
ていない待ち行列か
ら2つの要素を
取り出そうとした
Algorithms and Data Structures on C
課題161114
• QInt.ccのenq()とdeq()の不足しているコードを示せ。
• QIntを用いて、10個の整数をキューに入れ、それを取り出して表示する
プログラムQTest2.ccを作成せよ。実行結果を示せ。
• 作成方法：
• ソースコードを入力し、不足部分を補い、コンパイル・実行し、その
結果を示すこと。
• レポートはワードで作成すること。
• レポートの最初に学籍番号と氏名を明記すること。
• ワードのファイル名は、”scXXXXXX-al161114.docx” とすること。
• 完成したソースファイルを、ワード文書中に貼り付けて示せ。
• 提出方法：
• メールで。メールの本文中にも学籍番号を氏名を明記すること。
• 提出先：[email protected]
• メールタイトル：”アルゴリズム課題161114” ←厳守！
• 期限：2016年11月20日（日） 24:00
Algorithms and Data Structures on C
スタックと待ち行列
終了