Programmierer, der Datenstruktur-Stack, den Sie kennen sollten

Der Stapel in der Datenstruktur sollte nicht mit dem Stapel in Java verwechselt werden. Sie sind nicht dasselbe. Der Stapel in der Datenstruktur ist eine eingeschränkte lineare Liste verfügt über erweiterte Out- und Last-In-First-Out-Eigenschaften, da der Stapel nur den Zugriff auf das letzte Datenelement ermöglicht, dh auf das zuletzt eingefügte Datenelement. Vielleicht haben Sie Fragen, warum nicht ein Array oder eine verknüpfte Liste anstelle eines Stapels verwenden, da der Stapel so viele Einschränkungen hat? In der Entwicklung haben wir bestimmte Szenarien und wählen Datenstrukturen entsprechend bestimmten Szenarien aus. Es gibt viele anwendbare Szenarien für den Browser, z. B. die Vorwärts- und Rückwärtsbewegung des Browsers, die Rechtmäßigkeit von Zeichenfolgenklammern usw. Es ist für uns besser, Stapel zu verwenden Implementierung, da der Stack viel weniger externe Schnittstellen bereitstellt als Arrays und verknüpfte Listen. Durch weniger Schnittstellen wird die Fehlerwahrscheinlichkeit verringert und die Kontrollierbarkeit von Risiken verbessert.

Empfohlene Tutorials: PHP-Video-Tutorial

Implementieren Sie eins Stapel

Wie aus der Definition des Stapels ersichtlich ist, verfügt der Stapel hauptsächlich über zwei Operationen: Eine besteht darin, ein Datenelement hinzuzufügen, was wir Pushen nennen, und die andere darin Erhalten Sie ein Datenelement, das als „Stapel platzen“ bezeichnet wird. Die folgenden beiden Bilder sind schematische Diagramme zum Schieben und Platzieren des Stapels.

Es gibt zwei Möglichkeiten, den Stapel zu implementieren: Die eine basiert auf Arrays, wir nennen sie einen sequentiellen Stapel, und die andere ist es Basierend auf einer verknüpften Liste implementiert, nennen wir es einen verknüpften Stapel. Das Folgende ist der Implementierungscode der beiden Stapel

Array-basierter sequentieller Stapel

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

Verknüpfter Stapel basierend auf verknüpfter Liste

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

Die Implementierung des Stapels ist relativ einfach, da der Stapel nicht viele Operationen umfasst, hauptsächlich zwei Operationen: Push und Pop.

Stack-Anwendung

Erkennen Sie die Rechtmäßigkeit von Zeichenfolgenklammern

Manchmal müssen wir die Rechtmäßigkeit von Zeichenfolgenklammern überprüfen, das heißt, eine linke Klammer muss mit einer rechten Klammer übereinstimmen. Wir können den Stapel verwenden, um dies zu erreichen. Können wir verstehen, warum der Stapel aus rechtlicher Sicht verwendet wird? Wenn die Klammern legal verwendet werden, entspricht die letzte linke Klammer der ersten rechten Klammer, die vorletzte linke Klammer entspricht der zweiten rechten Klammer und so weiter. Dies steht im Einklang mit der First-In-Last-Out-Funktion unseres Stapels.

Angenommen, wir haben drei Arten von Klammern: runde Klammern (), eckige Klammern [] und geschweifte Klammern {}. Wir verwenden den Stapel, um die Gültigkeit der Klammern zu überprüfen. Wir schieben alle linken Klammern auf den Stapel. Zu diesem Zeitpunkt gibt es drei Situationen: ●Der Stapel ist leer, was darauf hinweist, dass keine linke Klammer vorhanden ist von Klammern ist illegal

●Die aus dem Stapel entnommene linke Klammer stimmt nicht mit der rechten Klammer überein, und die Verwendung von Klammern ist illegal

●Die aus dem Stapel entnommene linke Klammer stimmt mit überein rechte Klammer, und die Verwendung von Klammern ist vorübergehend zulässig

Wenn nach dem Scannen der gesamten Zeichenfolge noch ein Wert im Stapel vorhanden ist, bedeutet dies, dass die Verwendung von Klammern zulässig ist Auf jeden Fall ist die Verwendung von Klammern illegal.

Implementierungscode

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

Browser-Vorwärts- und Rückwärtsfunktionen Wir alle verwenden Browser. Wissen Sie? , der Browser kann sich vorwärts und rückwärts bewegen, und die Vorwärts- und Rückwärtsfunktionen des Browsers stimmen auch mit den Eigenschaften des Stapels überein. Die Webseite, die wir zuerst besuchen, muss die letzte sein, zu der wir zurückkehren. Schauen wir uns an, wie der Stack diese Funktion implementiert.

Wir müssen die zum ersten Mal besuchte Seite in den ersten Stapel verschieben. Wenn wir zurückklicken, nehmen wir die Daten vom ersten Stapel und legen sie in den zweiten Stapel ab Wenn Sie auf die Schaltfläche „Weiter“ klicken, werden die Daten vom zweiten Stapel übernommen und im ersten Stapel abgelegt. Wenn der erste Stapel keine Daten enthält, bedeutet dies, dass es keine Seite gibt, auf die man klicken kann, um vorwärts zu gehen. Wenn der zweite Stapel keine Daten enthält, bedeutet dies, dass es keine Seite gibt, auf die man klicken kann, um vorwärts zu gehen. Auf diese Weise implementieren wir die Vorwärts- und Rückwärtsfunktionen des Browsers über den Stapel.

Das obige ist der detaillierte Inhalt vonProgrammierer, der Datenstruktur-Stack, den Sie kennen sollten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!