자바(JAVA)로 큐(Queue) 구현하기

public class IntAryQueue {
    private int max; // 큐 용량
    private int num; // 현재 데이터 수
    private int[] que; // 큐 본체

    private int front;
    private int rear;

    // 예외 : 큐가 비어 있음
    class EmptyIntQueueException extends RuntimeException{
    }
    // 예외 : 큐가 가득 참
    class OverflowIntQueueException extends RuntimeException{
    }

    public IntAryQueue(int capacity){
        num = front = rear = 0;
        max = capacity;
        try {
            que = new int[capacity];
        }catch(OutOfMemoryError e){
            max = 0;
        }
    }

    public int enque(int x){
        if(num >= max){
            throw  new OverflowIntQueueException();
        }
        que[rear++] = x;
        num++;
        return x;
    }

    public int deque(){
        if(num <= 0){
            throw new EmptyIntQueueException();
        }
        int value = que[front];
        que = Arrays.copyOfRange(que, front + 1, rear--);
        num--;
        return value;
    }

    public void print(){
        for(int data : que){
            System.out.println("data : " + data);
        }
    }

    public int[] getQue(){
        return que;
    }

    public int size(){
        return num;
    }

    public int peek(){
        if(num <= 0){
            throw new EmptyIntQueueException();
        }
        return que[front];
    }

    public int indexOf(int x){
        for(int i=0; i<num; i++){
            if(que[i] == x) return i;
        }
        return -1;
    }
}

배열로 큐를 구현한다.
단순히 배열로 큐를 구현했을 때, 비효율적인 부분이 있는데 바로 deque 후에 뒤에 있는 데이터를 배열의 맨 앞으로 복사해야 한다는 점이다. (시간복잡도 O(n))
코드에서 보면

que = Arrays.copyOfRange(que, front + 1, rear--);

위와 같은 부분이다. 따라서 큐를 구현할 때는 배열을 링 버퍼(배열의 앞과 끝이 연결된 형태)로 생각하고 구현을 하게되면 저장 요소 이동 문제를 해결 할 수 있다.

2021/01/05 - [프로그래밍 노트/자료구조] - 자바(JAVA)로 큐(Queue) 구현하기_2 (링버퍼 사용)

https://github.com/ksh901016/algo-practice/blob/main/src/main/java/queue/IntAryQueue.java