[기본 자료구조] - 큐

큐(Queue)

데이터를 일시적으로 저장하기 위해 사용하는 자료구조

선입선출(FIFO, First In First Out) - 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다.

 

■ 큐 자료구조

큐에 데이터를 넣는 작업을 인큐(enqueue)

큐에서 데이터를 꺼내는 작업을 디큐(dequeue)

 

※ 배열 요소를 앞쪽으로 옮기지 않는 큐 구현을 위해 링 버퍼(ring buffer) 자료구조를 사용

링 버퍼 : 배열의 처음이 끝과 연결되었다고 보는 자료구조, 프런트와 리어의 값을 업데이트하며 인큐와 디큐를 수행

1) 프런트(front)와 리어(rear)
논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수
프런트(front) : 맨 처음 요소의 인덱스를 저장
리어(rear) : 맨 끝 요소의 하나 뒤인 인덱스를 저장(다음 요소를 인큐할 위치를 미리 지정)

2) 큐로 사용할 배열 : que
인큐하는 데이터를 저장하기 위한 큐 본체용 배열

3) 큐의 최대 용량 : max
큐 배열에 저장할 수 있는 최대 요소의 개수

4) enque 메서드
큐에 데이터를 인큐하는 메서드, 성공 시 인큐한 데이터 반환

5) deque 메서드
큐에서 데이터를 디큐하는 메서드, 디큐된 데이터를 반환

6) peek 메서드
큐의 맨 앞 데이터를 조회, 큐가 비어 있을 경우 예외 EmptyIntQueueException 발생
front, rear, num의 값이 변하지 않음

7) indexOf 메서드
큐의 배열에서 x와 같은 데이터가 저장되어 있는 위치를 반환하는 메서드

8) clear 메서드
큐의 모든 데이터를 삭제하는 메서드

9) capacity 메서드
큐의 최대 용량을 반환

10) size 메서드
현재 큐의 데이터 수를 반환

11) IsEmpty 메서드
큐가 비어 있는지 검사하는 메서드

12) IsFull 메서드
큐가 가득 차 있는지 검사하는 메서드

13) dump 메서드
큐에 인큐된 모든 데이터를 프런트에서 리어 순으로 출력하는 메서드

 

import java.util.Arrays;

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];
    }

    public int indexOf(int x){
        for(int i=0; i<num; i++){
            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();
        }
    }

    public static void main(String[] args) {
        IntQueue intque = new IntQueue(5);
        intque.enque(73);
        intque.enque(19);
        intque.enque(82);
        intque.enque(64);
        intque.enque(33);
        System.out.println("isFull : " + intque.isFull());
        intque.deque();
        intque.deque();
        intque.enque(15);
        intque.enque(21);

        System.out.println("indexOf : " + intque.indexOf(15));
        intque.dump();
    }
}