【DSaaA】スタックとキュー
21261 ワード
スタックとキュースタックとキュー スタック ADT シーケンススタック チェーンスタック シーケンススタックとチェーンスタックの比較 スタックの適用例 シンボルペアが に一致するかどうかを確認する.計算機(四則演算) メソッド呼び出しおよび再帰
キュー ADT シーケンスキュー チェーンキュー シーケンスキューとチェーンキュー キューのアプリケーション
スタック
ADT
スタックもテーブルですが、このテーブルの挿入と削除操作は同じ位置、すなわちテーブルの末尾(スタックトップ)でのみ行えます.スタックに対する操作が最も一般的なのは入スタックと出スタックであり、もちろんスタックが空いていると判断し、スタックがいっぱいであると判断し、スタックの頂上を取るなどの操作も含まれている.
スタックは後進先出(
シーヶンススタック
シーケンススタックはシーケンステーブルの単純な実装と見なすことができるが,シーケンステーブルのヘッダとテーブルテールをスタックトップとするかを決定する必要がある.
表頭をスタックのトップとすると、入スタックと出スタックの操作は
シーケンススタックの実装は、ArrayStack.java
チェーンスタック
チェーンスタックはチェーンテーブルを用いて実現され、順序実装とは特に大きな違いはなく、異なるデータ構造を用いているだけであり、チェーンスタックのスタックトップは、チェーンテーブルのヘッダの挿入と削除の時間的複雑さが
シーケンススタックとチェーンスタックの比較
単純なシーケンススタックは予め空間を割り当てる(単純配列実装)必要があり、スタック内のデータが多すぎるとオーバーフローを招く可能性があり、
チェーンスタックはシーケンススタックの大部分の悩みがなく、余分な空間を占有する以外に、実際のアプリケーションのスタックは基本的にシーケンステーブルで実現されている(
スタックの適用例
シンボルペアが一致するかどうかを確認します
たとえば、式
けいさんき
簡単な計算機は直接読みながら解釈し、4つの演算法則を守らないのは間違いない.四則演算を遵守するには、接尾辞表現(逆ポーランド式)式スタックを使用する必要があります.スタックを使用して、逆ポーランド式への接尾辞式の変換を行うこともできます.
上の方法は少し愚かで、実は直接2つのスタックを使うことができます:1つの操作数スタック、1つのオペレータスタック、解析しながら計算しますが、まず逆ポーランド式に変換してから計算して、構想はとてもはっきりしていて、2つのスタックの方式の効率はもっと高いです.
メソッド呼び出しと再帰
再帰調の実現も同様である.すなわち、f(x)=xf(x−1)f(x)=xf(x−1)の1つの問題は同じサブ問題に多く分けることができ、問題の難易度は減少し、最も簡単な問題は定数であり、問題の個数は限られている.すなわち,
キュー
ADT
キューも簡単なテーブル実装であり、ヘッダの削除、テールの挿入のみが可能で、先に出力されます.キューはバッファに使用され、容量があります.キューが満載の場合、新しいエンキュー要求は要素がデキューされるまでブロックされます.
キューの操作は一般的に、エンキュー、アウトキュー、空判定、空設定、満判定、キューヘッダの取得などがあります.
ちくじキュー
キューは、シーケンステーブルで実装することができ、2つのポインタ
偽のオーバーフローを解決する方法は、配列の最後のノードと最初のノードを論理的に接続することであり、
チェーンキュー
偽のオーバーフローを解決するのに非常に有効な方法は、チェーンテーブルを使用してキューを実現することです.自身のチェーンテーブルにはヘッダノードがあり、要素の削除と追加の時間的複雑さは
シーケンスキューとチェーンキュー
キューには固定容量があり、
キューの適用
キューは一般的にキャッシュとして使用され、生産と消費速度の不一致に一致します.
例えばプリンタ作業では、同じプリンタを使用する人が多く、
さらに
スタック
ADT
スタックもテーブルですが、このテーブルの挿入と削除操作は同じ位置、すなわちテーブルの末尾(スタックトップ)でのみ行えます.スタックに対する操作が最も一般的なのは入スタックと出スタックであり、もちろんスタックが空いていると判断し、スタックがいっぱいであると判断し、スタックの頂上を取るなどの操作も含まれている.
スタックは後進先出(
LIFO)であり、スタックの可視要素はスタックトップにのみ存在する.シーヶンススタック
シーケンススタックはシーケンステーブルの単純な実装と見なすことができるが,シーケンステーブルのヘッダとテーブルテールをスタックトップとするかを決定する必要がある.
表頭をスタックのトップとすると、入スタックと出スタックの操作は
0番目の位置で挿入と削除操作を行う必要があり、これにより、入スタックのたびに順序テーブルの残りのすべての要素を移動する必要があり、時間の複雑さはO(n)である.シーケンステーブルの最後の要素をスタックトップとし、出入りスタック操作のたびにシーケンステーブルの最後に削除または追加操作を行うと、時間複雑度はO(1)であることが明らかになる.シーケンススタックの実装は、ArrayStack.java
チェーンスタック
チェーンスタックはチェーンテーブルを用いて実現され、順序実装とは特に大きな違いはなく、異なるデータ構造を用いているだけであり、チェーンスタックのスタックトップは、チェーンテーブルのヘッダの挿入と削除の時間的複雑さが
O(1)であるため、テールノードであることを規定する必要はない.シーケンススタックとチェーンスタックの比較
単純なシーケンススタックは予め空間を割り当てる(単純配列実装)必要があり、スタック内のデータが多すぎるとオーバーフローを招く可能性があり、
ArrayListに依存して実装するとオーバーフローの可能性はないが、拡張や収縮の際にコピー操作があり、特にデータ量が大きい場合、拡張の半分が完全に使用されていないと空間が浪費され、しかし、格納されているのはすべてデータ自体であり、データの占有スペースは少なくなります.チェーンスタックはシーケンススタックの大部分の悩みがなく、余分な空間を占有する以外に、実際のアプリケーションのスタックは基本的にシーケンステーブルで実現されている(
Javaを含む).スタックは大量のデータを格納するのに適していないため、一般的にはスタックでコンテキスト関連の計算法を実現しているため、あまり多くのデータはなく、シーケンススタックを使用するのに十分である.スタックの適用例
シンボルペアが一致するかどうかを確認します
たとえば、式
{(a+b)/c-d+[(e-f)/(g+h)+i]}/100の{[()]}がペアで一致しているかどうかを確認します.public class SymbolPairChecker {
public static boolean check(String pattern) {
if (StringUtils.isNoneBlank(pattern)) {
ArrayStack stack = new ArrayStack<>();
for (int i = 0; i < pattern.length(); i++) {
Character character = pattern.charAt(i);
switch (character) {
case '{':
case '[':
case '(':
if (!stack.isEmpty()) {
Character preCharacter = stack.peek();
if (!order(character, preCharacter)) {
throw new RuntimeException(formatError(pattern, i));
}
}
stack.push(character);
break;
case ')':
case ']':
case '}':
if (stack.isEmpty()) {
throw new RuntimeException(formatError(pattern, i));
}
Character preCharacter = stack.pop();
if (!match(character, preCharacter)) {
throw new RuntimeException(formatError(pattern, i));
}
}
}
if(!stack.isEmpty()){
throw new RuntimeException(formatError(pattern, pattern.length() - 1));
}
}
return true;
}
private static boolean match(Character character, Character preCharacter) {
switch (character) {
case '}':
if(preCharacter != '{'){
return false;
}
break;
case ']':
if(preCharacter != '['){
return false;
}
break;
case ')':
if(preCharacter != '('){
return false;
}
break;
}
return true;
}
private static boolean order(Character character, Character preCharacter) {
return character <= preCharacter;
}
private static String formatError(String pattern, int i) {
return "Symbol not match!
" + pattern + "
" + pointer(i);
}
private static String pointer(int i) {
StringBuilder result = new StringBuilder();
for (int j = 0; j < i; j++) {
result.append(" ");
}
return result + "^";
}
public static void main(String[] args) {
check("{(a+b)/c-d+[(e-f)/(g+h)+i]}/100");
//check("(a+b)/c-d+[(e-f)/(g+h)+i]}/100");
//check("((a+b)/c-d+[(e-f)/(g+h)+i]}/100");
//check("([])");
//check("({})");
check("[");
}
} けいさんき
簡単な計算機は直接読みながら解釈し、4つの演算法則を守らないのは間違いない.四則演算を遵守するには、接尾辞表現(逆ポーランド式)式スタックを使用する必要があります.スタックを使用して、逆ポーランド式への接尾辞式の変換を行うこともできます.
public class StackCalculator {
private final static Map CHARACTER_WEIGHT_MAP = new HashMap<>();
static {
CHARACTER_WEIGHT_MAP.put('+', 1);
CHARACTER_WEIGHT_MAP.put('-', 1);
CHARACTER_WEIGHT_MAP.put('*', 2);
CHARACTER_WEIGHT_MAP.put('/', 2);
CHARACTER_WEIGHT_MAP.put('(', 3);
CHARACTER_WEIGHT_MAP.put(')', 4);
}
public static Double eval(String exp) {
exp = exp.replaceAll(" ", "")//
.replaceAll("\\(-", "(0-");// (-2) -> (0-2)，
SymbolPairChecker.check(exp);
List reversePolishExp = reversePolishExp(exp);
ArrayStack numStack = new ArrayStack<>();
for (String s : reversePolishExp) {
try {
Double d = Double.parseDouble(s);
numStack.push(d);
} catch (NumberFormatException e){
Double b = numStack.pop();
Double a = numStack.pop();
switch (s){
case "+":
numStack.push(a + b);
break;
case "-":
numStack.push(a - b);
break;
case "*":
numStack.push(a * b);
break;
case "/":
numStack.push(a / b);
break;
}
}
}
return numStack.pop();
}
private static List reversePolishExp(String exp) {
List list = new ArrayList<>();
ArrayStack stack = new ArrayStack<>();
StringBuilder num = new StringBuilder();
for (int i = 0; i < exp.length(); i++) {
Character character = exp.charAt(i);
String type = typeOfCharacter(character);
if (type.equals("num")) {
num.append(character);
} else if (type.equals("op")) {
if(num.length() > 0){
list.add(num.toString());
num = new StringBuilder();
}
if (stack.isEmpty()) {//
stack.push(character);
} else {
if (character == ')') {// )， ， (， (
Character toAppend = stack.pop();
while (toAppend != '(') {
list.add(String.valueOf(toAppend));
toAppend = stack.pop();
}
} else {// ， ， ；
Character preCharacter = stack.peek();
while (preCharacter != '(' && CHARACTER_WEIGHT_MAP.get(character) <= CHARACTER_WEIGHT_MAP.get(preCharacter)) {
list.add(String.valueOf(stack.pop()));
if(stack.isEmpty()){
break;
}
preCharacter = stack.peek();
}
}
//
if(character != ')'){
stack.push(character);
}
}
}
}
if(num.length() > 0){
list.add(num.toString());
}
if(!stack.isEmpty()){
while (!stack.isEmpty()){
list.add(String.valueOf(stack.pop()));
}
}
return list;
}
private static String typeOfCharacter(Character character) {
switch (character) {
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
return "op";
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '.':
return "num";
default:
throw new RuntimeException("Character not allowed here : " + character);
}
}
public static void main(String[] args) {
System.out.println(eval("((12+40)*2-4+((5-6/2)/(1+2)+100))/100"));
System.out.println(eval("11+22*33+(44*55+66)*77"));
System.out.println(eval("1/2-3*(4+5)"));
}
} 上の方法は少し愚かで、実は直接2つのスタックを使うことができます:1つの操作数スタック、1つのオペレータスタック、解析しながら計算しますが、まず逆ポーランド式に変換してから計算して、構想はとてもはっきりしていて、2つのスタックの方式の効率はもっと高いです.
メソッド呼び出しと再帰
Javaのいずれかのプログラムフラグメントは、ほとんどメソッドのネスト呼び出しである.メソッドA()に入ると、このメソッドには様々なパラメータ、変数名、および対応する値がある.その後、別の方法A1()の呼び出しが開始され、このときA()の方法の現場が1つのスタックに押し込まれ(push())、A1()の方法に入り始め、A1()の方法が終了した後、A()の方法の現場を復元し(pop())、実行を継続する.A1()メソッドに他のメソッドがネストされている場合、同じスタックにプッシュすることができます.再帰調の実現も同様である.すなわち、f(x)=xf(x−1)f(x)=xf(x−1)の1つの問題は同じサブ問題に多く分けることができ、問題の難易度は減少し、最も簡単な問題は定数であり、問題の個数は限られている.すなわち,
f(x)を解決するには,f(x-1)を解決するだけでよく,f(1)が固定解になるまで順次類推し,最後に戻ってf(2) f(3) ... f(x)を順次解決する.典型的な再帰-階乗の非再帰的な実装:public static Long factorialStack(int n){
Stack stack = new ArrayStack<>();
while(n > 0){
stack.push(n--);
}
Long result = 1L;
while(!stack.isEmpty()){
result *= stack.pop();
}
return result;
} キュー
ADT
キューも簡単なテーブル実装であり、ヘッダの削除、テールの挿入のみが可能で、先に出力されます.キューはバッファに使用され、容量があります.キューが満載の場合、新しいエンキュー要求は要素がデキューされるまでブロックされます.
キューの操作は一般的に、エンキュー、アウトキュー、空判定、空設定、満判定、キューヘッダの取得などがあります.
ちくじキュー
キューは、シーケンステーブルで実装することができ、2つのポインタ
frontおよびrearを維持することができ、前者はキューヘッダを指し、後者はキューヘッダを指し、入力するたびにキューを出る操作が単純にテールノードに加えられるか、またはヘッダノードに削除される場合、frontおよびrearを移動するだけで、時間の複雑さはO(1)であり、要素をコピーする必要はない.しかし、frontポインタはずっと後ろに移動しており、ある時点でfrontポインタがキューの最後に移動した場合、これは再入隊すると必ず1つの配列の境界を越える異常(偽オーバーフロー)が得られるが、frontポインタを配列の最初の要素に維持しておくと、そのたびに要素をコピーしなければならない.これは非常に完璧な実現方法ではない(ArrayQueue.java).偽のオーバーフローを解決する方法は、配列の最後のノードと最初のノードを論理的に接続することであり、
frontとrearのメンテナンスは簡単な++ではなく、2つのポインタのいずれかが配列の末尾に到着した場合、配列の開始位置に直接ジャンプし、入隊するたびにrear = (rear + 1) / capacity、出隊するたびにfront = (fron + 1) / capacityである.これにより、論理的に最初と最後が接続されていることが保証されます(SimpleArrayQueue.java).チェーンキュー
偽のオーバーフローを解決するのに非常に有効な方法は、チェーンテーブルを使用してキューを実現することです.自身のチェーンテーブルにはヘッダノードがあり、要素の削除と追加の時間的複雑さは
O(1)であり、ポインタを必要とせずにメンテナンスする必要はありませんが、キューの現在の容量を維持して、キューがオーバーフローしないことを保証する必要があります(LinkedQueue.java).シーケンスキューとチェーンキュー
キューには固定容量があり、
ADT定義に基づいて他のクエリー操作がないため、シーケンススタックを直接使用するとスペースを節約でき、JavaのArrayBlokingQueueがシーケンスキューである.キューの適用
キューは一般的にキャッシュとして使用され、生産と消費速度の不一致に一致します.
例えばプリンタ作業では、同じプリンタを使用する人が多く、
10人が同時に印刷要求を提出している場合、明らかにプリンタは忙しくて手が回らないが、印刷要求は成功することができ、これらの要求は1つのキューに入れられ、先着順サービスの原則に従って、1つずつ印刷される.さらに
redisのキューでは、メッセージの生産速度が速く、例えばクーポンを一括送信するが、メッセージの消費速度は遅い.1つの情報の送信はユーザーの状態、ネットワークなどに依存するため、このときメッセージを1つのキューに入れて、送信サーバにゆっくり消費させることができる.