逆転を狙う工大生の日々

絶賛留年中の落ちこぼれがなんとか頑張ろうとしている日記です

Javaでスタックを

「定本 Javaプログラマのためのアルゴリズムとデータ構造/近藤嘉雪 著」を参考にしながら、スタックのプログラムをJavaで書いてみました。

 

まずはスタックの基礎知識をおさらいしてみます。スタックとは、

・データ構造の一つである。箱を積み上げていくようなイメージ。

・挿入と削除がリストの先頭でのみ行われる、いわゆるLIFO(Last In First Out)になっている。つまり箱を上に積み上げて、一番上から取り出していく。

・削除する操作を「降ろす、取り出す」または「ポップ」、挿入する操作を「積む」または「プッシュ」という。

・スタックの先頭の位置をあらわす要素をスタックポインタといい、スタックポインタをとおして操作を行うことができる。

うろ覚えですが、確か深さ優先探索(そのうちやります)の時にも使いましたよね。一時的にデータを保管しておくための重要な概念ということでしょう。というわけでプログラムです。

------------Stack.java------------


import java.util.Arrays;

public class Stack {
	private Object stack[]; //スタック本体
	private int stackSize; //スタックの大きさ
	private int sp; //スタックポインタ
	
	private static final int DEFALT_STACK_SIZE = 100;
	
	//生成、デフォルトのスタックサイズは100
	public Stack(){
		this(DEFALT_STACK_SIZE);
	}
	
	//生成、サイズを指定する場合
	public Stack(int size){
		this.stack = new Object[size];
		this.stackSize = size;
		this.sp = 0;
	}

	//プッシュ
	public void Push(Object o){
	 if(sp >= stackSize){
	     throw new IllegalStateException("スタックの容量オーバー");
	 }
	 stack[sp++] = o;
	}
	
	//ポップ
	public Object Pop(){
	 if(sp <= 0){
		throw new IllegalStateException("スタックが空です");
	 }
	 Object value = stack[--sp];
	 stack[sp] = null;
	 return value;
	}
	
	public void PrintStack(){
	 System.out.println("--------------------------");
	 System.out.println("|スタックらしく上から表示|");
	 System.out.println("--------------------------");
	 for(int i = stack.length-1; i >= 0; i--){
		System.out.println(stack[i]);
	 }
	}
	
	public int getElementNum(){
	 return sp;
	}
	
	public void clearStack(){
	 Arrays.fill(stack, 0, sp, null);
	 sp = 0;
	}
}


基本的な機能として、生成・プッシュ・ポップ・リセット・要素数の取得・要素のプリントメソッドを用意しました。各メソッドの操作もシンプルですね。一番重要なプッシュ・ポップ操作に関しては、それぞれ「スタックポインタを後置インクリメント」「スタックポインタを前置デクリメントしたあと、元先頭の要素をnullにする」だけで実現できるようです。一年生の時にCでやったような気がするけど覚えてない。まあこれなら私でもわかる。

 

また、「Arrays.fill(Object[] o,int arg1,int arg2, Object val)」は、配列oのインデックスarg1からarg2までの要素にvalを代入するというArraysクラスに用意されたメソッドみたいです。これ中々便利そうですね。for文つかってnullにするよりスマートな気がする。気がするだけです。

---------------Main.java--------------


import java.util.Scanner;

public class Main {
 public static void main(String[] args) {
	 Scanner sc = new Scanner(System.in);
	 System.out.print("inputStackSize : ");
	 int n = sc.nextInt();
	
	 ack st = new Stack(n);
    for(int i=0; i < n; i++){
		st.Push(sc.next());
	 }
		
	 System.out.println("要素数は" + st.getElementNum() + "個です");
	 st.PrintStack();
	  System.out.println("---------------------");
		
	  for(int i=0; i < n; i++){
		System.out.println(st.Pop() + "を取り出しました");
	  }
	  System.out.println("---------------------");
	  st.clearStack();
	  System.out.println("要素数は" + st.getElementNum() + "個です");
	}
}


スタックのプッシュ・プリント・ポップ・リセットを行い、挙動を調べてみます。

-------------実行結果------------

inputStackSize : 5
11
22
33
44
55
要素数は5個です
--------------------------
|スタックらしく上から表示|
--------------------------
55
44
33
22
11
---------------------
55を取り出しました
44を取り出しました
33を取り出しました
22を取り出しました
11を取り出しました
---------------------
要素数は0個です

 最初のブロックではスタックサイズを5と指定して、「11,22,33,44,55」の順番にプッシュしています。それをプリントするとちゃんと55が先頭になっていますね。ポップも同様に先頭の55から取り出されています。プッシュを終えた時点での要素数は5でしたが、リセットを行った後には0になっています。

 

という感じでスタックの実装が出来ました。Javaにはスタッククラスが用意されてるので実際にはここまで書く必要ないです。

土曜日はJava、日曜日はCで同様のアルゴリズムを実装できればいいかなって思っています。始めたのが火曜日しかも祝日という中途半端なのがいけない。