Java プログラミングスキル - データ構造とアルゴリズムの「スタック」

[[387145]]

基本的な紹介

1. スタックはFILO（先入れ後出し）順序付きリストです

2. スタックは、線形テーブル内の要素の挿入と削除を、線形テーブルの同じ端でのみ実行するように制限する特殊な線形テーブルです。挿入と削除を許可する端は可変端で、スタックの上部と呼ばれ、もう一方の端は固定端で、スタックの下部と呼ばれます。

3. スタックの定義によれば、スタックに最初に配置された要素はスタックの一番下に配置され、スタックに最後に配置された要素はスタックの一番上に配置されます。要素を削除する場合はその逆になります。スタックに最後に配置された要素が最初に削除され、スタックに最初に配置された要素が最後に削除されます。

スタックの応用シナリオ

1. サブルーチン呼び出し：サブルーチンを呼び出す前に、次の命令のアドレスをスタックに格納し、サブルーチンの実行後にアドレスを取り出して元のプログラムに戻ります。

2. 再帰呼び出しを処理する: サブルーチン呼び出しに似ていますが、次の命令のアドレスを保存するだけでなく、パラメーター、ローカル変数、その他のデータもスタックに保存します。

3. 式の変換（中置式から後置式へ）と評価（実際の解）。

4. 二分木の走査。

5. グラフの深さ優先探索アルゴリズム。

スタック構造の実装例

パッケージ com.structures.stack; 
 
 java.util.Scanner をインポートします。 
 
パブリッククラスArrayStackDemo {
公共 静的void main(String[] args) {
        ArrayStack スタック = 新しいArrayStack(4);
        文字列キー= "" ;
        ブールループ = true ;
        スキャナー scanner = new Scanner( System.in );
        while (ループ) {
            System.out.println ( "show: スタックを表示" );
            System.out.println ( "exit: プログラムを終了" );
            System.out.println ( "push: スタックにデータを追加します (push)" );
            System.out.println ( "pop: スタックからデータを取り出す (pop)" );
キー= スキャナ.next ( );
            スイッチ（キー）{
場合  "見せる" ：
                    スタックリスト();
                    壊す;
場合  "押す" ：
                    System.out.println ( "数字を入力してください" );
 int値 = scanner.nextInt();
                    スタックに値をプッシュします。
                    壊す;
場合  「ポップ」 :
                    試す {
 int res = stack.pop();
                        System.out.println ( "スタックからデータがポップされました%d\n" +res);
                    } キャッチ (例外 e) {
                        System.out.println (e.getMessage()) ;
                    }
                    壊す;
場合  "出口" ：
                    スキャナーを閉じます() ;
                    ループ = false ;
                    壊す;
            }
        }
        System.out.println ( "プログラムが終了します" ) ;
    }
 } 
 
 //スタック構造を表すクラスを定義する
クラスArrayStack {
    private int maxSize; //スタックサイズ
    private int [] stack; //配列はスタックをシミュレートし、データは配列内に配置されます
    プライベートint   top = -1; // top はスタックの先頭を意味し、-1 に初期化されます
 
パブリックArrayStack( int最大サイズ){
        this.maxSize = 最大サイズ;
        スタック = 新しいint [this.maxSize];
    } 
 
    // スタックがいっぱいかどうか確認する
パブリックブール値isFull() {
戻る 上部== 最大サイズ - 1;
    } 
 
    // スタックが空かどうか確認する
パブリックブール値isEmpty() {
戻る 上== -1;
    } 
 
    //スタックにプッシュ
パブリックvoidプッシュ( int値){
        満杯の場合（）{
            System.out.println ( "スタックがいっぱいです" ) ;
戻る;
        }
トップ++;
        スタック[上部] = 値;
    } 
 
    //ポップアウト
公共 整数ポップ() {
        空の場合（）{
            新しい RuntimeException( "スタックが空です" ) をスローします。
        }
 int値 = スタック[上部];
トップ--;  
戻り値;
    } 
 
    //スタックの状況を表示する [スタックを走査する]
パブリックボイドリスト（）{
        空の場合（）{
            System.out.println ( "スタックは空です、データがありません~~" );
戻る;
        }
 ( int i = top ; i >= 0; i --) {  
            システム.out.printf ( "stack[%d]=%d\n" , i, stack[i]);
        }
    } 
 
 }

スタックを使用して式の計算を完了する（中置式）

数字スタックとシンボルスタックの 2 つのスタックを準備します。

1. インデックス値 (index) を介して式を走査します。

2. 数字であることが判明した場合、それは直接デジタルスタックに格納されます。

3. シンボルの場合は、状況を個別に考慮します。現在のシンボルスタックが空の場合は、ステーションに直接入力します。シンボルスタックに演算子がある場合は、それを比較します。

現在の演算子の優先度がスタック内の演算子の優先度以下の場合は、数値スタックから 2 つの数値をポップし、次にシンボルスタックから文字をポップして演算を実行し、その結果を数値スタックに入力してから、現在の演算子をシンボルスタックに入力します。
現在の演算子の優先度がスタック内の演算子よりも高い場合は、その演算子はスタックに直接プッシュされます。

