큐(queue) 구현해보기

큐(queue)

•  선입선출(FIFO: First In First Out)의 구조를 갖는 자료구조이다.

// 배열을 이용한 원형 큐 구현하기

public class RingQueue {
    private int[] que; // 큐용 배열
    private int capacity; // 큐 용량
    private int front; // 맨 앞의 요소의 인덱스
    private int rear; // 맨 뒤의 요소에서 하나 뒤 인덱스(인큐할 때 저장될 요소의 인덱스를 미리 준비)
    private int num; // 현재 데이터 개수
    // front와 rear 값이 같을 때 큐가 비어있는지, 가득찼는지 구분하기 위해 만든 변수

    // 실행 시 예외 : 큐가 비어있는 경우
    public class EmptyQueueException extends RuntimeException {
        public EmptyQueueException() {}
    }

    // 실행 시 예외 : 큐가 가득 찬 경우
    public class OverflowQueueException extends  RuntimeException {
        public OverflowQueueException() {}
    }

    // 생성자 메서드
    public RingQueue(int maxlen){
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = new int[capacity]; // 큐용 배열 생성
        } catch (OutOfMemoryError e) { // 생성할 수 없는 경우
            capacity = 0; // capacity를 0으로 하여 다른 메서드가 존재하지 않는 배열 que에 잘못 접근하는 것을 막는다.
        }
    }

    // enque() 메서드 생성
    public int enque(int x) throws OverflowQueueException { // 메서드 오류 발생시 호출한 곳으로 예외 떠넘기기
        if (num >= capacity) throw new OverflowQueueException() {}; // 큐가 가득차서 enque할 수 없을 경우에 예외를 발생시킴
        que[rear++] = x; // 현재 rear에 해당하는 인덱스에 x를 넣고, rear를 1 증가시킴
        num++; // 현재 데이터 개수 1 증가
        return x; // 큐에 전달받은 x를 넣은 그대로 리턴
    } //

    // deque() 메서드 생성
    public int deque() throws  EmptyQueueException { // 메서드 오류 발생시 호출한 곳으로 예외 떠넘기기
        if (num <= 0) throw new EmptyQueueException(); // 큐가 비어있어 deque할 수 없을 경우에 예외를 발생시킴
        int x = que[front++]; // 현재 front에 있는 데이터를 변수에 넣음
        num--; // 데이터 개수 1 감소
        if (front == capacity) front = 0; // 만약 front가 인덱스 끝에 있다면, 원형 큐이므로 0으로 돌아옴
        return x; // 삭제한 데이터를 리턴
        // 실제 값을 삭제할 필요없이 enque를 할 경우 num, front, rear를 기준으로 값을 넣기 때문에 새로운 값이 들어오면 그 값으로 자연스레 대체된다.
    }

    // peek() 메서드 생성
    public int peek() throws EmptyQueueException { // 메서드 오류 발생시 호출한 곳으로 예외 떠넘기기
        if (num <= 0) throw new EmptyQueueException(); // 큐가 비어있어 peek할 수 없을 경우에 예외를 발생시킴
        return que[front]; // 가장 최근에 들어간 값을 보여준다.
    }

    // clear() 메서드 생성
    public void clear() {
        num = front = rear = 0;
        // 실제 값을 삭제할 필요없이 enque를 할 경우 num, front, rear를 기준으로 값을 넣기 때문에 새로운 값이 들어오면 그 값으로 자연스레 대체된다.
    }

    // indexOf 메서드 생성
    public int indexOf(int x) {
       for (int i = 0; num > i; i--) {
           int idx = (i + front) % capacity; // front부터 올라가 인덱스 끝에 도착하면 0부터 탐색함(원형 큐를 보고 뇌코딩 해보면 이해가능)
           if (que[idx] == x) return idx; // 검색값이 있으면 해당 인덱스 리턴
       }
       return -1; // 검색 실패 시 -1 반환
    }

    // getCapacity 메서드 생성
    public int getCapacity() { // 큐의 용량 확인
        return capacity;
    }

    // size 메서드 생성
    public int size() { // 큐의 데이터 개수 확인
        return num;
    }

    // isEmpty 메서드 생성
    public boolean isEmpty() { // 큐가 비어있는지 확인
        return num <= 0;
    }

    //isFull 메서드 생성
    public boolean isFull() { // 큐가 가득 찼는지 확인
        return capacity <= num; // 큐가 가득차면 num과 capacity가 같아지지만, 프로그램의 오류 등을 고려하여 <=를 사용(안정성 증가)
    }

    //dump() 메서드 생성
    public void dump() { // que의 front부터 rear 순으로 출력
        if (num <= 0) {
            System.out.println("큐가 비어 있습니다.");
        }
        else {
            for (int i = 0; num > i; i--) {
                System.out.println(que[(i + front) % capacity] + " "); // front부터 올라가 인덱스 끝에 도착하면 0부터 시작
            }
            System.out.println();
        }
    }
}