자료구조 원형 큐 (Circular Queue) 자바로 구현

1. 개요

이전 글에서 선형 큐는 LinkedList로 구현했다. 배열을 사용하지 않은 이유는 일반적인 방법으로

배열로 큐를 구현하면 효율성이 떨어지기 때문이다.

 

만약 데이터가 1억개 있다고 치자, 큐는 가장 먼저 들어온 데이터가 가장 먼저 나가야 하니, poll()을 하게

되면, 첫번째 자리가 비게 된다.

 

일반적인 방법이라면, 뒤에 있는 모든 데이터를 한칸씩 당겨와 줘야한다. 그런데 배열에서 그 작업을 하려면

poll() 한번 하고 99,999,999개의 메모리를 이동시켜야 하니 상당히 비효율적이다.

 

만약 poll() 을 하고 빈 자리를 그대로 놔둔다고 해도 문제가 된다. 처음에야 그리 시간이 걸리지 않겠지만,

데이터를 1,000만개를 뺐다고 하면, 가장 먼저 들어온 데이터를 찾기 위해, 1,000만번을 이동해서 데이터를

찾아야 하고, 그 빈자리는 모두 메모리상 낭비가 되니 상당히 비효율적이다.

 

하지만 배열로 큐를 효과적으로 사용할 수 있는 방법이 있고, 그게 원형 큐다.

 

선형 큐는 front 와 rear가 가장 멀리 떨어져 있는 선형 모양의 큐지만, 원형 큐는 front와 rear가 배열의

상태에 따라 이동하며, 둥근 배열에서 offer을 하면 front가 뒤로 이동하고, poll을 하면 rear가 뒤로 이동하며

만날 수 있는 형태가 된다.

 

 

 

 

2. 구현

package queue;

public interface IQueue<T> {
    void offer(T data);
    T poll();
    T peek();
    int size();
    void clear();
    boolean isEmpty();
}

package queue;

public class MyCircularQueue<T> implements IQueue<T> {
    // 배열을 통해 구현
    private T[] elements;
    private int front;
    private int rear;
    private int maxSize;

    public MyCircularQueue(int size) {
        this.elements = (T[]) new Object[size + 1];
        //더미 공간, isEmpty와 Full 상태를 구별하기 위함
        this.front = 0;
        this.rear = 0;
        this.maxSize = size + 1;
   }

    @Override
    public void offer(T data) {
        if (this.isFull()) {
            throw new IllegalStateException();
        }

        this.rear = (this.rear + 1) % this.maxSize;
        this.elements[this.rear] = data;
    }

    @Override
    public T poll() {
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        this.front = (this.front + 1) % this.maxSize;
        return this.elements[this.front];
        // 어차피 데이터의 삽입과 인출은 front와 rear에 의해 일어나고,
        // 배열을 선언한 시점에서 그 위치를 쓰고있으니, 데이터를 지워줄 필요가 없다.
    }

    @Override
    public T peek() { // 데이터를 빼지 않고 확인만
        if (this.isEmpty()) {
            throw new IllegalStateException();
        }
        return this.elements[this.front + 1];
    }

    @Override
    public int size() {
        if (this.front <= this.rear) {
            return this.rear - this.front;
        }
        return this.maxSize - this.front + this.rear;
    }

    @Override
    public void clear() {
        this.front = 0; // 어차피 데이터 넣으면 초기화되니 이렇게 하면
        this.rear = 0; // 초기화
    }

    @Override
    public boolean isEmpty() {
        return this.front == this.rear;
    }

    private boolean isFull() {
        return (this.rear + 1) % this.maxSize == this.front;
        // rear 바로 뒤에 front가 있으면 큐가 꽉 찬 상태이다.
        // 한바퀴 돌면 front와 rear위치가 다시 바뀐다. rear+1 이 큐 사이즈보다
        // 커질 수 있기에, %연산으로 확실하게 확인한다.
    }
}

 

3. 설명

3-1. 멤버 변수(Member Variable), 생성자(Constructor)

멤버변수로는 elements[], front, rear, MaxSize가 있다.

배열을 만들 elements[], 이름 그대로 front, rear, MaxSize가 있다.

 

