アルゴリズムとデータ構造

アルゴリズムと
データ構造
第6回
スタック
前回の復習

抽象データ型としての「リスト」



一定の型の要素を０個以上一列に並べたもの
リスト中のどの位置でも自由に参照，挿入(Insert)，削除
(Delete)の操作を行える
リストの実現方法


配列を用いる方法：「要素の配列」と「最後の要素の位
置を示す変数」で実現
ポインタを用いる方法：「要素」と「次のセルを指すポイン
タ」でセルを構成し，セルを順次つなぐことで，連結リスト
を作成し，実現
前回演習問題の解答
ROOT
0093
0091
番地
ROOT
内容
0094
009D 0000
番地
内容
番地
内容
0106
0093
010E
0095
00FF
0100
0107
0108
010F
010A
0100
0091
0108
0094
0110
0096
0101
0106
0109
010E
0111
0112
0102
009C
010A
009A
0112
0098
0103
0104
010B
010C
0113
0114
0104
009D
010C
009B
0114
0099
0105
0000
010D
0102
0115
0000
前回演習問題の解答
ROOT
0091
ROOT
0106
009A
010C
番地
内容
0093
009B
0108
0102
0094
010E
009C 0104
0095
010A
009D 0000
番地
内容
番地
内容
0106
0093
010E
0095
00FF
0100
0107
0108
010F
010A
0100
0091
0108
0094
0110
0096
0101
0106
0109
010E
0111
0112
0102
009C
010A
009A
0112
0098
0103
0104
010B
010C
0113
0114
0104
009D
010C
009B
0114
0099
0105
0000
010D
0102
0115
0000
第6回と第7回の内容
スタック
 抽象データ型としてのスタック
 単方向リストによるスタックの実現
 配列によるスタックの実現
 スタックの利用例

ポーランド記法，逆ポーランド記法
今回の内容
キュー
 抽象データ型としてのキュー
 単方向リストによるキューの実現
 循環配列（リングバッファ）によるキューの実現
Ｐａｒｔ１：スタック(Stack)
スタック(Stack)


スタック：要素の挿入や削除がいつも一方の端
（先頭）からしかできないリスト
後から入れた要素ほど，先に出る
スタックの先頭→
別名
（top）
 後入れ先出しリスト
 LIFO (last-in first-out)
 push down list
a4
スタックの底→
（bottom）
a1
a3
a2
抽象データ型としてのスタック

抽象データ型：データ構造＋操作
スタック
操作
要素を
並べたもの
先頭への要素の挿入
Push
先頭からの要素の取出し
Pop
スタックの操作
 CREATE(S )：空スタックSを準備しその先頭
の位置を返す
 PUSH(x, S )：要素ｘをSの先頭に入れる
 POP(S )：先頭の要素を削除する
＜同時にSの先頭の要素を返す場合もある＞
単方向リストによるスタックの実現
top
……
init
an-1
Push, Popを行うために使用するスタッ
クの先頭へのポインタ
ak
…
bottom
init
(=a1)
a0
構造のイメージ
an-1
an-2
a0
完全に変える
セルを追加していくスタイル
スタックの底の要素が格納されて
いるセルのnextはNULL
スタックの型定義(単方向リスト版)とPUSH
のプログラム例
/* セルを表わす構造体の定義 */
struct cell
セルのデータ構造はリストのときと同じ。
{
ここではint型の要素としたが、どのような型でも
int element;
良い。
struct cell *next;
};
…
main(){…}
struct cell型への
…
ポインタを返す関数
struct cell *push(int x, struct cell *init)
{
struct cell *q, *r;
r = (struct cell *)malloc(sizeof(struct cell));
q = init; init =r;
r->element = x; r->next = q;
return(init);
}
Pushの実現(単方向リスト版)
Pushが始まる直前

initはあるリストの先頭要素を指す．
Push(x, S) [struct cell *push(int x, struct cell
*init)]

① 新しいセル用のメモリを確保し、rはそのセルを指すポインタとする
init
an-1
an-2
a0
r
① r = (struct cell *)malloc(sizeof(struct cell));
Pushの実現(単方向リスト版)

