[Data Structure] 원형 큐

 

선형 큐 구조로 구현하면 문제점은 

 

배열의 공간 낭비가 발생한다. 이런 문제점을 해결하기 위해 원형 큐로 큐를 구현하면 된다.

 

---

 

 

선형 큐와 동일하게 rear에서 데이터가 삽입되고 front에서 데이터가 삭제되는 구조이다.

 

원형 큐는 배열을 원 모양으로 둥글게 말은 형태이다. 

 

 

---

 

원형 큐 인터페이스 코드

 

package queue;

/*
  enpueue(Object o)
  depueue()
  peek()
  isEmpty()
  isFull()
  indexOf()
  clear()
 */

public interface QueueInterface<T> {
    public void enQueue(T item);
    public void deQueue();
    public void peek();
    public boolean isEmpty();
    public boolean isFull();
    public void indexOf(T key);
    public void clear();
}

 

 

사용자 예외, 생성자, 인스턴스 변수

    private T[] queue;
    private int front, rear;
    private int count, size;

    /**
     * 큐 기본 사이즈 10
     */
    CircleQueue() {
        this(10);
    }


    /**
     * @param size 큐 사이즈 지정 변수
     */
    CircleQueue(int size) {
        try {
            queue = (T[]) new Object[size];
            this.size = size;
        } catch (OutOfMemoryError oome) {
            System.out.println("메모리 부족");
        }
    }

    /**
     * 사용자 예외 큐가 빈 상태
     */
    private static class UnderFlow extends RuntimeException {
        public UnderFlow() throws RuntimeException {
            super("큐가 비어있는 상태");
        }
    }

    /**
     * 사용자 예외 큐가 가득 찬 상태
     */
    private static class OverFlow extends RuntimeException {
        public OverFlow() throws RuntimeException {
            super("큐가 꽉찬 상태");
        }
    }

 

 

정적할당으로 배열 사이즈는 미리 정한다. 기본 사이즈는 10이다.

 

사용자 예외 OverFlow와 UnderFlow를 정의한 후 큐의 상태 메시지를 문자열로 넘긴다.

 

 

 

 

 

 /**
     * count기반 isEmpty 체크 count가 0보다 작거나 크면 큐에 아무것도 없는 상태
     * front==rear 확인은 count기반이 아닌 큐 1자리 남기고 포화상태 체크할 때 사용하는 조건
     *
     * @return count<= 0 인 경우 false 반환
     */
    @Override
    public boolean isEmpty() {
        //return front==rear;
        return count <= 0;
    }

    /**
     * count기반 isFull 체크 count가 size와 크거나 같으면 큐가 꽉 찬 상태이다.
     * count기반 사용하기 싫다면 주석부분 삭제 후 사용
     * 큐의 한 자리 남기고 포화상태 체크하는 알고리즘 (rear+1)%size == front인 경우 한자리를 제외한 rear==front이므로 포화
     *
     * @return count>=size 일 경우 true 반환
     */
    @Override
    public boolean isFull() {
        //return ((rear+1)%size)==front; //마지막 자리 남기고 isFull 확인 가능
        return count >= size;
    }

 

 

주석 부분을 보면 알겠지만 isEmpty와 isFull은 사실 front==rear로 큐의 상태를 확인할 수 있다. 

front==rear연산의 문제는 isEmpty와 isFull 둘 다 true가 되므로 큐가 비어있는지 포화상태인지 구별할 수 없다.

 

따라서 해당 코드에서는 count <=0는 큐 공백상태 확인 연산으로 사용하였고 

포화상태 확인은 count변수 기반으로 count값이 큐의 size값과 동일하면 true 반환.

위 코드로 포화, 공백 상태 확인은 enqueue, dequeue 연산할 때 count를 증감 연산을 계속해줘야 한다.

 

count 변수를 관리하기 싫다면

큐의 한 자리는 계속 남겨 놓은 상태에서 (rear+1)%size==front 일 경우 포화상태라고 볼 수 있다.

 

 

return ((rear+1)%size)==front; //마지막 자리 남기고 isFull 확인 가능
return count >= size;

 

 

 

 

 

/**
     * 순환 구조 시계 방향 (rear+1)%size , count 기반
     *
     * @param item 큐에 추가할 요소
     * @throws OverFlow 큐 가득찬 상태 경우 예외 발생
     */
    @Override
    public void enQueue(T item) throws OverFlow {
        if (isFull()) {
            throw new OverFlow();
        }
        queue[rear] = item;
        rear = (rear + 1) % size;
        count++;

        System.out.println(Arrays.toString(queue));
    }

    /**
     * 순환 구조 시계 방향 (front+1)%front , count 기반
     *
     * @throws UnderFlow 큐가 빈 상태일 때 예외 발생
     */
    @Override
    public void deQueue() throws UnderFlow {
        if (isEmpty()) {
            throw new UnderFlow();
        }
        System.out.println("꺼낸 값: " + queue[front]);
        front = (front + 1) % size;
        count--;

        System.out.println(Arrays.toString(queue));
    }

 

 

enqueue:  rear의 맨 초기값은 0이다. queue[rear]에 값을 먼저 넣은 후 rear를 증가시킨다. 

                 일반적으로 rear++ 연산하면 선형 큐와 다를 게 없으므로 (rear+1)% SIZE로 rear값을  0~큐의 size-1 사이 값으로 순환하게 한다.   ex) rear = 3  SIZE = 4 front = 0일 경우 (3+1)%4는 0이므로 front와 같다 포화상태인 것을 확인할 수 있다.

 

dequeue

 

 

 

 

 

