큐 알아보기

• 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 구조이다.
• 하지만, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 방식을 사용한다.

배열로 큐 만들기

배열 {19, 40, 20, 40} 이 있다고 가정하자.
데이터 24라는 값을 인큐(데이터를 넣는 작업)하면 {19, 40, 20, 40, 24}가 된다.
데이터 19를 디큐(데이터를 빼는 작업)하면 {40, 20, 40, 24}가 된다

링 버퍼로 큐 만들기

배열 요소를 앞쪽으로 옮기지 않는 큐를 구현하기
이를 위한 자료구조는 링 버퍼라고 부른다.

package chap4;

public class IntQueue {
    private int[] que; // 큐용 배열
    private int capacity; // 큐의 용량
    private int front; // 맨앞의 요소 커서
    private int rear; // 맨뒤의 요소 커서
    private int num; // 현재 데이터 개수
    
    // 실행시 예외: 큐가 비어있음
    public class EmptyIntQueueException extends RuntimeException {
        public EmptyIntQueueException() {}
    }
    
    // 실행시 예외: 큐가 가득 참
    public class OverflowIntQueueException extends RuntimeException {
        public OverflowIntQueueException() {}
    }
    
    // 생성자
    public IntQueue(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = new int[capacity]; // 큐 본체용 배열 생성
        } catch(OutOfMemoryError e) { //생성할 수 없음
            capacity = 0;
        }
    }
    
}

분석

• 큐로 사용할 배열 Que

- 인큐하는 데이터를 저장하기 위한 본체용 배열

• 큐의 최대 용량 Capacity

- 큐의 최대 용량을 저장하는 필드.
- 이 값은 배열 que에 저장할 수 있는 최대 요솟수

• 프런트 front

- 인큐하는 데이터 가운데 맨 앞 요소의 인덱스를 저장하는 필드

• 리어 rear

- 인큐하는 데이터 가운데 맨 뒤 요소의 인덱스를 저장하는 필드

• 현재 데이터 num

- 큐에 쌓여 있는 데이터 개수를 나타내는 int형 필드
- front값과 rear값이 같을 때 큐가 비어있는지 가득차있는지 구별할 수 없는 상황을 피하기 위해 변수 필요

• 생성자 IntQueue

- 큐 본체용 배열을 생성하는 준비작업 수행

---

// 큐에 데이터를 만듬
public int enque(int x) throws OverflowIntQueueException {
    if(num >= capacity)
        throw new OverflowIntQueueException();
    que[rear++] = x;
    num++;
    if(rear == capacity)
        rear = 0;
    return x;
}

• 인큐 메서드 enque

- 큐에 데이터를 인큐하고 인큐한 값을 그대로 반환하는 메서드
- 큐가 가득차다면 OverflowIntQueueException 예외 발생

---

// 큐에서 데이터를 디큐
public int deque() throws EmptyIntQueueException {
    if(num <= 0)
        throw new EmptyIntQueueException();
    int x = que[front++];
    num--;
    if(front == capacity) 
        front = 0;
    return x;
}

• 디큐 메서드 deque

- 데이터를 디큐하고 그 값을 반환하는 메서드
- 큐가 비어 있다면(num <= 0) 예외 발생
- {3, 5, 2, 6, 9, 7, 1, 8}이 들어 있는 데이터에 3을 디큐한다.
- 그러면 que[front](que[7])에 들어있는 3값을 꺼내고 front값을 1씩 증가 그리고 num값 1 감소

---

// 큐에서 데이터를 피크(프런트 데이터를 들여다봄)
    public int peek() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();
        return que[front];
    }
    
    // 큐를 비움
    public void clear() {
        num = front = rear = 0;
    }
    
    // 큐에서 x를 검색하여 인덱스 반환
    public int indexOf(int x) {
        for(int i=0; i<num; i++) {
            int idx = (i + front) % capacity;
            if(que[idx] == x)
                return idx;
        }
        return -1; 
    }
    
    // 큐의 용량 반환
    public int getCapacity() {
        return capacity;
    }
    
    // 큐에 쌓여 있는 데이터 개수 반환
    public int size() {
        return num;
    }
    
    public boolean isEmpty() {
        return num <= 0;
    }
    
    public boolean isFull() {
        return num >= capacity;
    }
    
    // 큐 안의 모든 데이터를 프런트 -> 리어 순서로 출력
    public void dump() {
        if(num <= 0)
            System.out.println("큐가 비어 있습니다.");
        else {
            for(int i=0; i<num; i++)
                System.out.println(que[i + front] % capacity + " ");
            System.out.println();
        }
    }
}

• 검색 메서드 indexOf

- 큐 본체용 배열을 x와 값이 같은 데이터가 저장되어 있는지 위치 조사
- 스캔할때 인덱스 idx식이 (i + front) % capacity로 복잡.
- 검색에 성공하면 인덱스 반환, 실패하면 -1