4. 式をスキャンすると、対応する数字と記号が数字スタックと記号スタックから順番にポップされ、実行されます。

5. 最後に、数値スタックには式の結果である数値が 1 つだけ残ります。

パッケージ com.structures.stack; 
 
パブリッククラス Calculator {
公共 静的void main(String[] args) {
        //表現
        文字列式 = "700+2*6-2" ;
        //スタックをカウントする
        ArrayStack2 numStack = 新しいArrayStack2(10);
        //シンボルスタック
        ArrayStack2 operStack = 新しいArrayStack2(10);
整数  index = 0; // スキャン用
整数1 = 0;
整数2 = 0;
整数オペランド = 0;
整数res = 0;
 char ch = ' ' ; //スキャンした各文字を ch に保存します
        String keepNum = "" ; //複数の数字を連結するために使用します
        （真）の間{
            ch =式.部分文字列(インデックス,インデックス+ 1 ).charAt(0);
            //演算子の場合
            オペランドスタックがオペランドスタックである場合、
                //空の場合
                （operStack.isEmpty()）の場合{
                    operStack.push(ch);
                }それ以外{
                    operStack.priority(ch) <= operStack.priority(operStack.peek()) の場合 {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        //演算結果を数値スタックに、現在のシンボルをシンボルスタックに格納します
                        numStack.push(res);
                        operStack.push(ch);
                    }それ以外{
                        operStack.push(ch);
                    }
                }
            }それ以外{
                // 複数桁の数字を扱う場合、すぐにスタックにプッシュすることはできません。
                数値を保持 += ch;
                //chが式の最後の桁の場合
                if (インデックス== 式の長さ() - 1 ) {
                    numStack.push(整数.parseInt(keepNum));
                }それ以外{
                    if (operStack.isOper(式.部分文字列(インデックス+1,インデックス+2).charAt(0))) {
                        numStack.push(整数.parseInt(keepNum));
                        保持数 = "" ;
                    }
                }
            }
インデックス++;
            //最後までスキャンして終了
            if (インデックス>= 式の長さ()) {
                壊す;
            }
        }
        （真）の間{
            （operStack.isEmpty()）の場合{
                壊す;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            numStack.push(res);
        }
        System.out.printf ( "expression%s=%d\n" ,expression,numStack.pop()); 
 
    }
 } 
 
クラスArrayStack2 {
    private int maxSize; //スタックサイズ
    private int [] stack; //配列はスタックをシミュレートし、データは配列内に配置されます
    プライベートint   top = -1; // top はスタックの先頭を意味し、-1 に初期化されます
 
パブリックArrayStack2( int最大サイズ){
        this.maxSize = 最大サイズ;
        スタック = 新しいint [this.maxSize];
    } 
 
    //スタック上の現在の値を返す（ポップしない）
公共  intピーク() {
スタック[先頭]を返します。
    } 
 
    // スタックがいっぱいかどうか確認する
パブリックブール値isFull() {
戻る 上部== 最大サイズ - 1;
    } 
 
    // スタックが空かどうか確認する
パブリックブール値isEmpty() {
戻る 上== -1;
    } 
 
    //スタックにプッシュ
パブリックvoidプッシュ( int値){
        満杯の場合（）{
            System.out.println ( "スタックがいっぱいです" ) ;
戻る;
        }
トップ++;
        スタック[上部] = 値;
    } 
 
    //ポップアウト
公共 整数ポップ() {
        空の場合（）{
            新しい RuntimeException( "スタックが空です" ) をスローします。
        }
 int値 = スタック[上部];
トップ--;  
戻り値;
    } 
 
    //スタックの状況を表示する [スタックを走査する]
パブリックボイドリスト（）{
        空の場合（）{
            System.out.println ( "スタックは空です、データがありません~~" );
戻る;
        }
 ( int i = top ; i >= 0; i --) {  
            システム.out.printf ( "stack[%d]=%d\n" , i, stack[i]);
        }
    } 
 
    //演算子の優先度を返します。数値が大きいほど優先度が高くなります。
    //現在使用できる演算子は + - * / のみであると仮定します。
公共  int優先度( intオペランド) {
        演算子 == '*' || 演算子 == '/'の場合{
 1 を返します。
        }そうでない場合 (oper == '+' || oper == '-' ) {
 0を返します。
        }それ以外{
 -1 を返します。
        }
    } 
 
    // 演算子かどうかをチェックする
パブリックブールisOper( char val) {
 val == '+' || val == '-' || val == '*' || val == '/'を返します。
    } 
 
    //計算方法
公共  int cal( int num1, int num2, int oper) {
整数res = 0;
        スイッチ（オペランド）{
場合  '+' :
                数値1と数値2
                壊す;
場合  '-' :
                res = num2 - num1; //順序に注意
                壊す;
場合  '*' :
                数値1と数値2を合計します。
                壊す;
場合  '/' :
                res = num2 / num1; //順序に注意
                壊す;
        }
 resを返します。
    }
 }