Javaスタック(ダイナミック配列ベース)
前回のブログでは、Javaダイナミック配列の実装や注意点を皆さんと共有しましたが、見たことのない学生はまず、Javaダイナミック配列を理解することができます.
このダイナミック配列ができたら、次にスタックを見てみましょう.スタックという後進先出のデータ構造はよく知られていないと思います.スタックを適用する場所は少なくないからです.例えば、一般的な取り消し操作、括弧マッチングなどです.(ブログは最後にみんなと一緒に括弧マッチングの小さなdemoを実現します)
まず、スタックのインタフェースを定義します.
Javaソースを読んだことがある人は、ここで明らかにしたインタフェース名とjava内部にカプセル化されたStackインタフェース名はまったく同じで、興味のある学生は自分のスタックを実現すると同時に、javaソースコードの中でどのように実現されているのかを見て、自分にも向上することができます.
次に,前述のブログの動的配列に基づいてスタックを実現することができる.
動的配列ができた後、スタックを実現するのは非常に簡単なことがわかります.では、スタックができたら、カッコが一致するかどうかを判断するために、彼を使って何かをします.
「{[()]}」のようなものは一致し,「{(}}}」のようなものは一致しない.
このような問題に対して、私たちはどのようにスタックを利用して実現しますか?
左側のカッコ'{','[','(',直接スタックに入れ,右側のカッコ'}',']',')'について,スタックされた要素を取り出してマッチングし,コード実装を見てみよう.
ループ終了後、スタックが空であるか否かを判断し、空でなければ同様に一致しないことに注意してください.
注釈のStackはjavaが私たちに提供してくれたスタックで、興味のある学生はjavaのスタックと私たち自身が実現したスタックを比較することができます.
スタックはみんなとここまで分かち合って、次のブログは、みんなと一緒にダイナミック配列に基づくキューを分かち合って、読んでくれてありがとう.
転載する必要がある学生に出典を明記してください.https://blog.csdn.net/sinat_33150417/article/details/81744073
このダイナミック配列ができたら、次にスタックを見てみましょう.スタックという後進先出のデータ構造はよく知られていないと思います.スタックを適用する場所は少なくないからです.例えば、一般的な取り消し操作、括弧マッチングなどです.(ブログは最後にみんなと一緒に括弧マッチングの小さなdemoを実現します)
まず、スタックのインタフェースを定義します.
public interface StackInterface {
E pop();
E peek();
void push(E e);
boolean isEmpty();
int getSize();
}
Javaソースを読んだことがある人は、ここで明らかにしたインタフェース名とjava内部にカプセル化されたStackインタフェース名はまったく同じで、興味のある学生は自分のスタックを実現すると同時に、javaソースコードの中でどのように実現されているのかを見て、自分にも向上することができます.
次に,前述のブログの動的配列に基づいてスタックを実現することができる.
public class ArrayStack implements StackInterface {
private Array array;
public ArrayStack(int capacity) {
array = new Array<>(capacity);
}
public ArrayStack() {
array = new Array<>();
}
@Override
public E pop() {
return array.removeLast();
}
//
@Override
public E peek() {
return array.getLast();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public int getSize() {
return array.getSize();
}
public int getCatacity() {
return array.getCapacity();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append('[');
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1) {
res.append(", ");
}
}
res.append("] Top");
return res.toString();
}
}
動的配列ができた後、スタックを実現するのは非常に簡単なことがわかります.では、スタックができたら、カッコが一致するかどうかを判断するために、彼を使って何かをします.
「{[()]}」のようなものは一致し,「{(}}}」のようなものは一致しない.
このような問題に対して、私たちはどのようにスタックを利用して実現しますか?
左側のカッコ'{','[','(',直接スタックに入れ,右側のカッコ'}',']',')'について,スタックされた要素を取り出してマッチングし,コード実装を見てみよう.
public class BracketsTest {
public static boolean isBracketsVaild(String s) {
// Stack stack = new Stack<>();
ArrayStack stack = new ArrayStack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char topChar = stack.pop();
if (c == ')' && topChar != '(') {
return false;
}
if (c == ']' && topChar != '[') {
return false;
}
if (c == '}' && topChar != '{') {
return false;
}
}
}
return stack.isEmpty();
}
}
ループ終了後、スタックが空であるか否かを判断し、空でなければ同様に一致しないことに注意してください.
注釈のStackはjavaが私たちに提供してくれたスタックで、興味のある学生はjavaのスタックと私たち自身が実現したスタックを比較することができます.
スタックはみんなとここまで分かち合って、次のブログは、みんなと一緒にダイナミック配列に基づくキューを分かち合って、読んでくれてありがとう.
転載する必要がある学生に出典を明記してください.https://blog.csdn.net/sinat_33150417/article/details/81744073