スポンサード リンク

スポンサーサイト

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

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

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

スタックは後入れ先出し(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-スタック

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

書籍

明解Javaによるアルゴリズムとデータ構造
4797345233柴田 望洋

ソフトバンククリエイティブ 2007-11-07
売り上げランキング : 6152


Amazonで詳しく見る
by G-Tools

スポンサード リンク

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

19 : 37 : 18 | プログラミング-Java | トラックバック(0) | コメント(0) | page top↑
<<Javaで学ぶデータ構造入門01-スタック(2/3)-ジェネリクスの実装 | ホーム | Webページにソースコードを表示するために~CSS編~>>
コメント

コメントの投稿














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

トラックバック
トラックバックURL
http://networkprogramming.blog18.fc2.com/tb.php/20-23cfed86
この記事にトラックバックする(FC2ブログユーザー)
| ホーム |

プロフィール

TBVector

Author:TBVector

プロフィール

メールフォーム

記事検索

Google

最近の記事

人気の記事

過去の記事

カテゴリー

タグランキング

リンク

最近のコメント

最近のトラックバック

アクセスカウンタ

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