큐

• 데이터를 일시적으로 쌓아 두기 위한 자료구조
• 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out)
• 큐의 예로는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열이 있다.
• 데이터를 넣는 작업을 인큐(enqueue)라 하고, 꺼내는 작업을 디큐(dequeue)라고 한다.
• 데이터를 꺼내는 쪽은 프런트(front)라 하고, 넣는 쪽을 리어(rear)라고 한다.
• 배열로 큐를 구현할 때 디큐 시 요소를 꺼낸 후 다음 두 번째 이후의 요소를 모두 맨 앞으로 옮기는 구현 방식의 처리 복잡도는 O(n)이다.
• 링 버퍼(ring buffer, 배열의 처음이 끝과 연결되었다고 보는 자료구조)를 이용한다. 논리적으로 변수 프런트(front)와 리어(rear)의 값을 업데이트하며 인큐와 디큐를 수행하기 때문에 요소 이동 문제를 해결하게 되어 처리 복잡도는 O(1)이 된다.
  • [프런트(front)] : 맨 터음 요소의 인덱스
  • [리어(rear)] : 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐할 위치를 미리 지정)

//int형 큐
public class IntQueue {
 
    private int max;        //큐의 용량
    private int front;        //첫 번째 요소 인덱스
    private int rear;        //마지막 요소의 하나 뒤의 인덱스
    private int num;        //현재 데이터 수(front와 rear의 값이 같은 경우 큐가 비었는지, 가득 찼는지 구별할 수 없는 상황을 피하기 위해 필요)
    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를 검색하여 인덱스를 반환
    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();
        }
    }
}