Programmers, the data structure stack you should know

The stack in the data structure should not be confused with the stack in Java. They are not the same thing. The stack in the data structure is a restricted linear list. The stack has an advanced Out, last in first out characteristics, because the stack only allows access to the last data item, that is, the last inserted data item. Maybe you have questions, since the stack has so many limitations, why not use an array or linked list instead of a stack? In development, we have specific scenarios, and we choose data structures according to specific scenarios. There are many applicable scenarios for stacks, such as browser forward and backward, the legality of string brackets, etc. It is better for us to use stacks to implement , because the stack provides much fewer external interfaces than arrays and linked lists. With fewer interfaces, the probability of errors is reduced, and the controllability of risks is improved.

Recommended tutorial: PHP video tutorial

Implement one Stack

As can be seen from the definition of the stack, the stack mainly has two operations, one is to add a piece of data, which we call pushing, and the other is to obtain a piece of data, which is called Pop the stack. The following two pictures are schematic diagrams of pushing and popping the stack.

There are two ways to implement the stack. One is based on array implementation, which we call a sequential stack. The other is Implemented based on a linked list, we call it a linked stack. The following is the implementation code of the two stacks

Array-based sequential stack

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

Linked stack based on linked list

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

The implementation of the stack is relatively simple, because there are not many operations involved in the stack, mainly two operations: push and pop.

Application of stack

Detect the legality of string brackets

Sometimes we need to detect the legality of string brackets, that is, a left bracket needs to match a right bracket. We can use the stack to achieve this. We can understand why the stack is used from a legal bracket? If the brackets are used legally, the last left bracket matches the first right bracket, the penultimate left bracket matches the second right bracket, and so on. This is in line with the first-in-last-out feature of our stack.

Suppose we have three kinds of brackets: round brackets (), square brackets [] and curly brackets {}. We use the stack to check the validity of the brackets. We push all left brackets onto the stack, and when a right bracket appears, we perform a match. At this time, there are three situations:

●The stack is empty, indicating that there is no left bracket and the use of brackets is illegal

　●The left bracket taken out from the stack does not match the right bracket, and the use of brackets is illegal

●The left bracket taken out from the stack matches the right bracket, and the use of brackets is temporarily legal

When After the entire string is scanned, check whether there is still a value in the stack. If the stack is empty, it means that the use of brackets is legal. Anyway, the use of brackets is illegal.

Implementation code

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 forward and backward functions

We all use browsers You know, the browser can move forward and backward, and the browser's forward and backward functions are also in line with the characteristics of the stack. The web page we visit first must be the last one to go back to. Let’s take a look at how the stack implements this function?

We need to define two stacks. We push the page visited for the first time into the first stack. When we click back, we take the data from the first stack and put it into the second stack. When the forward button is clicked, data is taken from the second stack and placed into the first stack. When there is no data in the first stack, it means that there is no page to click to go back. When there is no data in the second stack, it means that there is no page to click to go forward. In this way, we implement the browser forward and backward functions through the stack.

The above is the detailed content of Programmers, the data structure stack you should know. For more information, please follow other related articles on the PHP Chinese website!