1.スタックの概念

スタックはLIFO(Last In First Out)で動作する線形資料構造の一種である.スタックの典型的な応用は関数のcallスタックである.関数が呼び出されると、ローカル変数、伝達パラメータ、戻り値アドレスなど(プロセッサアーキテクチャによって若干異なるが)がスタックに積み上げられ、より奥にある関数ほど呼び出しが速くなり、戻り値(pop)が元のビットに戻る.
次の関数呼び出し構造では,スタックの挙動を表す.

void x() {...}
void y() {...}

void z() {
    x();
    y();
}

int main() {
    z();
}

2.スタック実装

詳細な説明はいくつかの重要な方法に限られる.最後にコード全体があります.

1)フィールドと初期化

public class Stack<T> {

	private int capacity;
	private int ptr;
	private T[] array;

	@SuppressWarnings("unchecked")
	public Stack() {
		ptr = 0;
		capacity = 10;
		array = (T[]) new Object[capacity];
	}
}

スタックを実装するには、少なくとも3つのプロパティが必要です.

capacity

スタック容量(内部アレイサイズ)

ptr

スタックポインタ

スタック内の要素数

array

要素記憶アレイ

初期容量は10に設定します.ptrの初期値には何も含まれていないので、もちろんゼロで配列を生成して初期化します.

2) push()

public void push(T t) {
    justifyStackSize();
    array[ptr++] = t;
}

private void justifyStackSize() {
    if (ptr >= capacity) {
        capacity *= 2;
        @SuppressWarnings("unchecked")
        T[] extendedArray = (T[]) new Object[capacity];
        System.arraycopy(array, 0, extendedArray, 0, array.length);
        array = extendedArray;
    }
}

要素を追加する前に、フルになっているかどうかを確認し、容量を増やします.フルになると、容量が2倍の新しいアレイが生成されます.その後、既存のアレイの要素を新しいアレイにコピーすると、array変数に新しいアレイが割り当てられます.
配列に要素を追加する操作なので、時間の複雑さは定数時間です.ただし、スタックが満たされている場合、配列サイズを増やして前の配列のすべての要素をコピーする操作は、データの数に比例するため、O(N)となります.
しかし,Nが大きいほど配列サイズを調整した場合はN比0に収束する.したがって、通常スタックのpush()動作は、時間的複雑さを定数と見なす.

3) pop()

public T pop() {
    if (ptr <= 0) {
        throw new EmptyStackException();
    }
    return array[--ptr];
}

空の場合は例外を放出します.空でない場合は、最後の要素が返されます.

4) clear()

public void clear() {
    while (ptr-- > 0) {
        array[ptr] = null;
    }
}

単純にptr = 0をすれば、正常な動作は問題ありません.これにより,時間複雑度も定数時間O(1)となる.ただし、配列に含まれるオブジェクトはgcのオブジェクトではなく、メモリの浪費を招くため、nullの処理を直接行い、gcを収集させることが望ましい.ただし,時間的複雑度がO(N)であれば,特に制限はなく,必ずそうしなければならない.
完全なコード

public class Stack<T> {

    private int capacity;
    private int ptr;
    private T[] array;

    @SuppressWarnings("unchecked")
    public Stack() {
        ptr = 0;
        capacity = 10;
        array = (T[]) new Object[capacity];
    }

    public void push(T t) {
        justifyStackSize();
        array[ptr++] = t;
    }

    private void justifyStackSize() {
        if (ptr >= capacity) {
            capacity *= 2;
            @SuppressWarnings("unchecked")
            T[] extendedArray = (T[]) new Object[capacity];
            System.arraycopy(array, 0, extendedArray, 0, array.length);
            array = extendedArray;
        }
    }

    public T pop() {
        if (ptr <= 0) {
            throw new EmptyStackException();
        }

        return array[--ptr];
    }

    public T peek() {
        return array[ptr - 1];
    }

    public int indexOf(T t) {
        for (int i = ptr - 1; i >= 0; i--) {
            if (array[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }

    public void clear() {
        while (ptr-- > 0) {
            array[ptr] = null;
        }
    }

    public int capacity() {
        return capacity;
    }

    public int size() {
        return ptr;
    }

    public boolean isEmpty() {
        return ptr <= 0;
    }

    public boolean isFull() {
        return ptr >= capacity;
    }
}