Java Queue 구현하기

자료구조와 함께 배우는 알고리즘 실습 내용 (157P)
링버퍼로 큐를 구현한 예제

배열로 구현하되 링버퍼로 구현한 큐는 배열의 끝에 도달할 때 다시 처음으로 돌아가게 되는 구조이다. 따라서 디큐를 할 때 앞요소를 가리키는 포인터를 +1 만 해주면 된다.
데이터들을 전부 이동시키거나 할 필요가 없어 링으로 구현한 큐의 복잡도는 $O(1)$이 된다.

/**
 * Description: 링버퍼로 큐를 구현
 */
public class IntQueue {
    private int max; //큐의 용량
    private int front; //앞 요소
    private int rear; //마지막 요소
    private int num; //현재 데이터 수
    private int[] que; //큐 본체

    //실행 시 예외 : 큐가 비어있음
    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException() { }
    }
    //실행 시 예외 : 큐가 가득 참
    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException() { }
    }
    //생성자
    public IntQueue(int capacity){
        num = front = rear = 0;
        max = capacity;
        try{
            que = new int[max];
        }catch (OutOfMemoryError e){
            max = 0;
        }
    }
    //큐에 데이터를 인큐
    public int enque(int x) throws OverflowIntQueueException {
        if (num >= max)
            throw new OverflowIntQueueException();
        que[rear++] = x;
        num++;
        if(rear == max)
            rear = 0;
        return x; //인큐한 데이터를 리턴
    }
    //큐에 데이터를 디큐
    public int deque() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if (front == max)
            front = 0;
        return x;
    }
    //큐에서 데이터를 피크(프런트 데이터를 들여다봄)
    public int peek() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();
        return que[front];
    }
    //큐에서 x를 검색하여 인덱스를 반환, 찾지 못하면 -1
    public int indexOf(int x) {
        //i는 num의 수만큼만 반복하면 된다.
        for(int i = 0; i < num; i++) { 
            /** 
             * 실제 시작지점에서부터의 인덱스를 구하기 위함.
             * 링형태의 인덱스값을 구해야 하므로 
             * max로 나누어 떨어질때 0부터 시작할 수 있도록 한다.
             */
            int idx = (i + front) % max;
            if(que[idx] == x)
                return idx;
        }
        return -1;
    }
    //큐를 비움
    public void clear() {
        num = front = rear = 0;
    }
    //큐의 용량의 반환
    public int capacity() {
        return max;
    }
    //큐에 쌓여있는 데이터 수를 반환
    public int size() {
        return num;
    }
    //큐가 비어있나요?
    public boolean isEmpty() {
        return num <= 0;
    }
    //큐가 가득 찾나요?
    public boolean isFull() {
        return num >= max;
    }
    //큐 안의 모든 데이터를 프런트 -> 리어 순으로 출력
    public void dump() {
        if (num <= 0)
            System.out.println("큐가 비어 있습니다.");
        else{
            for (int i = 0; i < num ; i++)
                System.out.print(que[(i + front) % max] + " ");
            System.out.println();
        }
    }
}