Androidデータ構造02-スタック、キュー、および逆ポーランド式

6769 ワード

データ構造02-スタックとキュー
一、桟
スタックは、テーブルの最後にのみ挿入および削除を行う線形テーブルを定義します.挿入と削除を許可する一端をスタックトップ(top)、他端をスタックベース(bottom)と呼び、データ要素を含まないスタックを空スタックと呼ぶ.スタックは後進先出の線形テーブルとも呼ばれる.
スタックの適用:逆ポーランド式.
1.スタックの実装
スタックには、配列とチェーンテーブルの2つの実装方法があります.
配列実装は複雑で、サイズを限定する必要があり、スタックオーバーフローの問題が発生します.AndroidソースのStackは配列で実現される.
チェーンテーブルを使用すると、サイズを限定することなく、メモリの消費量が高くなります.
この2つの方式の添削改査効率は近い.
2.スタックのチェーン実装
スタックの上部に要素を追加するには、次の手順に従います.

public void add(E e) {
    LinkedTable.Node node = new LinkedTable.Node(e, first);
    first = node;
    size++;
}

スタックトップ削除要素:

public E pop() {
    if (first == null) {
        return null;
    }
    E e = first.item;
    first = first.next;
    size--;
    return e;
}

二、逆ポーランド式
1.定義
逆ポーランド式は接尾辞式とも呼ばれます.通常の式では、二元演算子は常に関連する2つの演算オブジェクトの間に配置され、この表現は接尾辞表現とも呼ばれます.ポーランドの論理学者J.Lukasiewiczは1929年に別の表現式を表す方法を提案した.この方法では、各演算子が演算対象の後に置かれているため、接尾辞表現と呼ばれている.
2.用途
逆ポーランド式は、複雑な式を簡単な操作で計算結果を得ることができる式に変換するのに非常に有用な式です.例えば(a+b)(c+d)はab+cd+に変換される.
3.実現
接尾辞式を接尾辞式に変換するには、スタックで実装する必要があります.文字をスタックに入れるには、次のルールに従う必要があります.

数字であれば

を直接取り出す.

スタックトップが空の場合、直接スタック

に入る

プラスマイナス乗除であれば、スタックトップと比較して優先度がスタックトップより高く、直接スタックに入る.優先度はスタックトップより低く、まずスタックをスタックトップから出して、それから新しいスタックトップと比較します.優先度がスタックのトップより高くなるまで、スタックに入ります.

が'(')であれば、直接スタックに入ります.

が')'であれば、スタックトップと比較して優先度がスタックトップより高く、直接スタックに入る.優先度はスタックトップより低く、まずスタックをスタックトップから出して、それから新しいスタックトップと比較します.スタックの頂上が'(',把'('出スタック;

/**
 * @param expStr      
 * @return      
 */
public static String getSuffixExpression(String expStr) {
    //      ')'
    char[] expChars = (expStr + Type.RSP.name).toCharArray();
    Stack stack = new Stack();
    StringBuffer stringBuffer = new StringBuffer();
    for (char c : expChars) {
        //      
        if (Type.isSymbol(c)) {
            Character top = stack.get();
            if (top == null) {
                stack.add(c);
            } else if (c == Type.LSP.name) {
                stack.add(c);
                //         
            } else if (Type.compareTo(top, c) >= 0) {
                while (Type.compareTo(top, c) >= 0) {
                    //     
                    stringBuffer.append(star);
                    //      
                    stringBuffer.append(stack.pop());
                    top = stack.get();
                    if (top == null) {
                        break;
                    }
                    //      ')'，   '('     
                    if (top.charValue() == Type.LSP.name && c == Type.RSP.name) {
                        stack.pop();
                        break;
                    }
                }
                if (c != Type.RSP.name) {
                    stack.add(c);
                }
            } else {
                stack.add(c);
            }
            //     
            if (c != Type.LSP.name && c != Type.RSP.name) {
                stringBuffer.append(star);
            }
        } else {
            stringBuffer.append(c);
        }
    }
    return stringBuffer.toString();
}

