ひとまず覚え書き。
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; } }