큐(Queue)

큐(QUEUE)

스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조인 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 FIFO(First in First Out) 형식을 따르고 있다.
Queue 라는 단어는 실제로 영어 회화에서도 많이 사용되는 단어로, 식당에 손님들이 서있는 줄을 queue 라고 표현하기도 한다. 가장 먼저 와서 기다린 사람이 가장 먼저 식당에 입장할 수 있듯, 큐 자료구조에선 가장 먼저 입력된 데이터가 가장 먼저 출력될 수 있다.

큐에 데이터를 넣는 작업은 enqueue 라고하고, 꺼내는 작업은 dequeue,
데이터를 꺼내는 쪽을 front 라 하고 넣는 쪽을 rear 라고 표현한다.

큐를 효과적으로 구현하려면 Ring Buffer 에 대한 이해가 필요한데,
Ring Buffer는 배열의 처음과 끝이 연결되어 있는 구조로 맨 처음 element 의 index 를 front, 맨 마지막 element+1 index 를 rear 라고한다.

다음으로 JAVA 코드로 Ring Buffer 구조를 기억하며 Queue를 구현해 보자.

public class IntQueue {
    private int max;        // 큐의 용량
    private int front;      // 첫 번째 요소 커서
    private int rear;       // 마지막 요소 커서
    private int num;        // 현재 데이터 수
    private int[] queue;    // 큐 본체

    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException(){}
    }
    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException(){}
    }

    public IntQueue(int max) {
        num = 0;
        front = 0;
        rear = 0; 
        this.max = max;
        try{
            queue = new int[max];
        } catch (OutOfMemoryError e){
            e.printStackTrace();
        }
    }

    public int enqueue(int value) throws OverflowIntQueueException{
        if(num >= max) // 현재 데이터의 개수 (num) 가 용량치 이상일 경우 데이터추가시 오버플로우
            throw new OverflowIntQueueException();

        queue[rear++] = value;    // queue 의 rear 에 value 추가 후 rear 1 증가
        num++;                    // 현재 데이터 개수(num) 1 증가

        if(rear == max)           // 자료구조의 입구가 rear, 출구가 front 다. 순환해야함으로 입구가 배열의 끝까지가면 입구는 배열의 처음으로 이동
            rear = 0;

        return value;
    }

    public int deque() throws EmptyIntQueueException{
        if (num <= 0 )
            throw new EmptyIntQueueException();

        int frontVal = queue[front++];      // queue 에서 dequeue 할 값을 임시 저장 후 front 1 증가
        num--;                              // 현재 데이터 개수(num) 1 감소

        if(front == max)                    // front (데이터가 나가는 구멍)
            front = 0;

        return frontVal;
    }

    public int peek() throws EmptyIntQueueException{
        if(num <= 0)
            throw new EmptyIntQueueException();

        return queue[front];
    }

    public int indexOf(int x){
        for(int i = 0; i < num; i++){
            int idx = (i + front) % max;
            if(queue[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(queue[(i + front) % max]+ " ");
            }
            System.out.println();
        }
    }

}

/참고
Buffer 는 컴퓨팅에서, 버퍼(buffer, 문화어: 완충기억기)는 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역
출처 - https://ko.wikipedia.org/wiki/%EB%B2%84%ED%8D%BC_(%EC%BB%B4%ED%93%A8%ED%84%B0_%EA%B3%BC%ED%95%99
/