ツールクラスで演算子の優先度を判断するには、次の手順に従います.

/**
 *     
 */
public static enum Type {
    ADD('+', 1), MIN('-', 1), MUL('*', 2), DIV('/', 2), LSP('(', 0), RSP(')', 0);
    //     
    public char name;
    //      
    public int index;

    Type(char name, int index) {
        this.name = name;
        this.index = index;
    }

    /**
     *           
     *
     * @param c
     * @return
     */
    public static int getID(char c) {
        for (Type type : values()) {
            if (type.name == c) {
                return type.index;
            }
        }
        return -1;
    }

    /**
     *          
     *
     * @param c   
     * @return
     */
    public static boolean isSymbol(char c) {
        for (Type type : values()) {
            if (type.name == c) {
                return true;
            }
        }
        return false;
    }

    /**
     *      
     *
     * @param a
     * @param b
     * @return
     */
    public static int compareTo(char a, char b) {
        return getID(a) - getID(b);
    }
}

4.計算
接尾辞式を結果として計算する場合は、スタックも使用します.

/**
 * @param expStr      
 * @return     
 */
public static long countSuffixExpression(String expStr) {
    long result = 0;
    if (Tool.isEmpty(expStr)) {
        return result;
    }
    String[] array = expStr.split(Character.toString(star));
    Stack stack = new Stack();
    for (String s : array) {
        char c = s.charAt(0);
        //         
        if (Type.isSymbol(c)) {
            String a = stack.pop();
            String b = stack.pop();
            if (!Tool.isEmpty(a) && !Tool.isEmpty(b)) {
                //             
                BigDecimal bigA = new BigDecimal(b);
                BigDecimal bigB = new BigDecimal(a);
                BigDecimal bigC = null;
                //     
                if (c == Type.ADD.name) {
                    bigC = bigA.add(bigB);
                    //     
                } else if (c == Type.MIN.name) {
                    bigC = bigA.subtract(bigB);
                    //     
                } else if (c == Type.MUL.name) {
                    bigC = bigA.multiply(bigB);
                    //     
                } else if (c == Type.DIV.name) {
                    bigC = bigA.divide(bigB, 0, BigDecimal.ROUND_UP);
                }
                //      
                stack.add(bigC.toString());
            }
            //      ，   
        } else {
            stack.add(s);
        }
    }
    result = new BigDecimal(stack.get()).longValue();
    return result;
}

三、行列
キューは、一端でのみ挿入操作を許可し、他端では削除操作を行うリニアテーブルです.挿入された一端をキューテール、削除された一端をキューヘッダと呼びます.
1.実現
キューには、配列とチェーンテーブルの2つの実装もあります.
配列実装:デキュー複雑度が0(n)高く、偽オーバーフローしやすい.
チェーンテーブル実装:実装が簡単で、メモリが高い.
注意:偽オーバーフローとは、キューの頭部に空席があり、尾がいっぱいで、尾に要素を挿入しなくなり、オーバーフローの仮象をもたらすことです.
2.一般的なキュー
ループキュー
ヘッダとテールが接続されたシーケンスストレージ構造のキュー.偽オーバーフローの問題を解決しました.
両端キュー(Deque)
スタックとキューの性質を持つデータ構造です.両端キューの要素は、テーブルの両端から挿入および削除することを制限します.
適用:LinkedList/ARayDeque/LinkedBlockingDeque(ブロックされた双方向キュー)
優先キュー
優先度キューは、通常のスタックとキューと同じですが、中の各要素には「優先度」があります.処理時には、まず優先度が最も高く処理されます.2つの要素が同じ優先度を持っている場合は、キューに挿入された順に処理されます.
適用:MessageQueue
最後に
コードアドレス:https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/datastructure/table/Stack.java
データ構造とアルゴリズムのテーマ:https://www.jianshu.com/nb/25128590
好きならいいね、ありがとう!

Ethereum全ノード構築

ドメインコントローラにSRV DNSレコードが作成されていることを確認する方法