[자료구조] Circular Queue (원형큐) 구현 - 자바(JAVA)

원형큐

 

백준 알고리즘 사이트에서 자료구조 분류에 있는 1158번 요세푸스 순열 문제를 풀면서 원형큐를 만들어 봤다.

 

원형큐는 FIFO 구조인 큐를 원형으로 동작하게 소스를 작성한 자료구조이고 큐에 대한 정보는 이전 포스팅에 작성하였다.

 

https://jiji-gilog.tistory.com/3

자바(JAVA) - Queue (큐) 구현

 

 

원형큐 구현 시 고려할 사항

• 내가 작성한 원형큐의 front 변수는 첫 번째 인덱스이고 빈 공간으로 설정한다. 만약 front 맨 앞 인덱스를 빈 공간으로 설정하지 않으면 길이가 7인 배열에 원소가 6개로 가득 찬 상태에서 모두 추출(poll) 했다고 가정한 경우 rear는 6, front는 0인 상태인데 rear와 front 변수가 엇갈려서 비어있는지 가득 찬 상태인지 알 수 없다.
• 길이가 8인 배열에 인덱스 7까지 데이터가 삽입되어 있다면 다음 원소는 0 인덱스에 삽입되어야 한다.

rear = (rear + 1) % queue.length;

 

• 길이가 7인 배열에 front가 인덱스 6을 바라보고 있다면 0 인덱스에 있는 원소를 꺼내와야 한다.

- front는 큐의 첫 번째 인덱스로 빈 공간으로 +1을 더한다.

- 원소를 가져온 후 다시 빈공간(초기화)으로 만들어준다.

front = (front + 1) % queue.length;
int element = queue[front];

queue[front] = 0;

 

resize 메소드 : queue 배열의 용량을 재할당하는 메소드.
- queue 배열 사이즈를 offer, poll 시 동적으로 할당하였다.

 

- 원형큐 구현 소스

/**
 * 원형큐 구현 
 * - resize: 용량을 동적 할당
 * - offer: rear에 요소 추가
 * - poll: front + 1 요소 추출 후 제거
 * - remove: front + 1 요소 제거
 * - peek: front + 1 요소 추가
 */
public class CircularQueue {

    private static int[] queue;

    // 큐 첫 번째 인덱스(빈 공간)
    private static int front = 0;
    // 큐 마지막 인덱스
    private static int rear = 0;
    // 큐 요소 개수
    private static int size = 0;

    /**
     * queue 용량을 재설정한다(up, down).
     * @param newCapacity 새로운 용량크기
     */
    private static void resize(int newCapacity) {
        int[] newQueue = new int[newCapacity];

        /*
        기존 큐에 존재하던 데이터를 복사한다.
        새로운 큐에는 front가 0이고 첫 번째 인덱스부터 값을 세팅한다.
         */
        for (int i = 1, j = front + 1; i <= size; i++, j++) {
            newQueue[i] = queue[j % queue.length];
        }

        queue = newQueue;

        front = 0;

        /*
        용량이 더 커진 경우에는 1자로 데이터가 나열되었기 때문에 rear = size
        용량이 더 작아진 경우에는 데이터가 없어서 사이즈를 줄인 것.
         */
        rear = size;
    }

    /**
     * offer: 큐 마지막에 요소를 추가한다.
     * @param val 추가할 요소 값
     */
    private static void offer(int val) {
        // 용량이 가득찬 경우 용량을 2배로 동적 할당한다.
        if (front == (rear + 1) % queue.length) {
            resize(queue.length * 2);
        }

        rear = (rear + 1) % queue.length;

        queue[rear] = val;
        size++;
    }

    /**
     * poll: 큐의 첫 번째 요소를 삭제하고 삭제 된 요소를 반환한다.
     * @return 큐의 첫 번째 요소
     */
    private static int poll() {
        if (size <= 0) {
            return -1;
        }

        // 공백(front) 다음 값을 가져온 후 0(or 빈값)으로 초기 세팅한다.
        front = (front + 1) % queue.length;
        int element = queue[front];

        queue[front] = 0;
        size--;

        // 요소 개수가 1/4 미만일 경우 용량(사이즈)를 1/2로 줄인다.
        if(size < (queue.length / 4)) {
            resize(queue.length / 2);
        }

        return element;
    }

    /**
     * 큐의 첫 번째 요소를 삭제한다.
     * @return 삭제된 요소 값
     */
    private static int remove() {
        int element = poll();

        // 원래 queue가 참조 타입이면 null을 체크하지만 원시(int) 타입이기 때문에 0으로 체크한다.
        if (element == 0) {
            return -1;
//            throw new NoSuchElementException();
        }

        return element;
    }

    private static int size() {
        return size;
    }

    private static int empty() {
        if(size <= 0) {
            return 1;
        }

        return 0;
    }

