java-char-stack
Javaでの文字スタックの定義
-
link:/tag/data-structures/ [データ構造]
1. 概要
このチュートリアルでは、Javaで_char_スタックを作成する方法について説明します。 最初にJava APIを使用してこれを行う方法を確認し、次にカスタム実装をいくつか見ていきます。
link:/java-stack[Stack]は、LIFO(後入れ先出し)の原則に従うデータ構造です。 一般的な方法のいくつかは次のとおりです。
-
_push(E item)_–アイテムをスタックの一番上にプッシュします
-
_pop()_–は、スタックの一番上のオブジェクトを削除して返します
-
_peek()_–は、削除せずにスタックの一番上にあるオブジェクトを返します
it
2. Java APIを使用した_Char_スタック
Javaには、_java.util.Stack_という名前の組み込みAPIがあります。 * _char_はプリミティブデータ型であり、ジェネリックでは使用できないため、_Stack。を作成するには、_java.lang.Character_ *のラッパークラスを使用する必要があります。
Stack<Character> charStack = new Stack<>();
これで、_Stack_で_push _、_ pop_、および_peek_メソッドを使用できます。
一方、スタックのカスタム実装を構築するよう求められる場合があります。 したがって、いくつかの異なるアプローチを検討します。
3. _LinkedList_を使用したカスタム実装
バックエンドデータ構造としてa__LinkedList_を使用して_char_スタックを実装しましょう。
public class CharStack {
private LinkedList<Character> items;
public CharStack() {
this.items = new LinkedList<Character>();
}
}
コンストラクタで初期化されるan__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_メソッドは、a _LinkedList_の組み込みメソッドを使用しています。 _pop_については、最初に_Iterator_を使用して、上部にアイテムがあるかどうかを確認しました。 存在する場合、_remove_ method _._を呼び出してリストから項目を削除します
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倍にしたい理由については、https://stackoverflow.com/questions/10419250/why-double-stack-capacity-を参照してください。固定量による増加の代わりに[StackOverflow post]。
最後に、_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];
}
両方のメソッドについて、スタックが空でないことを検証した後、position__size –_ 1の要素を返します。 _pop_の場合、要素を返すことに加えて、_size_を1減らします。
5. 結論
この記事では、Java APIを使用して_char_スタックを作成する方法を学び、いくつかのカスタム実装を見ました。
この記事に記載されているコードは、https://github.com/eugenp/tutorials/tree/master/core-java-modules/core-java-collections [GitHub上]で入手できます。