링 큐 대기 열

링 큐 대기 열
배열 대기 열 을 재 활용 할 수 없 는 문 제 를 해결 하기 위해 서 입 니 다.사용 하 는 사고방식 은 모델 링 이다.% 는 이전의 queue 에 비해 사고방식 이 바 뀌 었 다.현재 rear: rear 는 대기 열의 마지막 요소 의 다음 위 치 를 가리 키 고 있 습 니 다. 현재 의 front: front 를 약속 하기 위해 하나의 공간 을 비 워 두 기 를 원 하기 때 문 입 니 다. 즉, arr [front] 는 대기 열의 첫 번 째 요소 입 니 다. 그들의 초기 값 은 현재 0 으로 설정 되 어 있 습 니 다.rear 는 다음 요소 이 고 front 는 첫 번 째 요소 이기 때문에 초기 값 은 0 입 니 다.이전의 정상 적 인 대기 열, rear 는 현재 요소 이 고 front 는 첫 번 째 요소 의 이전 요소 이기 때문에 초기 값 은 - 1 입 니 다.

대기 열 이 가득 찬 조건 은: (rear + 1)% MaxSize = = front / / (real + 1) 마지막 요 소 는 real 에 있 습 니 다. 생각 은 항상 하나의 요 소 를 비 우 는 것 이기 때문에 + 1 모드 가 같 을 때 대기 열 이 가득 합 니 다

.

대기 열 이 비어 있 는 조건 은: rear = front 입 니 다.   //초기 에 같 았 고 대기 열 이 비 었 습 니 다

대기 열의 실제 유효 개 수 는: (rear + MaxSize - front)% MaxSize

코드 구현:

//               ArrayQueue
class circleArray{
    private int MaxSize;   //      
    private int front;     //   
    private int rear;      //    
    private  int[] arr;    //         ，    

    //        
    public circleArray(int arrMaxSize)
    {
        MaxSize=arrMaxSize;
        arr=new int[MaxSize];
        //front           ： front            ,      arr[front]           
        //front      = 0
        front=0;
        //rear           ：rear                  .               .
        //rear      = 0
        rear=0;
    }

    //       
    public boolean issFull(){
        return (rear+1)%MaxSize==front;
    }

    //        
    public boolean issEmpty(){
        return rear==front;
    }

    //       
    public void addQueue(int n)
    {
        //       
        if (issFull())
        {
            System.out.println("   ，      ");
            return;
        }
        //       
        arr[rear]=n;
        // rear  ，               
        rear=(rear+1)%MaxSize;
    }

    //       ，   
    public int getQueue()
    {
        //       
        if (issEmpty())
        {
            //     
            throw new RuntimeException("    ");
        }
        //       front           
        //1.  front           
        //2. front  
        //3.          
        int value=arr[front];
        front= (front+1)%MaxSize;      
        return value;
    }

    //         
    public void showQueue(){
        if (issEmpty())
        {
            System.out.println("    ");
            return;
        }
        //  ： front    ，       
        //(rear+maxsize-front)%maxsize
        for (int i=front;i<front+size();i++)
        {
            System.out.print("a["+i%MaxSize+"]:"+arr[i % MaxSize]+" ");
        }
        System.out.println();
    }
    //           
    public int size(){
        return (rear+MaxSize-front)%MaxSize;
    }
    //        ,     
    public int headQueue(){
        if (issEmpty())
        {
            System.out.println("    ");
            throw new RuntimeException("    ");
        }
        return arr[front];
    }
}

다음 코드 로 조작 할 수 있 습 니 다:

        circleArray queue = new circleArray(4);   //   4，         3
        char key = ' '; //      
        Scanner scanner = new Scanner(System.in);//
        boolean loop = true;
        //      
        while(loop) {
            System.out.println("s(show):     ");
            System.out.println("e(exit):     ");
            System.out.println("a(add):        ");
            System.out.println("g(get):        ");
            System.out.println("h(head):         ");
            key = scanner.next().charAt(0);//      
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("     ");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //    
                    try {
                        int res = queue.getQueue();
                        System.out.printf("      %d
", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //        
                    try {
                        int res = queue.headQueue();
                        System.out.printf("       %d
", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //  
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }

        System.out.println("    ~~");