[자료구조] 원형 큐의 기능 및 구현

안녕하세요. PEACE-입니다.

자료구조 스터디 [여섯 번째] 글입니다.

배열을 이용한 원형 큐에 대해 알아보겠습니다. 

선형 큐에 대한 이해가 부족하시면 아래 주소로 가서 선형 큐 포스팅을 참고해주시기 바랍니다.

선형 큐 포스팅 http://mailmail.tistory.com/33

1. 원형 큐

원형 큐는 선형 큐와 마찬가지로 선입선출(First In First Out) 형태의 데이터 구조입니다. front와 rear 역시 사용하며 배열로 구현할 수 있습니다. 원형 큐는 선형 큐의 한계점을 해결하기 위해 구조화한 것인데, 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 '(index+1) % 배열의 사이즈'를 이용하여 OutOfBoundsException이 일어나지 않고 인덱스 0으로 순환되는 구조를 가집니다.

2. Enqueue와 Dequeue

그림을 통해 enqueue, dequeue에 따른원형 큐의 상태 변화를 보여드리겠습니다.

 

3. 소스코드 (JAVA)

Queue.class

/* 원형 큐
 * front : int - 초기 값 0, 처음 데이터의 바로 전 인덱스
 * rear : int - 초기 값 0, 마지막 데이터의 인덱스
 * isEmpty() : boolean - 큐가 비어있는가
 * isFull() : boolean - 큐가 가득 찼는가
 * enqueue() : void - 데이터 넣기
 * dequeue() : void - 데이터 빼기
 * diplay() : void - 데이터 출력
 * */
public class Queue {

    private final int MAX_SIZE = 5;
    private int front, rear;
    private int[] queue;

    public Queue2() {
        front = rear = 0;
        queue = new int[MAX_SIZE];
    }

    // front와 rear이 같은 위치에 있다면 큐가 비어있다는 뜻이다.
    private boolean isEmpty() {
        return front == rear;
    }
    // rear이 front의 바로 전 위치에 있다면 큐가 가득찼다는 뜻이다.
    private boolean isFull() {
        return (rear+1) % MAX_SIZE == front;
    }
    // 데이터가 들어갈 땐 rear만 움직인다. 
    // rear의 위치는 최근에 들어온 데이터의 위치이다. 
    // 즉, 새로운 데이터가 들어오기 위해 먼저 이동해야한다.
    public void enqueue(int data) {
        // 큐가 가득차면 들어갈 수 없다 -> 리턴
        if (isFull())
            System.out.println("It's FULL!!!");
            // 큐에 자리가 있다면 데이터를 넣는다.
        else {
            rear = (++rear) % MAX_SIZE; //원형 큐이기 때문에 순환한다.
            queue[rear] = data;
        }
    }
    // 데이터가 나갈 땐 front만 움직인다. 
    public int dequeue() {
        int preIndex;
        // 큐가 비어있다면 데이터를 뺄 수 없다. 나는 데이터가 없다는 신호로 -1을 리턴했다(임시 정의)
        if (isEmpty())
            return -1;
            // 큐에 데이터가 있다면 데이터를 뺀다. front 이동(증가)
        else {
            preIndex = front;
            front = (++front) % MAX_SIZE;
        }
        return queue[preIndex];
    }

    public void display() {
        System.out.println("FRONT :"+front+" REAR :"+rear);
        System.out.print("QUEUE DATA: ");
        for(int index = front + 1; index != (rear+1) % MAX_SIZE; index = (index+1) % MAX_SIZE)
            System.out.print(queue[index] + " ");
        System.out.println();
        System.out.println();
    }
}