プログラマ、知っておくべきデータ構造スタック

データ構造内のスタックを Java のスタックと混同しないでください。これらは同じものではありません。データ構造内のスタックは、制限された線形リストです。スタックには次のものがあります。スタックは最後のデータ項目、つまり最後に挿入されたデータ項目へのアクセスのみを許可するため、高度な Out、後入れ先出しの特性。スタックには多くの制限があるため、なぜスタックの代わりに配列またはリンク リストを使用しないのかという疑問があるかもしれません。開発では、特定のシナリオがあり、特定のシナリオに従ってデータ構造を選択します。スタックには、ブラウザの前後方向、文字列括弧の正当性など、適用可能なシナリオが多数あります。スタックを使用する方が良いでしょう。スタックが提供する外部インターフェイスの数が配列やリンク リストよりもはるかに少ないため、 を実装すると、インターフェイスの数が少なくなり、エラーの可能性が減り、リスクの制御性が向上します。

推奨チュートリアル: PHP ビデオ チュートリアル

実装してみようスタック

スタックの定義からわかるように、スタックには主に 2 つの操作があります。1 つはデータの追加 (プッシュと呼ばれます) で、もう 1 つはデータの追加です。次の 2 つの図は、スタックのプッシュとポップの概略図です。

スタックを実装するには 2 つの方法があります。1 つは配列の実装に基づくもので、これをシーケンシャル スタックと呼びます。もう 1 つはリンクされたリストに基づいて実装されるため、これをリンク スタックと呼びます。以下は 2 つのスタックの実装コードです。

配列ベースのシーケンシャル スタック

/**
 * 基于数组的顺序栈
 */
 public class ArrayStack {    // 栈最大容量
    private int maxSzie;    // 存放内容
    private String[] array;    // 栈顶元素
    private int top;    
    public ArrayStack(int size){      
      this.maxSzie = size;        
      this.array = new String[this.maxSzie];        
      this.top = 0;
    }  
      /**
     * 入栈操作
     *
     * @param data 数据
     * @return 0：入栈失败 1：入栈成功
     */
    public int push(String data) {      
      if (top == maxSzie) return 0;
        array[top] = data;
        top++;        
        return 1;
    }    
    /**
     * 出栈操作
     *
     * @return
     */
    public String pop() {     
       if (top == 0) return null;        
       return array[--top];
    }    
    /**
     * 获取栈顶元素
     *
     * @return
     */
    public String peek() {     
       return array[top - 1];
    }    
    /**
     * 判断栈是否为空
     * @return
     */
    public boolean isEmpty() {    
        return top == 0;
    }
}

リンク リストに基づくリンク スタック

/**
 * 基于链表的链式栈
 */public class LinkStack {    // 始终指向栈的第一个元素
    private Node top = null;    
    /**
     * 压栈
     *
     * @param data
     * @return
     */
    public int push(String data) {
        Node node = new Node(data);        
        if (top == null) {
            top = node;
        } else {
            node.next = top;
            top = node;
        }       
         return 1;
        }   
     /**
     * 出栈
     *
     * @return
     */
    public String pop() {     
       if (top == null) return null;
        String data = top.getData();
        top = top.next;       
         return data;
    }   
     /**
     * 节点信息
     */
    private static class Node {      
      private String data;      
      private Node next;        
      public Node(String data) {        
          this.data = data;          
          this.next = null;
        }       
      public String getData() {          
        return this.data;
        }
    }
}

スタックに関与する操作はそれほど多くなく、主にプッシュとポップの 2 つの操作であるため、スタックの実装は比較的単純です。

#スタックの適用

文字列括弧の正当性の検出

場合によっては、文字列括弧の正当性、つまり、左括弧が右括弧と一致する必要があるかどうかを検出する必要があることがあります。スタックを使用してこれを実現できます。なぜスタックが合法的な括弧から使用されるのか理解できますか?括弧が合法的に使用されている場合、最後の左括弧は最初の右括弧と一致し、最後から 2 番目の左括弧は 2 番目の右括弧と一致し、以下同様になります。これは、スタックの先入れ後出し機能と一致しています。

丸括弧 ()、角括弧 []、中括弧 {} の 3 種類の括弧があるとします。スタックを使用して括弧の有効性をチェックします。すべての左括弧をスタックにプッシュし、右括弧が現れたら照合を実行します。このとき、次の 3 つの状況があります。括弧の使用は不正です

●スタックから取り出した左括弧は右括弧と一致せず、括弧の使用は不正です

●スタックから取り出した左括弧は右括弧と一致し、括弧の使用は一時的に有効です

When 文字列全体がスキャンされた後、スタックにまだ値があるかどうかを確認します。スタックが空の場合は、いずれにせよ、括弧の使用は違法です。

実装コード

public static boolean BracketChecker(String data) {
    char[] chars = data.toCharArray();
    ArrayStack stack = new ArrayStack(chars.length);    
    for (char ch : chars) {
            switch (ch){
                        case '{':            
                        case '[':            
                        case '(':
                                stack.push(ch);                
                                break;            
                         case '}':            
                         case ']':            
                         case ')':             
                                if (!stack.isEmpty()){                 
                                   char ch1 = stack.pop();                    
                                   if ((ch=='}' && ch1 !='{')
                                        ||(ch==']' && ch1 !='[')
                                        ||(ch==')' && ch1 !='(')

                    ){                 
                           return false;
                    }
                }else {    
                           return false;
                }     
                break;            
        default:            
            break;
        }
    }   
    return stack.isEmpty();
}

ブラウザの進む関数と戻る関数

私たちは皆、ブラウザを使用しています。 、ブラウザは前後に移動でき、ブラウザの進む機能と戻る機能もスタックの特性と一致しています。最初にアクセスした Web ページは、最後に戻る必要があります。スタックがこの関数をどのように実装しているかを見てみましょう。

2 つのスタックを定義する必要があります。初めて訪問したページを最初のスタックにプッシュします。戻るをクリックすると、最初のスタックからデータを取得して 2 番目のスタックに置きます。 「進む」ボタンをクリックすると、データが 2 番目のスタックから取得され、最初のスタックに配置されます。最初のスタックにデータがない場合は、戻るためにクリックするページがないことを意味し、2 番目のスタックにデータがない場合は、クリックして進むページがないことを意味します。このようにして、スタックを介してブラウザの進む機能と戻る機能を実装します。

以上がプログラマ、知っておくべきデータ構造スタックの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。