Push(x, S)
① 新しいセル用のメモリを確保し、rはそのセルを指すポインタとする
② qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく）
③ initにrを代入する（＝initを新しい要素用セルへのポインタとする）
init
② q = init;
q
③ init = r;
r
an-1
an-2
a0
Pushの実現(単方向リスト版)

Push(x, S)
① 新しいセル用のメモリを確保し、rはそのセルを指すポインタとする
② qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく）
③ initにrを代入する（＝initを新しい要素用セルへのポインタとする）
④ 新しいセルに要素ｘを代入
⑤ r->nextが，前の先頭要素のセルを指すようにする
init
q
an-1
④ r->element = x;
r
x
⑤ r->next = q;
an-2
a0
Pushの実現(単方向リスト版)

Push(x, S)
① 新しいセル用のメモリを確保し、rはそのセルを指すポインタとする
② qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく）
③ initにrを代入する（＝initを新しい要素用セルへのポインタとする）
④ 新しいセルに要素ｘを代入
⑤ r->nextが，前の先頭要素のセルを指すようにする
⑥ 新しい要素を指すinitを返す
呼び出し元
（mainなど）
へ
新要素を指す
initだよ〜
q
init
x
r
⑥ return(init);
an-1
an-2
a0
POPのプログラム例
スタックが空でない場合はstruct
…
cell型へのポインタを返す関数
main()
空の場合はエラーメッセージ
…
struct cell *pop(struct cell *init)
{
struct cell *q;
if(init !=NULL)
{
q = init; init = init->next;free(q); return(init);
}
else
{
printf(“Error: Stack is empty.\n”); exit(1);
}
return;
}
exit文はプログラムを終了させる標準関数で，この関数が０を返せば正常終了，それ以外を返せば異常終了と
判断される．exit文を使用する場合には，#include <stdlib.h>が必要である．
Popの実現(単方向リスト版)
init

Popが始まる直前
an-1
an-2
a0
initはあるリストの先頭要素を指す．

Pop(S)

initがNULLではない場合以下を実行
① qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく）
init
① q = init;
q
an-1
an-2
a0
Popの実現(単方向リスト版)

Pop(S)

initがNULLではない場合以下を実行
① qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく）
② initを前の先頭要素の次（＝前の２番目）へのポインタとする
③ 削除するセルの領域を解放
④ 書き換えられたinitを呼び出し元（main関数など）へ返す
呼び出し元
（mainなど）
へ
init
init変えました〜
q
③ free(q);
an-1
an-2
② init = init->next;
④ return(init);
a0
Popの実現(単方向リスト版)

Pop(S)

initがNULLではない場合以下を実行
① qにinitを代入する（＝前の先頭要素へのポインタをqに保持しておく）
② initを前の先頭要素の次（＝前の２番目）へのポインタとする
③ 削除するセルの領域を解放
④ 書き換えられたinitを返す

initがNULLの場合
⑤ エラーメッセージを表示して関数を終了
init
⑤ printf(“Error: stack is empty.¥n”);exit(1);
スタックの型の定義(配列版)
#define N 100 /* 配列の最大サイズ */
struct stack /* 構造体stackの定義 */
{
int top;
int element[N];
};
…
main()
データ構造はリスト(配列版)のときと基本的には同じ．タグ
…
名，メンバー名を変更しただけ．
配列によるpushのプログラム例
void push(int x,struct stack *S)
{
if(S->top >=N || S->top < 0) S->top = N;
if(S->top == 0)
{
printf(“Error: Stack is full.\n”);exit(1);
}
else
{
S->top = S->top-1; S->element[S->top]=x;
}
return;
}
配列によるスタックの実現
element
topはスタックの先頭位置を示すint型変数
ポインタ型変数ではない
top
［N-1］に，スタックの底を固定
する点がポイント．
要素を挿入/削除するたびにリ
スト全体を上げ下げしなくて済
む．
[0]
[1]
an-1(先頭)
an-2
a1
[N-1] a0(底)
ス
タ
ッ
ク
が
伸
び
る
方
向
Pushの実現
(配列版)
N=7の場合
初期状態

element
Stack型:スタックの要素が入る配列element