peek(), indexOf()

    /**
     * 큐 front에 존재하는 값 출력
     *
     * @throws UnderFlow 큐가 빈 상태일 때 예외 바생
     */
    @Override
    public void peek() throws UnderFlow {
        if (isEmpty()) {
            throw new UnderFlow();
        }
        System.out.println(queue[front]);
    }

 

 

    /**
     * 순차 탐색으로 배열안에 값 찾는 메서드
     *
     * @param key 메서드 호출 시 인수로 넘어올 값을 큐에 존재하는지 순차 탐색한다.
     */
    @Override
    public void indexOf(T key) {
        int copyFront = front;
        for (int i = 0; i < count; i++) {
            if (key.equals(queue[copyFront])) {
                System.out.println("해당 " + key + " 는 index queue[" + copyFront + "]에 있습니다.");
                return;
            }
            copyFront = (copyFront + 1) % size;
        }
    }

 

 

peek(): 큐의 출구 쪽 (front) 쪽에 가장 가까운 요소 출력

 

indexOf(T key): front값부터 시작하여 for문의 지역변수 i를 계속 더해 순차적으로 탐색한다. 여기서 count변수 대신 size변수를 사용하여 반복문의 횟수를 관리해도 된다. 탐색할 때 front값은 (front+1) % SIZE로 size값을 초과하지 않게 한다.

 

 

---

전체 Queue 코드

 

package queue;

import java.util.Arrays;

public class CircleQueue<T> implements QueueInterface<T> {
    private T[] queue;
    private int front, rear;
    private int count, size;

    /**
     * 큐 기본 사이즈 10
     */
    CircleQueue() {
        this(10);
    }


    /**
     * @param size 큐 사이즈 지정 변수
     */
    CircleQueue(int size) {
        try {
            queue = (T[]) new Object[size];
            this.size = size;
        } catch (OutOfMemoryError oome) {
            System.out.println("메모리 부족");
        }
    }

    /**
     * 사용자 예외 큐가 빈 상태
     */
    private static class UnderFlow extends RuntimeException {
        public UnderFlow() throws RuntimeException {
            super("큐가 비어있는 상태");
        }
    }

    /**
     * 사용자 예외 큐가 가득 찬 상태
     */
    private static class OverFlow extends RuntimeException {
        public OverFlow() throws RuntimeException {
            super("큐가 꽉찬 상태");
        }
    }

    /**
     * 순환 구조 시계 방향 (rear+1)%size , count 기반
     *
     * @param item 큐에 추가할 요소
     * @throws OverFlow 큐 가득찬 상태 경우 예외 발생
     */
    @Override
    public void enQueue(T item) throws OverFlow {
        if (isFull()) {
            throw new OverFlow();
        }
        queue[rear] = item;
        rear = (rear + 1) % size;
        count++;

        System.out.println(Arrays.toString(queue));
    }

    /**
     * 순환 구조 시계 방향 (front+1)%front , count 기반
     *
     * @throws UnderFlow 큐가 빈 상태일 때 예외 발생
     */
    @Override
    public void deQueue() throws UnderFlow {
        if (isEmpty()) {
            throw new UnderFlow();
        }
        System.out.println("꺼낸 값: " + queue[front]);
        front = (front + 1) % size;
        count--;

        System.out.println(Arrays.toString(queue));
    }

    /**
     * 큐 front에 존재하는 값 출력
     *
     * @throws UnderFlow 큐가 빈 상태일 때 예외 바생
     */
    @Override
    public void peek() throws UnderFlow {
        if (isEmpty()) {
            throw new UnderFlow();
        }
        System.out.println(queue[front]);
    }

    /**
     * count기반 isEmpty 체크 count가 0보다 작거나 크면 큐에 아무것도 없는 상태
     * front==rear 확인은 count기반이 아닌 큐 1자리 남기고 포화상태 체크할 때 사용하는 조건
     *
     * @return count<= 0 인 경우 false 반환
     */
    @Override
    public boolean isEmpty() {
        //return front==rear;
        return count <= 0;
    }

    /**
     * count기반 isFull 체크 count가 size와 크거나 같으면 큐가 꽉 찬 상태이다.
     * count기반 사용하기 싫다면 주석부분 삭제 후 사용
     * 큐의 한 자리 남기고 포화상태 체크하는 알고리즘 (rear+1)%size == front인 경우 한자리를 제외한 rear==front이므로 포화
     *
     * @return count>=size 일 경우 true 반환
     */
    @Override
    public boolean isFull() {
        return ((rear + 1) % size) == front; //마지막 자리 남기고 isFull 확인 가능
        //return count >= size;
    }

    /**
     * 순차 탐색으로 배열안에 값 찾는 메서드
     *
     * @param key 메서드 호출 시 인수로 넘어올 값을 큐에 존재하는지 순차 탐색한다.
     */
    @Override
    public void indexOf(T key) {
        int copyFront = front;
        for (int i = 0; i < count; i++) {
            if (key.equals(queue[copyFront])) {
                System.out.println("해당 " + key + " 는 index queue[" + copyFront + "]에 있습니다.");
                return;
            }
            copyFront = (copyFront + 1) % size;
        }
    }

    /**
     * 큐를 초기화하는 메서드 rear, front, count도 모두 0으로 값을 바꾼다.
     */
    @Override
    public void clear() {
        queue = (T[]) new Object[size];
        front = 0;
        rear = 0;
        count = 0;
    }
}

 

 

 

Main 코드

package queue;

public class Main {
    public static void main(String[] args) {
        CircleQueue<Integer> circleQueue = new CircleQueue<>(7);
        for (int i = 0; i < 6; i++) {
            circleQueue.enQueue(i);
        }
        circleQueue.deQueue();
        circleQueue.deQueue();
        circleQueue.peek();

        circleQueue.enQueue(6);
        circleQueue.enQueue(7);

        circleQueue.indexOf(3);
        circleQueue.clear();
    }
}