Programmeurs, la pile de structures de données que vous devez connaître

La pile dans la structure de données ne doit pas être confondue avec la pile en Java. Ce n'est pas la même chose. La pile dans la structure de données est une liste linéaire restreinte. une caractéristique avancée de sortie, dernier entré, premier sorti, car la pile ne permet d'accéder qu'à la dernière donnée, c'est-à-dire à la dernière donnée insérée. Peut-être avez-vous des questions, puisque la pile a de nombreuses limitations, pourquoi ne pas utiliser un tableau ou une liste chaînée au lieu d'une pile ? En développement, nous avons des scénarios spécifiques et nous choisissons les structures de données en fonction de scénarios spécifiques. Il existe de nombreux scénarios applicables pour les piles, tels que le navigateur avant et arrière, la légalité des crochets de chaîne, etc. , car la pile fournit beaucoup moins d'interfaces externes que les tableaux et les listes chaînées, la probabilité d'erreurs est réduite et la contrôlabilité des risques est améliorée.

Tutoriels recommandés : Tutoriel vidéo PHP

Implémenter un Pile

Comme le montre la définition de la pile, la pile a principalement deux opérations, l'une consiste à ajouter une donnée, que nous appelons pousser, et l'autre consiste à obtenir une donnée, appelée Pop the stack. Les deux images suivantes sont des diagrammes schématiques de poussée et d'éclatement de la pile.

Il existe deux façons d'implémenter la pile, l'une est basée sur des tableaux, nous l'appelons une pile séquentielle et l'autre est Implémenté sur la base d'une liste chaînée, nous l'appelons une pile liée. Voici le code d'implémentation des deux piles

Pile séquentielle basée sur un tableau

/**
 * 基于数组的顺序栈
 */
 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;
    }
}

Pile liée basée sur une liste chaînée

/**
 * 基于链表的链式栈
 */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;
        }
    }
}

La mise en œuvre de la pile est relativement simple, car la pile n'implique pas beaucoup d'opérations, principalement deux opérations : push et pop.

Application Stack

Détecter la légalité des crochets de chaîne

Parfois, nous devons détecter la légalité des parenthèses de chaîne, c'est-à-dire qu'une parenthèse gauche doit correspondre à une parenthèse droite. Nous pouvons utiliser la pile pour y parvenir. On peut comprendre pourquoi le stack est utilisé à partir d'une tranche légale ? Si les parenthèses sont utilisées légalement, la dernière parenthèse gauche correspond à la première parenthèse droite, l'avant-dernière parenthèse gauche correspond à la deuxième parenthèse droite, et ainsi de suite. Ceci est conforme à la fonctionnalité premier entré, dernier sorti de notre pile.

Supposons que nous ayons trois types de parenthèses : les parenthèses rondes (), les crochets [] et les accolades {}. Nous utilisons la pile pour vérifier la validité des parenthèses. Nous plaçons toutes les parenthèses gauches sur la pile, et lorsqu'une parenthèse droite apparaît, nous effectuons une correspondance. À ce moment, il y a trois situations :

La pile est vide, ce qui indique qu'il n'y a pas de parenthèse gauche et. l'utilisation de parenthèses est illégale

●La parenthèse gauche retirée de la pile ne correspond pas à la parenthèse droite, et l'utilisation de parenthèses est illégale

●La parenthèse gauche retirée de la pile correspond au bon support, et l'utilisation de crochets est temporairement légale

Quand Une fois la chaîne entière analysée, vérifiez s'il y a encore une valeur dans la pile. Si la pile est vide, cela signifie que l'utilisation de. Les parenthèses sont légales. Quoi qu'il en soit, l'utilisation de parenthèses est illégale.

Code d'implémentation

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();
}

Fonctions avant et arrière du navigateur

Nous utilisons tous des navigateurs Vous savez , le navigateur peut avancer et reculer, et les fonctions avant et arrière du navigateur sont également conformes aux caractéristiques de la pile. La page Web que nous visitons en premier doit être la dernière à laquelle revenir. Voyons comment la pile implémente cette fonction ?

Nous devons définir deux piles. Nous poussons la page visitée pour la première fois dans la première pile. Lorsque nous cliquons en arrière, nous prenons les données de la première pile et les mettons dans la deuxième pile. est cliqué sur le bouton Suivant, les données sont extraites de la deuxième pile et placées dans la première pile. Lorsqu'il n'y a pas de données dans la première pile, cela signifie qu'il n'y a pas de page sur laquelle cliquer pour revenir en arrière. Lorsqu'il n'y a pas de données dans la deuxième pile, cela signifie qu'il n'y a pas de page sur laquelle cliquer pour avancer. De cette façon, nous implémentons les fonctions avant et arrière du navigateur via la pile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!