큐(queue)

1. 개념정리

1) 뒤쪽에서는 삽입이, 앞쪽에서는 삭제가 일어나는 구조

2) FIFO(First In First Out, 첫 삽입 데이터가 먼저 삭제됨)

3) java.util 패키지에 Queue 인터페이스가 있고, 이를 구현한 클래스 중 대표적인 것이 LinkedList가 있다.

 

2. 구현 코드

class ArrayQueue{	 // int[]로 구현하는 큐
    protected final int defCap = 100;	// 큐의 용량
    protected int[] queue;		// 큐로 사용할 배열
    protected int numElements = 0;	// 큐에 들어간 요소의 개수
    protected int front = 0;		// 큐의 맨 앞 인덱스
    protected int rear;			// 큐의 맨 뒤 인덱스

    public ArrayQueue() {	// 기본 생성자
        queue = new int[defCap];
        rear = defCap -1;
    }

    public ArrayQueue(int maxSize) {	// 큐의 크기를 지정한 생성자
        queue = new int[maxSize];
        rear = maxSize -1;
    }

    public void enqueue(int element) throws Exception { // 큐의 맨 뒤에 요소 추가
        if (isFull()) // 큐가 가득 찼다면 에러 발생
            throw new Exception("full queue: enqueue 실패 -> " + element);
        else{
            rear = (rear + 1) % queue.length;
            queue[rear] = element;
            numElements += 1;
        }
    }

    public int dequeue() throws Exception{ // 큐의 첫 번째 요소 제거
        if (isEmpty()) // 큐가 비어있다면 에러 발생
            throw new Exception("empty queue: dequeue 실패");
        else{
            int toReturn = queue[front];
            queue[front] = 0;
            front = (front + 1) % queue.length;
            numElements -= 1;
            return toReturn;
        }
    }

    public boolean isEmpty() { // 큐가 비어있다면 true 반환
        return (numElements == 0);
    }

    public boolean isFull() { // 큐가 가득 찼다면 true 반환
        return (numElements == queue.length);
    }
    
    public int size() { // 큐에 들어있는 요소의 개수 반환
        return numElements;
    }

    public int capacity() { // 큐의 용량 반환
        return queue.length;
    }
}

 

3. 예제 코드

// 1) 생성
ArrayQueue queue = new ArrayQueue(10);	// 크기를 정하는 큐
ArrayQueue queue2 = new ArrayQueue();	// 기본 생성자로 만드는 큐

// 2) 추가
for(int i=1 ; i<=queue.capacity() ; i++)
    queue.enqueue(i);
// queue = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

// 3) 삭제
for(int i=0 ; i<5 ; i++)
    System.out.print(queue.dequeue() + " ");
// 1 2 3 4 5
// queue = [6, 7, 8, 9, 10]