Javaで学ぶデータ構造入門01－スタック(2/3)－ジェネリクスの実装

Ads by Google

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

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

スポンサードリンク

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

Javaで学ぶデータ構造入門01－スタック(2/3)－ジェネリクスの実装

2008 / 02 / 26 ( Tue )

第1回となる前回エントリ「Javaで学ぶデータ構造入門01－スタック(1/3)－基本操作の実装」ではスタックが備える基本的な操作のみを実装しました。

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

しかし、前回の実装には

配列サイズが固定である。
int型のデータしか格納できない。

という問題がありました。そこで、今回は次のような改良をします。

pushのたびに配列の容量をチェックし、いっぱいになっていたら拡大する。
ジェネリクスを実装し、さまざまなオブジェクトを格納できるようにする。

ジェネリクスを実装したMyStack

public class MyStack<T> {
	
	private T[] stack;
	private int sp; /* stack pointer */
	private final static int DEFAULT_CAPACITY = 10;
	private int capacity;
	
	public MyStack() {
		this(DEFAULT_CAPACITY);
	}
	
	public MyStack(int initialCapacity) {
		capacity = initialCapacity;
		stack = (T[]) new Object[initialCapacity];
	}
	
	public void push(T item) {
		stack[sp++] = item;
		capacityCheck();
	}
	
	public T pop() {
		return stack[--sp];
	}
	
	private void capacityCheck() {
		if(sp >= capacity)
			expandCapacity();
	}
	
	private void expandCapacity() {
		capacity *= 2;
		Object[] oldStack = stack;
		stack = (T[]) new Object[capacity];
		System.arraycopy(oldStack, 0, stack, 0, sp);
	}

}

public MyStack()

引数が異なるもう1つのコンストラクタ MyStack(int initialCapacity) にデフォルトの容量(DEFAULT_CAPACITY(=10))を渡して呼び出します。

public MyStack(int initialCapacity)

引数にとった値をスタックの容量（内部で保持する配列のサイズ）にします。

public void push(T item)

T型のオブジェクトを引数にとり、それをスタックに積みます。その後、スタック（の内部に保持する配列）がいっぱいになっていないか確認します（capacityCheck()を呼び出します）。

public T pop()

スタックの一番上にある要素を取り出します。

private void capacityCheck()

スタック（の内部に保持する配列がいっぱいになっている(sp >= capacity)ならば、それを大きくするメソッドexpandCapacity()を呼び出します。これらのメソッドはクラス内のメソッドからしか呼び出さないので、アクセス指定子はprivateにしてあります。

private void expandCapacity()

スタック（の内部に保持する配列）の容量を増やします。といっても、今使っている配列を大きくすることはできないので、新しい配列を作り、System.arraycopy()でデータをそこにコピーします。

使用例

/* ○正しい */
MyStack<String> sStack = new MyStack<String>();
stack.push("hoge");

/* ○正しい */
MyStack<Integer> iStack = new MyStack<Integer>();
stack.push(10);

/* ×間違い */
MyStack<int> iStack = new MyStack<int>();
stack.push(10);

int型はオブジェクトではないのでIntegerとして扱う必要があります。ただし、オートボクシング/アンボクシングにより、いったんInteger用のスタックを作ってしまえば、（見かけ上）int型のデータをそのまま出し入れすることができます。