Javaでの文字スタックの定義

投稿日: 2019-10-18 2022-10-25
タグ: Data Structures, Java, Java Collections

1. 概要

このチュートリアルでは、Javaでcharスタックを作成する方法について説明します。最初にJavaAPIを使用してこれを行う方法を確認し、次にいくつかのカスタム実装を確認します。

Stack は、LIFO（後入れ先出し）の原則に従ったデータ構造です。その一般的な方法のいくつかは次のとおりです。

push（E item） –アイテムをスタックの一番上にプッシュします
pop（） –スタックの最上位にあるオブジェクトを削除して返します
peek（） –オブジェクトを削除せずにスタックの一番上にあるオブジェクトを返します

2. Char JavaAPIを使用したスタック

Javaには、java.util.Stackという名前の組み込みAPIがあります。 charはプリミティブデータ型であり、ジェネリックでは使用できないため、java.lang.Characterのラッパークラスを使用してStackを作成する必要があります。

Stack<Character> charStack = new Stack<>();

これで、 push 、 pop 、およびpeekメソッドをStackで使用できるようになりました。

一方、スタックのカスタム実装を構築するように求められる場合があります。したがって、いくつかの異なるアプローチを検討します。

3. LinkedListを使用したカスタム実装

バックエンドデータ構造としてLinkedListを使用して、charスタックを実装しましょう。

public class CharStack {

    private LinkedList<Character> items;

    public CharStack() {
        this.items = new LinkedList<Character>();
    }
}

コンストラクターで初期化されるitems変数を作成しました。

ここで、 push 、 peek 、およびpopメソッドの実装を提供する必要があります。

public void push(Character item) {
    items.push(item);
}

public Character peek() {
    return items.getFirst();
}

public Character pop() {
    Iterator<Character> iter = items.iterator();
    Character item = iter.next();
    if (item != null) {
        iter.remove();
        return item;
    }
    return null;
}

pushおよびpeekメソッドは、LinkedListの組み込みメソッドを使用しています。 pop の場合、最初に Iterator を使用して、上部にアイテムがあるかどうかを確認しました。そこにある場合は、 remove メソッド。を呼び出して、リストからアイテムを削除します。

4. 配列を使用したカスタム実装

データ構造に配列を使用することもできます。

public class CharStackWithArray {

    private char[] elements;
    private int size;

    public CharStackWithArray() {
        size = 0;
        elements = new char[4];
    }

}

上記では、 char 配列を作成します。この配列は、コンストラクターで初期容量4で初期化されます。さらに、スタックに存在するレコードの数を追跡するためのsize変数があります。

それでは、pushメソッドを実装しましょう。

public void push(char item) {
    ensureCapacity(size + 1);
    elements[size] = item;
    size++;
}

private void ensureCapacity(int newSize) {
    char newBiggerArray[];
    if (elements.length < newSize) {
        newBiggerArray = new char[elements.length * 2];
        System.arraycopy(elements, 0, newBiggerArray, 0, size);
        elements = newBiggerArray;
    }
}

アイテムをスタックにプッシュするとき、最初に、配列にアイテムを格納する容量があるかどうかを確認する必要があります。そうでない場合は、新しい配列を作成し、そのサイズを2倍にします。次に、古い要素を新しく作成された配列にコピーし、それをelements変数に割り当てます。

注：単にサイズを1つ増やすのではなく、配列のサイズを2倍にしたい理由の説明については、この StackOverflowpostを参照してください。

最後に、peekメソッドとpopメソッドを実装しましょう。

public char peek() {
    if (size == 0) {
        throw new EmptyStackException();
    }
    return elements[size - 1];
}

public char pop() {
    if (size == 0) {
        throw new EmptyStackException();
    }
    return elements[--size];
}

どちらの方法でも、スタックが空でないことを確認した後、 size –1の位置にある要素を返します。 pop の場合、要素を返すことに加えて、sizeを1デクリメントします。

5. 結論

この記事では、JavaAPIを使用してchar スタックを作成する方法を学び、いくつかのカスタム実装を確認しました。

この記事で紹介するコードは、GitHubでから入手できます。

getdocs

13036