데이터 구조 (2): 스 택 과 대기 열

이 시 리 즈 는 데이터 구조 학습 노트 입 니 다. 오류 가 있 으 면 지적 해 주세요 ~
데이터 구조 (1): 배열 과 링크
이론 지식
스 택 과 대기 열 은 모두 선형 데이터 구조 로 논리 구조 에 속 하 며 물리 구조 (배열 과 링크) 에서 파생 된 것 이기 때문에 스 택 과 대기 열 은 배열 로 실현 할 수도 있 고 링크 로 실현 할 수도 있 으 며 두 가지 실현 방식 은 각종 우열 이다.
1. 창고
기본 개념

스 택 지붕: 마지막 으로 들 어 온 요소 가 저 장 된 위치

창고 바닥: 가장 먼저 들 어 온 원소 가 저 장 된 위치

먼저 들 어간 후에 나 옵 니 다 (First In Last Out, FILO): 예 를 들 어 12345 개의 숫자 가 순서대로 창고 에 들 어가 고 창고 에서 나 오 는 순 서 는 54321

입 니 다.

스 택 에 들 어가 기 (push): 새 요 소 를 스 택 에 넣 기

스 택 (pop): 스 택 에서 요 소 를 꺼 내 고 스 택 꼭대기 의 요소 만 스 택 에서 나 올 수 있 습 니 다. 스 택 요소 의 이전 요 소 는 새로운 스 택 꼭대기

가 됩 니 다.
코딩 실현 사고
배열 로 스 택 을 실현 합 니 다. 전체 스 택 의 작업 은 스 택 꼭대기 라 는 위치 에 있 는 요 소 를 조작 하 는 것 입 니 다. 스 택 에 들 어 갈 때 스 택 꼭대기 요 소 는 배열 의 새로운 요소 의 아래 표 로 변경 합 니 다.스 택 을 나 갈 때 스 택 상단 요 소 는 스 택 요소 의 이전 요소 의 배열 아래 표 시 됩 니 다.
배열 의 크기 가 일정 하기 때문에 경 계 를 넘 는 문제 에 주의해 야 한다.읽 을 때 비어 있 는 지, 삽입 할 때 꽉 찼 는 지 판단 합 니 다.
응용 장면
스 택 의 수출 순서 와 입력 순서 가 반대 되 기 때문에 스 택 은 보통 '역사' 에 대한 역 추적 에 사용 된다. 비교적 전형 적 인 응용 은 바로 빵 부스러기 내 비게 이 션 으로 앞의 단계 나 앞의 몇 단계 로 쉽게 거 슬러 올 라 갈 수 있다.
2. 대열
기본 개념

팀 헤드 (front): 대열 의 출구

팀 끝 (rear): 대열 의 입구

입단 (enqueue): 팀 끝의 위치 에 요소 만 넣 을 수 있 습 니 다

출 대 (dequeue): 팀 머리 쪽 에서 만 요 소 를 이동 할 수 있 습 니 다

먼저 들 어가 서 먼저 나 간다 (First In First Out, FIFO): 예 를 들 어 12345 가 순서대로 들 어 오고 나 가 는 순 서 는 12345

이다.
코딩 실현 사고
배열 로 대기 열 을 실현 합 니 다. 스 택 과 마찬가지 로 배열 에 대한 작업 으로 전 환 됩 니 다.스 택 과 달리 스 택 은 스 택 지붕 에 만 관심 을 가지 면 됩 니 다. 대열 은 '두 마리', 즉 팀 머리 와 팀 꼬리 에 관심 을 가 져 야 합 니 다. 나머지 실현 원 리 는 비슷 합 니 다.
창고 와 마찬가지 로 수조 의 크기 가 일정 하기 때문에 반드시 경 계 를 넘 는 문제 에 주의해 야 한다.읽 을 때 비어 있 는 지, 삽입 할 때 꽉 찼 는 지 판단 합 니 다.
응용 장면
파충 류 는 비교적 전형 적 인 응용 이 라 고 할 수 있다. 사 이 트 를 기어 올 라 갈 때 한 라인 으로 기어 올 라 갈 수 없고 여러 라인 으로 기어 올 라 갈 때 중복 기어 오 르 는 문 제 를 해결 해 야 한다.따라서 기어 오 를 url 을 대열 에 넣 고 대열 의 순서에 따라 순서대로 기어 올 라 갈 수 있다.
같은 이치 로 일부 다 중 스 레 드 응용 에서 다음 대기 열 을 고려 할 수 있다.
소스 코드
창고.

/**
 *    demo
 * @author yangjunqiang
 *
 */
public class MyStackDemo {

    //      
    private int[] stackArray;
    //          
    private int top;
    //     
    private int size;
    
    /**
     *    ，    
     * @param size
     */
    public MyStackDemo(int size) {
        this.size = size;
        this.stackArray = new int[size];
        //     , -1          
        this.top = -1;
    }
    
    /**
     *   
     * @param element
     * @return    
     */
    public int push(int element) {
        //          ，            
        if(isFull()) {
            throw new IndexOutOfBoundsException("   ");
        }
        //     ，             
        top += 1;
        stackArray[top] = element;
        return element;
    }
    
    /**
     *   
     * @return
     */
    public int pop() {
        //              
        if(isEmpty()) {
            throw new NoSuchElementException("  ,         ");
        }
        int element = stackArray[top];
        //   ，                 
        top -= 1;
        return element;
    }
    
    /**
     *    
     *           ，             
     */
    public void clear() {
        top = -1;
    }
    
    /**
     *     ，                
     * @return
     */
    public int size() {
        return size;
    }
    
    /**
     *        
     * @return
     */
    public boolean isEmpty() {
        return (top == -1);
    }
    
    /**
     *        
     * @return
     */
    public boolean isFull() {
        return (top == size - 1);
    }
}

대열

/**
 *     
 * @author yangjunqiang
 *
 */
public class MyQueueDemo {

    //       
    private int[] array;
    //     
    private int front;
    //     ，           ，                
    private int rear;
    
    /**
     *      ，      
     * @param size
     */
    public MyQueueDemo(int size) {
        this.array = new int[size];
    }
            
    public void enQueue(int element) throws Exception {
        if(isFull()) {
            throw new Exception("    ");
        }
        
        array[rear] = element;
        //       ，    ，                    ，          ，                
        //        ，               ，      ，       
        rear = (rear + 1) % array.length;
    }
    
    public int deQueue() throws Exception {
        if(isEmpty()) {
            throw new Exception("    ");
        }
        //    ，  
        int deQueueElement = array[front];
        //        
        front = (front + 1) % array.length;
        return deQueueElement;
    }
    
    public void printf() {
        for(int i = front; i != rear; i = (i + 1) % array.length) {
            System.out.println(array[i]);
        }
    }
    
    /**
     *         ，         。
     *         ，      ：（     + 1） %      =     
     * @return
     */
    public boolean isFull() {
        return ((rear + 1) % array.length == front);
    }
    
    /**
     *         
     *   =  
     */
    public boolean isEmpty() {
        return (rear == front);
    }
    
}