생성자는 인스턴스가 생성되면 elements에 인수로 들어온 사이즈 + 1 을 집어넣는다.

+1인 이유는 원형 큐에선 데이터가 가득 찼을 때, front의 위치와 rear의 위치가 같게 된다.

그런데 front의 첫번째부터 데이터를 넣게 되면, 큐가 비어있는 상태와 가득 찬 상태를 구별하기 힘들게 된다.

 

그래서 사이즈 + 1로 front의 부분에는 데이터를 넣지 않는 더미 공간으로 만든다.

 

front, rear은 0, maxSize는 인수로 들어온 size + 1로 만들어 준다.

 

 

3-2. isFull()

 

배열이 꽉 찼나 확인하는 메소드다.

this.rear = (this.rear + 1) % this.maxSize 이 코드로 원형 큐의 개념을 설명할 수 있다.

데이터를 계속 넣다보면 rear가 maxSize보다 커지고, 배열을 사용할 수 없을 것이다.

 

하지만, % 연산자는 숫자를 나눈 뒤, 나머지를 준다.

즉 maxSize가 10이고, rear가 66이라도, rear는 6이 되고, 메모리의 낭비를 최소화 하는 것이다.

 

더미 공간이 있으니, front와 rear가 같다면, 들어온 데이터가 없다는 뜻이 된다.

하지만, 더미 공간이 있으니, front 바로 뒤로 rear가 있다는 말은, 큐에 데이터가 가득 찼다는 말이 된다.

 

(rear + 1) % maxSize == this.front  배열의 모든 공간에 데이터가 들어가서 넣을 자리가 없다는 말이다.

 

 

 

3-3. isEmpty()

데이터가 비어있는지 확인한다.

front와 rear가 같다는 말은 들어와 있는 데이터가 없다는 말이다.

 

 

3-4. offer()

큐에 데이터를 집어넣는 메소드다.

우선 큐가 꽉 찼나 isFull() 메소드로 확인하고, 만약 꽉 찼다면 데이터를 넣을 자리가 없으니 에러를 일으킨다.

 

남은 자리가 있다면 rear의 자리를 바꾸고, 그 자리에 데이터를 넣어주면 offer 메소드가 종료된다.

 

 

3-5. poll()

큐에서 데이터를 하나 빼는 메소드다.

isEmpty() 메소드로 큐가 비었나 확인하고, 큐에 아무런 데이터도 없다면, 꺼낼 게 없으니 에러를 일으킨다.

 

데이터가 있다면, front를 한칸 이동시켜 프론트에 있는 데이터를 꺼낸다.

데이터를 삭제할 필요는 없다. 어차피 원형 큐라 rear에 데이터를 계속 넣어주면, 결국 한바퀴 돌아서

front가 있던 자리에 새로운 데이터를 넣을 것이고, 데이터를 넣기 전이라고 해도, 어차피 배열은 특정 크기의

메모리를 사용하고 있으니, 삭제해줄 필요는 전혀 없는 것이다.

 

 

3-6. peek()

큐에서 가장 먼저 들어온 데이터를 확인하는 방법이다. poll() 메소드와 다른 점은, front를 이동시키지 않으니,

다시 peek() 을 해도 같은 데이터가 나온다.

 

 

3-7. size()

큐에서 데이터가 들어간 공간의 크기를 반환하는 메소드다.

 

front가 rear보다 크다는 말은, rear가 한바퀴 돌아서 front에 뒤에 있게 되는 것이다.

rear가 더 크다면, rear - front로 크기를 반환한다.

 

front가 더 크다면 maxSize 에서 (front + rear)의 값을 반환하면, 데이터가 있는 공간의 크기가 된다.

 

 

3-8. clear()

큐를 초기화 시켜주는 메소드다.

front와 rear을 0으로 만들면 데이터를 집어넣을 때마다 새로운 데이터를 넣게 될테니 초기화와 다를 게 없다.

위에서 설명한 것처럼, 어차피 배열을 선언한 시점부터 그 공간을 사용하고 있으니, 굳이 데이터를 다 찾아서 지우는

건 필요도 없을 뿐더러, 비효율적인 작업이다.