Fight the Future

Java言語とJVM、そしてJavaエコシステム全般にまつわること

メモ

ひとまず覚え書き。

public final class Stack {

	private int pointer = 0;	// スタック内のデータ位置を指すポインタ
	private Object[] stack;		// データを格納するための配列
	
	/**
	 * スタックのサイズを引数にとるコンストラクタ。
	 * @param size スタックのサイズ。
	 */
	public Stack(int size) {
		stack = new Object[size];
	}
	
	/**
	 * スタックにデータを積む。
	 * @param data スタックに積むデータ。
	 */
	public void push(Object data) {
		
		if(pointer < stack.length) {
			// データを格納してポインタをカウントアップ
			stack[pointer++] = data;
		} else {
			// スタックのオーバーフロー(例外をスロー)
			throw new IndexOutOfBoundsException("Stack is over flow.");
		}
	}
	
	/**
	 * スタックからデータを取り出す。
	 * @return data スタックから取り出されたデータ。
	 *              スタックが空の場合にはnullを返す。
	 */
	public Object pop() {
		
		Object data = null;
		
		// スタックが空でない場合のみ
		if(pointer > 0){
			// スタックからデータを取り出す。
			// ポインタはカウントダウン
			data = stack[--pointer];
		}
		
		return data;
	}
}
public final class Queue {

	private int capacity;	// キューの容量
	private int head = 0;	// キューの先頭位置
	private int tail = 0;	// キューの後尾位置
	
	private float loadFactor = 0.75f;	// 負荷係数
	
	private Object[] queue;
	
	/**
	 * キュー・サイズを引数にとるコンストラクタ
	 * @param size キューのサイズ
	 */
	public Queue(int size) {
		
		this.capacity = size + 1;	// サイズを1つ余分に設定(ポインタ移動のための余白)
		queue = new Object[this.capacity];
	}
	
	/**
	 * キューにデータを挿入する。
	 * @param data キューに挿入されるデータ
	 */	
	public void enQueue(Object data) {
		
		if(isNeedToExpand()) {
			ensureCapacity();
		}
		
		// tail + 1 が headと同じ場合にはキュー・サイズ
		// が満杯であることを意味するため挿入は実行しない。
		if((tail + 1) % capacity != head) {
			queue[tail++] = data;		// データを挿入
			tail = tail % capacity;		// tailの値を 0 〜 capacity までの値に調整 
			
		} else { // 満杯の場合
			throw new IndexOutOfBoundsException("Queue is full.");
		}
	}
	
	/**
	 * キューからデータを取り出す。
	 * @return キューから取り出されたデータ。
	 *         キューが空の場合にはnullが返る。
	 */
	public Object deQueue() {
	
		Object data = null;
		
		// tail == head の場合にはキューが空の状態であることを
		// 意味するためデータの取り出しは実行しない。
		if(tail != head) {
			data = queue[head];			// データを取り出す。
			queue[head++] = null;		// GCの対象とするため null を設定
			head = head % capacity;		// head の値を 0 〜 capacity までの値に調整 
		}
		
		return data;	// データを返す。
	}
	
	/**
	 * 容量拡張の必要性を検証
	 * @return 容量拡張の必要性があればtrue
	 */
	private boolean isNeedToExpand() {
		return loadFactor * capacity > tail;
	}
	
	/**
	 * 容量を拡張
	 */
	private void ensureCapacity() {
		int newCapacity = capacity * 2;
		Object[] newQueue = new Object[newCapacity];
		capacity = newCapacity;
		System.arraycopy(queue, 0, newQueue, 0, queue.length);
		queue = newQueue;
	}
}