    /**
     * peek: 큐의 첫 번째 요소를 반환한다.
     * @return 큐의 첫 번째 요소
     */
    private static int peek() {
        if(size <= 0) {
            return -1;
        }

        return queue[(front + 1) % queue.length];
    }

    private static int front() {
        if(size <= 0) {
            return -1;
        }

        return queue[(front + 1) % queue.length];
    }

    private static int back() {
        if(size <= 0) {
            return -1;
        }

        return queue[(rear) % queue.length];
    }
}

 

위 소스는 원형큐의 기능(메소드)만 구현한 소스이고 아래 소스는 테스트 가능한 전체 소스이다.

 

 

원형큐 구현 및 테스트 소스

/**
 * 원형큐 구현 
 * - resize: 용량을 동적 할당
 * - offer: rear에 요소 추가
 * - poll: front + 1 요소 추출 후 제거
 * - remove: front + 1 요소 제거
 * - peek: front + 1 요소 추가
 */
public class CircularQueue {

    private static int[] queue;

    // 큐 첫 번째 인덱스(빈 공간)
    private static int front = 0;
    // 큐 마지막 인덱스
    private static int rear = 0;
    // 큐 요소 개수
    private static int size = 0;

    /**
     * queue 용량을 재설정한다(up, down).
     * @param newCapacity 새로운 용량크기
     */
    private static void resize(int newCapacity) {
        int[] newQueue = new int[newCapacity];

        /*
        기존 큐에 존재하던 데이터를 복사한다.
        새로운 큐에는 front가 0이고 첫 번째 인덱스부터 값을 세팅한다.
         */
        for (int i = 1, j = front + 1; i <= size; i++, j++) {
            newQueue[i] = queue[j % queue.length];
        }

        queue = newQueue;

        front = 0;

        /*
        용량이 더 커진 경우에는 1자로 데이터가 나열되었기 때문에 rear = size
        용량이 더 작아진 경우에는 데이터가 없어서 사이즈를 줄인 것.
         */
        rear = size;
    }

    /**
     * offer: 큐 마지막에 요소를 추가한다.
     * @param val 추가할 요소 값
     */
    private static void offer(int val) {
        // 용량이 가득찬 경우 용량을 2배로 동적 할당한다.
        if (front == (rear + 1) % queue.length) {
            resize(queue.length * 2);
        }

        rear = (rear + 1) % queue.length;

        queue[rear] = val;
        size++;
    }

    /**
     * poll: 큐의 첫 번째 요소를 삭제하고 삭제 된 요소를 반환한다.
     * @return 큐의 첫 번째 요소
     */
    private static int poll() {
        if (size <= 0) {
            return -1;
        }

        // 공백(front) 다음 값을 가져온 후 0(or 빈값)으로 초기 세팅한다.
        front = (front + 1) % queue.length;
        int element = queue[front];

        queue[front] = 0;
        size--;

        // 요소 개수가 1/4 미만일 경우 용량(사이즈)를 1/2로 줄인다.
        if(size < (queue.length / 4)) {
            resize(queue.length / 2);
        }

        return element;
    }

    /**
     * 큐의 첫 번째 요소를 삭제한다.
     * @return 삭제된 요소 값
     */
    private static int remove() {
        int element = poll();

        // 원래 queue가 객체 타입이면 null을 체크하지만 int 타입이기 때문에 0으로 체크한다.
        if (element == 0) {
            return -1;
//            throw new NoSuchElementException();
        }

        return element;
    }

    private static int size() {
        return size;
    }

    private static int empty() {
        if(size <= 0) {
            return 1;
        }

        return 0;
    }

    /**
     * peek: 큐의 첫 번째 요소를 반환한다.
     * @return 큐의 첫 번째 요소
     */
    private static int peek() {
        if(size <= 0) {
            return -1;
        }

        return queue[(front + 1) % queue.length];
    }

    private static int front() {
        if(size <= 0) {
            return -1;
        }

        return queue[(front + 1) % queue.length];
    }

    private static int back() {
        if(size <= 0) {
            return -1;
        }

        return queue[(rear) % queue.length];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int cmd = Integer.parseInt(br.readLine());
        queue = new int[cmd];

        for(int i = 0; i < cmd; i++) {
            st = new StringTokenizer(br.readLine());

            String str = st.nextToken();
            switch (str) {
                case "push":
                    offer(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    sb.append(poll()).append("\n");
                    break;
                case "size":
                    sb.append(size()).append("\n");
                    break;
                case "empty":
                    sb.append(empty()).append("\n");
                    break;
                case "peek":
                    sb.append(peek()).append("\n");
                    break;
                case "front":
                    sb.append(front()).append("\n");
                    break;
                case "back":
                    sb.append(back()).append("\n");
                    break;
            }
        }

        System.out.println(sb);
        br.close();
    }
}