큐

큐란?

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다. 

가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조로 되어 있습니다.

 

인큐(enque) : 큐에 데이터를 넣는 작업

디큐(deque) : 데이터를 꺼내는 작업

프런트(front) : 데이터를 꺼내는 쪽

리어(rear) : 데이터를 넣는 쪽 

 

배열로 큐 만들기 

인 큐 할때 시간 복잡도 : O(1)

디 큐 할때 시간 복잡도 : O(n) → 첫 요소를 꺼낸 다음에 두번째 이후의 요소를 모두 맨 앞으로 옮긴다. (비효율적)

 

링 버퍼로 큐 만들기

링 버퍼는 배열의 처음이 끝과 연결되어있다고 보는 자료구조이다. (배열 요소를 앞쪽으로 옮기지 않아도 된다.)

- 프런트 : 맨 처음 요소의 인덱스

- 리어 : 맨 끝 요소의 하나 뒤의 인덱스 (다음 요소를 인큐할 위치를 미리 지정)

 

인큐 메서드 enque

큐에 데이터를 인큐하는 메서드.

인큐에 성공하면 인큐한 값을 그대로 반환합니다.

큐가 가득 차서 인큐할 수 없으면 내가 만든 예외 클래스(OverflowIntQueueException)를 던집니다.

인큐하고 rear 와 num의 값을 1만큼 증가하고, rear 값과 max값이 같아질 경우 rear를 배열의 처음인 0으로 변경해야 합니다.

 

디큐 메서드 deque

큐에서 데이터를 디큐하고 그 값을 반환하는 메서드.

만약 큐가 비어 있어 디큐할 수 없으면 예외 EmptyIntQueueException을 던집니다.

큐에 저장한 값 하나를 꺼내고 front 값을 1만큼 증가, 다음 num값을 1만큼 감소합니다.

front값이 max의 값과 같아질 경우 front 값을 배열의 처음인 0으로 변경해야 합니다.

 

package Chapter04;
 
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];
    }
 
    // 큐에서 x를 검색하여 인덱스 (찾지 못하면 -1)를 반환
    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 capacitiy() {
        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.println(que[(i + front) % max] + " ");
                System.out.println();
            }
        }
    }
 
}
 

 

 

---

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 [시바타 보요, 옮긴이 : 강민 (이지스퍼블리싱)]