데이터 구조 - 배열 시 뮬 레이 션 구현 대기 열

1. 대열 소개
대열 은 하나의 로 배열 이나 링크 로 이 루어 질 수 있 으 며 원칙 을 따른다.
2. 배열 시 뮬 레이 션 구현 대기 열
2.1 사고방식
대기 열 자체 에 서열 표 가 있 습 니 다. 배열 의 구 조 를 사용 하여 대기 열의 데 이 터 를 저장 하면:

이 대기 열의 최대 용량 maxSize 으로 설정

대기 열의 입 출력 은 각각 앞 뒤 에서 처리 되 기 때문에 head 과 tail 대기 열의 앞 뒤 단 하 표를 각각 기록 해 야 합 니 다. head 는 데이터 의 출력 에 따라 달라 집 니 다. tail 은 데이터 의 입력 에 따라 달라 집 니 다

tail = = maxSize - 1 시 대기 열 이 가득 찼 습 니 다

2.2. 코드 구현

//      
class ArrayQueue{
    //        
    private int maxSize;
    //   
    private int head;
    //   
    private int tail;
    //      
    private int[] arr;

    //        
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        //            
        head = -1;
        //             
        tail = -1;
    }

    //       
    //   true，    false
    public boolean isFull(){
        return tail == maxSize - 1;
    }

    //         ，      
    //   true，    false
    public boolean isEmpty(){
        return tail == head;
    }

    //       
    public void addQueue(int data){
        //  
        if(isFull()){
            System.out.println("    ");
            return;
        }
        //tail  
        tail ++;
        arr[tail] = data;
    }

    //      
    public int getData(){
        //  
        if(isEmpty()){
            //         ,throw       return
            throw new RuntimeException("    ");
        }
        head ++;
        return arr[head];
    }

    //        
    public void showQueue(){
        //  
        if(isEmpty()){
            System.out.println("    ");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%d ",arr[i]);
        }
    }

    //      
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("    ");
        }
        return arr[head + 1];
    }
}

2.3. 문제 분석 과 해결

문제: 현재 실현 되 고 있 는 방법 배열 은 한 번 사용 하면 재 활용 할 수 없다

해결: 배열 의 사용 알고리즘 을 링 배열 로 개선 (모델 링 방식)

3. 링 배열 이 대기 열 을 실현 합 니 다 (배열 이 대기 열의 최적화 실현)
3.1 사고방식

헤드 변수의 의 미 를 조정 합 니 다. 헤드 가 대열 을 가리 키 는 첫 번 째 요소 입 니 다. 즉, arr [head] 는 대열 의 첫 번 째 요소 이 고 헤드 의 초기 값 은 0

입 니 다.

tail 변수의 의 미 를 조정 합 니 다. tail 은 대기 열의 마지막 요 소 를 가리 키 는 다음 위치 (한 공간 을 비 워 서 약속 하 기 를 바 랍 니 다), tail 의 초기 값 은 0

입 니 다.

대기 열 이 가득 찼 을 때 (tail + 1)% max Size = head

대기 열 이 비어 있 을 때 tail = = head

대기 열 에서 유효한 데이터 개수: (tail + maxSize - front)% maxSize

3.2 코드 구현

class CircleArray{
    //        
    private int maxSize;
    //   
    private int head;
    //   
    private int tail;
    //      
    private int[] arr;

    public CircleArray(int arrayMaxSize){
        maxSize = arrayMaxSize;
        arr = new int[maxSize];
        //            
        head = 0;
        //             
        tail = 0;
    }

    //       
    //   true，    false
    public boolean isFull(){
        return (tail + 1) % maxSize == head;
    }

    //         ，      
    //   true，    false
    public boolean isEmpty(){
        return tail == head;
    }

    //       
    public void addQueue(int data){
        //  
        if(isFull()){
            System.out.println("    ");
            return;
        }
        //       
        arr[tail] = data;
        // tail  
        tail = (tail + 1) % maxSize;
    }

    //      
    public int getData(){
        //  
        if(isEmpty()){
            //         ,throw       return
            throw new RuntimeException("    ");
        }
        //      head           
        //  head             
        //head  
        //      
      int value = arr[head];
        head = (head + 1) % maxSize;
        return value;
    }

    //            
    public int size(){
        return (tail + maxSize - head) % maxSize;
    }

    //        
    public void showQueue(){
        //  
        if(isEmpty()){
            System.out.println("    ");
            return;
        }
        // head    
        for (int i = head; i < head + size(); i++) {
            System.out.printf("%d ",arr[i % maxSize]);
        }
    }

    //      
    public int headQueue(){
        if(isEmpty()){
            throw new RuntimeException("    ");
        }
        return arr[head];
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[JAVA] 배열 회전 출력

요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

데이터 구조 - 배열 시 뮬 레이 션 구현 대기 열

좋은 웹페이지 즐겨찾기