スタックの先頭位置を示すtop
から成る構造体で、elementには既に要素あり
[0]
[1]

[2]
(つまりtopの先頭アドレスを指す）
[3]
Sはstack型を指すポインタ
準備ができたら
S
[4] Ｃ
top 5
push関数を呼ぶ
void push(int x,struct stack *S)
[5] Ａ
Ｂ1
[6] Ａ0
Pushの実現
(配列版)
①if(S->top >=N || S->top < 0) S->top = N;
element
element
[0]
[1]
S
[2]
top -1 ?
[3]
[4]
S
[5]
top 8
topが7以上又はtopが負
ならスタックは空
その場合はtop=7とする
? [6]
[0]
[1]
[2]
[3]
[4]
S
top 7
[5]
[6]
Pushの実現
(配列版)
topが0ならば、スタックは満杯。
エラーメッセージを表示して関数 top 0
を終了
②
N=7の場合
element
[0] Ａ6
[1] Ａ5
[2] Ａ4
[3] Ａ3
if(S->top == 0)
[4] Ａ
{
2
printf(“Error: Stack is full.\n”);
[5] Ａ1
exit(1);
}
[6] Ａ
0
Pushの実現
(配列版)
それ以外の場合：
 topを1減らす
 topが指しているelementの位置に
要素xを挿入
N=7の場合
element
[0]
[1]
[2]
[3]
③ else
{
S->top = S->top-1;
S->element[s->top]=x;
}
top 4
[4] x
top 5
[5] Ａ1
[6] Ａ0
配列によるpopのプログラム例
void pop(struct stack *S)
{
if(S->top < N)
{
S->top = S->top + 1;
}
else
{
printf(“Error: Stack is empty.\n”);
exit(1);
}
return;
}
Popの実現
(配列版)
N=7の場合
element
topがN未満なら要素はある
その場合は topを1増やす
[0]
[1]
[2]
① if(S->top < N)
{
S->top = S->top + 1;
}
[3]
[4] Ｃ
5
[5] A
Ｂ1
① top 6
[6] Ａ0
Popの実現
(配列版)
N=7の場合
element
それ以外（N以上）なら
エラーメッセージを表示して関数を終了
[0]
[1]
[2]
else
{
printf(“Error: Stack is empty.\n”);
exit(1);
}
7
[3]
[4] Ｃ
？
[5] Ｂ
[6] Ａ
配列によるスタックの実現（参考）
element
[0] a0 (底)
[1] a1
スタックの底を，配列の
インデクス[0]に固定し
てもよい．
この場合，上下を逆に
する点に注意．
an-2
top
an-1(先頭)
[N-1]
ス
タ
ッ
ク
が
伸
び
る
方
向
練習問題
Push
Pop
次の手順で操作を行うと
スタックS1,S2の中身は
最終的にどのようになるか？
Push
① Push(A,S1)
② Push(B,S2)
③ Push(C,S1)
④ D=Pop(S1)で削除した要素
⑤ Push(D, S2)
⑥ Pop(S1)
S1
S2
Pop
練習問題
Push
Pop
Push
① Push(A,S1)
② Push(B,S2)
③ Push(C,S1)
④ D=Pop(S1)で削除
した要素
⑤ Push(D, S2)
⑥ Pop(S1)
S1
S2
Pop
練習問題
D(=C)
Pop
① Push(A,S1)
② Push(B,S2)
③ Push(C,S1)
④ D=Pop(S1)で削除
した要素
⑤ Push(D, S2)
C
⑥ Pop(S1)
A
B
S1
S2
練習問題
D(=C)
Push
① Push(A,S1)
② Push(B,S2)
③ Push(C,S1)
④ D=Pop(S1)で削除
した要素
⑤ Push(D, S2)
⑥ Pop(S1)
A
B
S1
S2
練習問題
Pop
① Push(A,S1)
② Push(B,S2)
③ Push(C,S1)
④ D=Pop(S1)で削除
した要素
D(=C)
⑤ Push(D, S2)
⑥ Pop(S1)
A
B
S1
S2
スタックの利用例：算術式の評価
大切
予備知識：数式の表記法
 前置表現（prefix notation）

ポーランド記法(polish notation)
 中置表現（infix notation）

通常の数式表記法
 後置表現（postfix notation）

逆ポーランド記法(reverse polish notation)
ポーランド記法，逆ポーランド記法では括弧
[“（”と“）”]を使わずに数式を表現できる
歴史
 ポーランド記法は，ポーランドの論理学者
Jan Łukasiewicz(1878-1956) が1920年
に提案
出典http://www.calculator.org/Lukasiewicz.html
 1957年には，オーストラリアの計算機科学
者Charles L. Hamblin (1922-1985) が
New South Wales University of
Technologyで，スタックを実装
出典http://www.csc.liv.ac.uk/~peter/hamblin.html
A+Bの表記法
前置表現（ポーランド記法）
演算子を変数の前に置く
例：+AB 足すことのAB
演算子の優先順位は存在しない．括弧が不要．
中置表現
演算子を変数の間に置く
例：A+B A足すB
演算子の優先順位が存在する．括弧が必要．
後置表現（逆ポーランド記法）
演算子を変数の後に置く
例：AB+ AとBを足す
演算子の優先順位は存在しない．括弧が不要．
後置表現への変換
( A – B ) * ( C + D ) (式1) 演算子 (式2)
(式1)
演算子
(式2)
(A–B) (C+D)＊
(式1) 演算子 (式2)
AB- (C+D)＊
AB–CD+＊
(式1) (式2) 演算子
個々の式を
後置表現に
する
後置表現
その他の数式の例
前置表現
ポーランド記法
中置表現
通常の表記法
後置表現
逆ポーランド記法
++ABC
A+B+C
AB+C+
*-AB+CD
(A-B)*(C+D)
AB-CD+*
-*47+53
4*7-(5+3)
47*53+-
-A÷BC
A-B÷C
ABC÷-
練習問題

ア
イ
ウ
エ
逆ポーランド記法では，例えば，式(A-B)*CをABC*と表現する．次の式を逆ポーランド記法で表現
したものはどれか
（A+B）*(C-D÷E)
AB+CDE÷-*
AB+C-DE÷*
AB+EDC÷-*
BA+CD-E÷*
練習問題
（A+B）*(C-D÷E)
（A+B） (C-D÷E) *
AB+ (C-D÷E) *
AB+ (C-DE÷) *
AB+ CDE÷- *
答ア
スタックの利用例：算術式の評価

スタックを使うと，逆ポーランド記法で書かれた
式を左から順に読んで演算処理できる．

処理手順
一要素ずつ読み込み，要素が“数”ならスタック
にPush
“演算子”ならスタックから２つの要素をPopして
演算し，演算結果をスタックにPush
最終的にスタックに式の演算結果が残る
◆
◆
◆
算術式の評価例1

例：６＋４＊７
後置表現⇒６４７ * ＋
4*7
７
４
６
6+28
２８
６
３４
算術式の評価例2
例２：６＋｛４＊（７＋４）－３｝
⇒６４７４＋＊３－＋

７＋４
４
７
４
６
４＊１１
１１
４
６
４４－３
４４
６
３
４４
６
６＋４１
４１
６
４７
まとめ
要素の追加
要素の削除
リスト
どこでも可
どこでも可
スタック
先頭
先頭
キュー
代表的な操作
Insert
Delete
Push
Pop
演習問題
問題１：
スタックＳに次のような一連の操作を実行したとき、
スタックＳの内容がどのようになるか示しなさい。
Push(S, a), Push(S, b), Push(S, c), Pop(S),
Pop(S), Push(S, d), Pop(S), Push(S, e).
演習問題
問題２：
次のアルゴリズムpush(S, x)をプログラムとして実
現しなさい。
push(S, x)
{
if(top < max)
{
top ← top + 1
S[top] ← x;
}
else{
print(“Stack S over flows.”);
}
}
演習問題
名前と学籍番号をご記入のうえ、解答用紙（A4）を提出する
提出先：
工学部電子情報実験研究棟５階
NO.5506室のドアのポストに入れてください
締め切り時間：
来週月曜日（5月26日）午前９時まで

Download Report