프로그래머, 당신이 알아야 할 데이터 구조 스택

데이터 구조의 스택은 Java의 스택과 혼동되어서는 안 됩니다. 데이터 구조의 스택은 제한된 선형 목록입니다. 왜냐하면 스택은 마지막으로 삽입된 데이터 항목인 마지막 데이터 항목에만 액세스할 수 있기 때문입니다. 어쩌면 질문이 있을 수도 있습니다. 스택에는 너무 많은 제한이 있으므로 스택 대신 배열이나 연결 목록을 사용하는 것은 어떨까요? 개발 중에는 특정 시나리오가 있으며 특정 시나리오에 따라 데이터 구조를 선택합니다. 브라우저 앞으로 및 뒤로, 문자열 괄호의 적법성 등과 같은 스택에 적용 가능한 시나리오가 많이 있습니다. 스택은 배열 및 연결 목록보다 훨씬 적은 수의 외부 인터페이스를 제공하므로 오류 가능성이 줄어들고 위험 제어 가능성이 향상됩니다.

추천 튜토리얼: PHP 비디오 튜토리얼

스택 구현

스택의 정의에서 스택에는 두 가지 주요 작업이 있음을 알 수 있습니다. 하나는 데이터 조각을 푸싱이라고 하고, 다른 하나는 데이터 조각을 얻는 것인데, 이를 팝핑이라고 합니다. 다음 두 그림은 푸시와 팝의 개략도입니다.

스택을 구현하는 방법에는 두 가지가 있습니다. 하나는 배열을 기반으로 하는 순차 스택이고 다른 하나는 연결된 목록을 기반으로 하는 체인 스택입니다. 다음은 두 스택의 구현 코드입니다.

배열 기반 순차 스택

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

스택 구현은 상대적으로 간단합니다. 스택에는 많은 작업이 포함되지 않으며 주로 푸시와 팝이라는 두 가지 작업이 포함됩니다.

스택 적용

문자열 괄호의 합법성 감지

때때로 문자열 괄호의 합법성을 감지해야 합니다. 즉, 왼쪽 괄호는 오른쪽 괄호와 일치해야 합니다. 대괄호, 이를 달성하기 위해 스택을 사용할 수 있습니다. 스택이 법적 괄호에서 사용되는 이유를 이해할 수 있습니까? 대괄호가 합법적으로 사용되는 경우 마지막 왼쪽 대괄호는 첫 번째 오른쪽 대괄호와 일치하고 끝에서 두 번째 왼쪽 대괄호는 두 번째 오른쪽 대괄호와 일치하며 이는 스택의 선입 후 출력 기능과 일치합니다.

　 대괄호(), 대괄호 [], 중괄호 {}의 세 가지 유형의 괄호가 있다고 가정합니다. 우리는 대괄호의 유효성을 확인하기 위해 스택을 사용합니다. 왼쪽 괄호를 모두 스택에 밀어 넣고 오른쪽 괄호가 나타나면 일치를 수행합니다. 이때 세 가지 상황이 있습니다.

　● 스택이 비어 있어 왼쪽 괄호가 없음을 나타냅니다. 괄호는 불법입니다

　●스택에서 제거됨 왼쪽 괄호가 오른쪽 괄호와 일치하지 않아 괄호 사용이 불법입니다

●스택에서 꺼낸 왼쪽 괄호가 오른쪽 괄호와 일치하여 일시적으로 괄호 사용이 금지됩니다 legal

전체 문자열을 스캔할 때 스택에 값이 남아 있는지 확인하세요. 스택이 비어 있으면 괄호 사용이 허용됩니다. 어쨌든 괄호 사용은 불법입니다.

구현 코드

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

브라우저의 앞으로 및 뒤로 기능

우리 모두는 브라우저가 앞으로 및 뒤로 기능을 할 수 있다는 것을 알고 있으며, 브라우저의 앞으로 및 뒤로 기능도 스택의 특성과 일치합니다. 처음 방문한 웹페이지는 다시 돌아갈 수 있는 마지막 웹페이지여야 합니다. 스택이 이 기능을 어떻게 구현하는지 살펴보겠습니다.

　 두 개의 스택을 정의해야 합니다. 처음 방문한 페이지를 첫 번째 스택에 푸시합니다. 뒤로를 클릭하면 첫 번째 스택에서 데이터를 가져와 두 번째 스택에 넣습니다. , 두 번째 스택에서 데이터를 가져와 첫 번째 스택에 넣습니다. 첫 번째 스택에 데이터가 없으면 뒤로 가기 위해 클릭할 페이지가 없다는 뜻이고, 두 번째 스택에 데이터가 없으면 클릭해서 앞으로 이동할 페이지가 없다는 의미입니다. 이러한 방식으로 스택을 통해 브라우저의 앞으로 및 뒤로 기능을 구현합니다.

위 내용은 프로그래머, 당신이 알아야 할 데이터 구조 스택의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!