目次 †
スタック †
スタックは、最後に格納したデータから順に取り出す（＝LIFO：後入先出）構造を持った1次元配列である。
データを格納することをプッシュ（push）、データを取り出すことをポップ（pop）という。このプッシュとポップはLIFO（Last In First Out：後入れ先出し）である。
スタックのアルゴリズム †
スタックSはS=(array A,top,length)で定義される。
- array
- top
- スタックポインタ
- 次にデータを積む位置の要素番号のこと。
- length
ただし、初期値としてtop=0である。
プッシュのアルゴリズムPush(S,x)は次の通りである。
1
2
3
4
| | if top=length then
return error
top←top+1
A[top]←x
|
それではアルゴリズムPush(S,x)について解説する。
1行目のif文はスタックが一杯になったかどうかをチェックしている。もし一杯になったら、エラーを出力して終了する。
3行目でスタックポインタを1増やして、4行目でスタックポインタの位置にデータを積んでいる。
このアルゴリズムPush(S,x)の計算量は)
である。
また、ポップのアルゴリズムPop(S)は次の通りである。
1
2
3
4
| | if top=0 then
return error
top←top-1
return A[top+1]
|
それではアルゴリズムPop(S)について解説する。
1行目のif文はスタックが空になったかどうかをチェックしている。もし空になったら、エラーを出力して終了する。
3行目でスタックポインタを1減らして、4行目でスタックポインタの位置のデータを返して終了する。
このアルゴリズムPop(S)の計算量はである。
Javaでスタックを操作 †
スタック用のメソッドは次が挙げられる。
- Init
- スタックを確保し、スタックの深さとスタックポインタを初期化する。
- Push
- Pop
- IsEmpty
- IsFull
Javaによる実験 †
キー入力で数値を入力して、スタックにそのデータをPushし、スタックが一杯になったら順番にPopするプログラム（StackTest.java）を次に示す。ただし、IsEmpty,IsFullの結果はboolean型を返すことにする。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
-
|
|
|
|
|
|
|
-
|
|
|
!
|
|
|
|
-
-
|
!
|
|
!
|
|
|
-
-
|
!
|
|
!
|
|
|
-
-
|
-
|
!
!
|
|
|
-
-
|
-
|
!
!
|
|
|
-
|
-
|
!
|
!
|
|
-
|
|
|
|
|
|
|
-
-
|
|
|
|
|
|
-
|
|
-
|
|
!
!
|
|
|
|
|
|
-
|
|
|
!
!
!
|
import java.io.*;
public class StackTest {
static int[] StackData; static int StackPtr; static int StackMax;
static void Init(int stackMax){
StackMax=stackMax;
StackData=new int[StackMax];
StackPtr=0;
}
static void Push(int data){
if(StackMax <= StackPtr){
return;
}
StackData[StackPtr]=data;
StackPtr++;
}
static int Pop(){
if(StackPtr <= 0){
return 0;
}
StackPtr--;
return StackData[StackPtr];
}
static boolean IsEmpty(){
if(StackPtr==0){
return true;
}else{
return false;
}
}
static boolean IsFull(){
if(StackPtr >= StackMax){
return true;
}else{
return false;
}
}
static void ShowStack(){
System.out.println(StackPtr + ":");
for(int i=0;i<StackPtr;i++){
System.out.println(StackData[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
Init(5);
ShowStack();
BufferedReader rd=new BufferedReader(new InputStreamReader(System.in));
while(IsFull()!=true){
try{
System.out.println("?");
String ln=rd.readLine();
int data=Integer.parseInt(ln);
System.out.println("push:"+data+"\t");
Push(data);
ShowStack();
}catch(IOException e){
System.out.println("入力エラー");
return;
}catch(NumberFormatException e){
System.out.println("スタックに積む数値を入力せよ");
continue;
}
}
System.out.println("\n\t");
ShowStack();
while(IsEmpty() != true){
int n = Pop();
System.out.println("pop:"+n+"\t");
ShowStack();
}
}
}
|
このプログラムを実行すると次のようになる。?の次の数字が入力した数値である。
>java StackTest
0:
? 6
push:6 1:6
? 4
push:4 2:6 4
? 2
push:2 3:6 4 2
? 1
push:1 4:6 4 2 1
? 9
push:9 5:6 4 2 1 9
5:6 4 2 1 9
pop:9 4:6 4 2 1
pop:1 3:6 4 2
pop:2 2:6 4
pop:4 1:6
pop:6 0:
スタックの応用 †
- main関数の中で別の関数を呼び出すプログラム
- ハノイの塔
- グラフアルゴリズム
- グラフ探索アルゴリズムでスタックやキューが使われる。
- 逆ポーランド記法
- 式評価方法
参考文献 †
- 講義ノート
- 『超図解mini 基本情報技術者試験 平成19年度版』
- 『Eclipseによる体験学習 Javaではじめるアルゴリズム入門』
