05_큐(queue)

- 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조

- 선입선출(FIFO, First In First Out / LILO, Last In Last Out)

- 실생활에서 많이 보는 예) 은행 창구 차례, 마트 계산 대기열 등등

- 기본 용어

• enqueue: 인큐(큐에 데이터 넣기)  → O(1)
• dequeue: 디큐(큐에서 데이터 꺼내기  → O(n) : 맨 앞 데이터 꺼내고, 나머지 데이터들 다 한 칸씩 앞으로 이동
• front: 데이터를 꺼내는 쪽
• rear: 데이터를 넣는 쪽

- 링 버퍼(ring buffer)를 사용한 Queue:  dequeue 하고도 배열 요소를 앞으로 옮기지 않는 큐

• ring처럼 처음과 끝이 연결되어 있음
• enqueue(), dequeue() 모두 O(1)
• **주의할 점

1. enqueue하고 rear가 max와 같아지면 rear = 0; 처리 (원형으로 돌아야하니까)
2. dequeue하고 front가 max와 같아지면 front = 0; 처리
3. indexOf 할 때, 인덱스의 계산 『(i + front) % max』
4. dump할 때에도, 인덱스 계산  『(i + front) % max』

- 링 버퍼로 큐 만들어보기

public class RingBufferQueue {
    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 ringBufferQueue(int capacity) {
        num = front = rear = 0;
        max = capacity;
        try {
            que = new int[max];
        } catch (OutOfMemoryError e) {
            max = 0;
        }
    }

    // enque() : 큐의 맨 뒤에 데이터 넣음
    public int enque(int x) throws OverflowIntQueueException {
        if (num >= max)
            throw new OverflowIntQueueException();
        que[rear++] = x;
        num++;
        if (rear == max)    // *rear가 최대 용량의 max와 같을 경우, rear = 0으로 설정
            rear = 0;
        return x;
    }

    // deque() : 큐의 맨 앞 데이터 꺼냄
    public int deque() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if (front == max)   // *front가 max와 같을 경우, front = 0으로 설정
            front = 0;
        return x;
    }
    // peek() : 큐의 맨 앞 데이터 확인 (꺼내지는 X → front, rear, num 값 변화 없음)
    public int peek() throws EmptyIntQueueException {
        if (num <= 0)
            throw new EmptyIntQueueException();
        return que[front];
    }

    // indexOf() : 검색 값의 인덱스 반환 (없으면 -1 반환)
    public int indexOf(int x) {
        // front → rear 선형 검색
        for (int i = 0; i < num; i++) {
            int idx = (i + front) % max;        // ★
            if (que[idx] == x)
                return idx;
        }
        return -1;
    }

    // clear() : 큐의 모든 데이터 삭제
    public void clear() {
        num = front = rear = 0;     // → 큐의 요솟값 바꿀 필요 X
    }

    // capacity() : 최대 용량 확인
    public int capacity() {
        return max;
    }

    // size() : 현재 데이터 개수 확인
    public int size() {
        return num;
    }

    // isEmpty() : 큐 비어 있음? (true/false 반환)
    public boolean isEmpty() {
        return num <= 0;
    }

    // isFull() : 큐 가득 참? (true/false 반환)
    public boolean isFull() {
        return num >= max;
    }

    // dump() : 큐의 모든 데이터 front → rear 순으로 출력
    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();
        }
    }
}

 

- 링 버퍼: 오래된 데이터를 버리는 용도로도 사용할 수 있음

 ex) 용량 10으로 해놓고 enqueue는 무한히 가능하게

       > 데이터는 10개만 저장하고 10개 초과 시, 오래된 데이터는 새로 입력된 데이터로 덮어쓰기

      > 가장 최근에 입력한 10개의 데이터만 링 버퍼에 남게 된다.

코드 예시)

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    final int N = 10;
    int[] a = new int[N];
    int cnt = 0;    // 입력 받은 개수
    int retry;

    System.out.println("정수를 입력하세요.");
    do {
        System.out.printf("%d번째 정수 : ", cnt + 1);
        a[cnt++ % N] = sc.nextInt();
        //-- 『cnt++ % N』 : 링 버퍼(배열)에 순환하며 저장되고 있음

        System.out.print("계속? (예.1/아니오.0) : ");
        retry = sc.nextInt();
    } while (retry == 1);

    int i = cnt - N;    // 최근 입력한 N개 중 첫번째 번호 구함
    if (i < 0) i = 0;
    for ( ; i < cnt; i++)
        System.out.printf("%2d번째 정수 = %d\n", i + 1, a[i % N]);
}

 

- 덱(deck): 양방향 대기열(deque/double ended queue), 시작과 끝 지점에서 양쪽으로 데이터를 인큐, 디큐하는 자료구조

- 덱 만들어보기

public class Deck {
    private int max;    // 덱(deck)의 용량
    private int num;    // 현재 데이터 개수
    private int front;  // 맨 앞 커서
    private int rear;   // 맨 뒤 커서
    private int[] que;  // 덱(deck)의 본체

    // 실행 시 예외: deck 비어 있음
    public class EmptyDeckException extends RuntimeException {
        public EmptyDeckException() {}
    }

    // 실행 시 예외: deck 가득 참
    public class OverflowDeckException extends RuntimeException {
        public OverflowDeckException() {}
    }

    // 생성자
    public deck(int capacity) {
        num = front = rear = 0;
        max = capacity;
        try {
            que = new int[max];
        } catch (OutOfMemoryError e) {
            max = 0;
        }
    }

    // enqueFront() : 데이터를 front에 enque
    public int enqueFront(int x) throws OverflowDeckException {
        if (num >= max)
            throw new OverflowDeckException();
        if (--front < 0)
            front = max - 1;
        que[front] = x;
        num++;
        return x;
    }

    // enqueRear()  : 데이터를 rear에 enque
    public int enqueRear(int x) throws OverflowDeckException {
        if (num >= max)
            throw new OverflowDeckException();
        que[rear++] = x;
        if (rear == max)
            rear = 0;
        num++;
        return x;
    }

    // dequeFront() : front에서 deque
    public int dequeFront() throws EmptyDeckException {
        if (num <= 0)
            throw new EmptyDeckException();
        int x = que[front++];
        if (front == max)
            front = 0;
        num--;
        return x;
    }

    // dequeRear()  : rear에서 deque
    public int dequeRear() throws EmptyDeckException {
        if (num <= 0)
            throw new EmptyDeckException();
        if (--rear < 0)
            rear = max - 1;
        num--;
        return que[rear];
    }

    // peekFront()  : front 데이터를 peek
    public int peekFront() throws EmptyDeckException {
        if (num <= 0)
            throw new EmptyDeckException();
        return que[front];
    }

    // peekRear()   : rear 데이터를 peek
    public int peekRear() throws EmptyDeckException {
        if (num <= 0)
            throw new EmptyDeckException();
        return que[rear == 0 ? max - 1 : rear - 1];
    }

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

	// 아래 메서드는 RingBufferQueue 코드와 동일
    // search()
    // clear()
    // capacity()
    // size()
    // isEmpty()
    // isFull()
    // dump() 
}