スポンサード リンク

スポンサーサイト

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

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

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

第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型のデータをそのまま出し入れすることができます。

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

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

  4. スポンサード リンク

    テーマ:プログラミング - ジャンル:コンピュータ - ソーシャルブックマーク: この記事をクリップ! Yahoo!ブックマークに登録

16 : 06 : 41 | プログラミング-Java | トラックバック(1) | コメント(0) | page top↑
<<UNIXシステムプログラミング-簡易シェルの実装 | ホーム | Javaで学ぶデータ構造入門01-スタック(1/3)-基本操作の実装>>
コメント

コメントの投稿














管理者にだけ表示を許可する

トラックバック
トラックバックURL
http://networkprogramming.blog18.fc2.com/tb.php/21-ef46b7e3
この記事にトラックバックする(FC2ブログユーザー)
第1回 順序付けされた要素の集合「線形リスト」
 いよいよ始まる第1回。今回は「線形リスト」を学ぶ。 == 線形リストのまとめ == ・「&#039;&#039;&#039;線形リスト&#039;&#039;&#039;」(&#039;&#039;&#039;リスト&#039;&#039;&#039;,&#039;&#039;&#039;並び&#039;&#039;&#039;,&#039;&#039;&#039;列&#039;&#039;&... 初心者の初心者による初心者のための自習室【2010/04/17 00:53】
| ホーム |

プロフィール

Author:TBVector

プロフィール

メールフォーム

記事検索

Google

最近の記事

人気の記事

過去の記事

カテゴリー

タグランキング

リンク

最近のコメント

最近のトラックバック

アクセスカウンタ

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