Javaで学ぶデータ構造入門01－スタック(1/3)－基本操作の実装

Ads by Google

-- / -- / -- ( -- )

上記の広告は１ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

スポンサードリンク

-- : -- : -- | スポンサー広告 | page top↑

Javaで学ぶデータ構造入門01－スタック(1/3)－基本操作の実装

2008 / 02 / 25 ( Mon )

スタックは後入れ先出し(LIFO : Last In First Out)に基づくデータ構造です。(cf. FIFOキュー)

基本的かつ応用上重要なデータ構造であるため、多くのプログラミング言語が標準ライブラリなどの形でサポートしています。JavaのAPIにもjava.util.Stackというクラスがあります。

第1回となるこのエントリではスタックが備える基本的な操作のみを実装しました。

push : スタックにデータを積む。
pop : スタックからデータを取り出す。

public class MyStack {
	
	private int[] stack;
	private final int DEFAULT_CAPACITY = 10;
	private int sp; /* Stack Pointer */
	
	public MyStack() {
		stack = new int[DEFAULT_CAPACITY];
	}
	
	public MyStack(int capacity) {
		stack = new int[capacity];
	}
	
	public void push(int item) {
		stack[sp++] = item;
	}
	
	public int pop() {
		return stack[--sp];
	}
}

public MyStack()

MyStackクラスのデフォルトのコンストラクタです。次のようにMyStackクラスのインスタンスをつくったときに呼び出されます。このとき、スタックの最大サイズはDEFAULT_SIZE(=10)になります。

使用例

MyStack stack = new MyStack();

public MyStack(int size)

MyStackクラスのコンストラクタです。int型の値を引数にとり、それをスタックの最大サイズに指定します。例えば、スタックの最大サイズを100としたい場合は次のようにします。

使用例

MyStack stack = new MyStack(100);

public void push(int item)

int型の値を引数にとり、それをスタックに積みます。以下のコードはスタックポインタ(sp : stack pointer)が指す場所へデータを格納し、その後、スタックポインタを進めています。

使用例

MyStack stack = new MyStack();
stack.push(10);
stack.push(20);
stack.push(30);

public int pop()

スタックの一番上に積まれているデータを取り出し、その値(int型)を返します。"--sp"とすることで、配列要素へアクセスする前にスタックポインタで一つ前を指しているのがポイントです。

使用例

MyStack stack = new MyStack();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());

出力結果

30
20
10

スタックにデータを積んだ順番とは逆順に値が出力されています。

問題点

この実装にはいくつかの問題があります。そこで、次回のエントリ（第2回）ではこれらを解決します。

配列サイズが固定である。

スタックが内部にもつ配列の最大サイズより多くのデータがpushされた場合をサポートしていません。

int型のデータしか格納できない。

スタックにint型以外のデータを積むことができません。

Javaで学ぶデータ構造入門01－スタック

Javaで学ぶデータ構造入門01－スタック(1/3)－基本操作の実装（このエントリ）
Javaで学ぶデータ構造入門01－スタック(2/3)－ジェネリクスの実装
Javaで学ぶデータ構造入門01－スタック(3/3)－さらなる操作の実装

書籍

明解Javaによるアルゴリズムとデータ構造
	柴田望洋ソフトバンククリエイティブ 2007-11-07 売り上げランキング : 6152 Amazonで詳しく見る by G-Tools