자바로 구현하는 큐 (Queue)

큐(Queue) ?

 

큐(queue)는 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다.

나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

 

<그림> Queue 의 과정

 

 

 

큐의 데이터 삽입, 추출 과정

 

큐에서 front 는 가장 먼저 큐에 들어온 첫번째 원소 이고,

rear 는 큐에 가장 늦게 들어온 마지막 원소가 된다.

 

 

공백 큐 상태에서는 삽입된 데이터의 위치를 나타내는 rear, 삭제된 데이터의 위치를 나타내는 front

의 위치가 일치하면 공백 큐 임을 알 수 있습니다.

 

 

 

 

큐에 데이터 A를 삽입하였을때, rear 는 A의 위치를 가르키게 됩니다.

이유는 가장 마지막에 들어온 원소를 가르켜야 하기 때문 입니다.

 

이번에는 큐에 데이터 B를 삽입하였을때, rear 는 B의 위치를 가르키게 됩니다.

이유는, B가 A보다 늦게 들어왔기 때문 입니다.

 

이번에 반대로 deQueue 를 통해 데이터를 추출해본다면, A의 원소가 먼저 빠지는 것을 알수 있습니다.

가장 먼저 들어온 원소는 바로 A 이기 때문 입니다.

그리고 front 는 A의 위치를 가르키게 됩니다.

이유는, 다음에 deQueue 를 하였을때 바로 다음 원소 B를 추출하기 위함 입니다.

 

이번에도 deQueue 를 통해 배열[1] 위치에 있던 B 데이터를 추출 하였습니다.

이로서 A,B 순으로 삽입시 A,B 순으로 추출되었음을 알 수 있습니다.

그리고 front 는 한칸 옮겨졌으니 rear 와 같은 위치가 되었습니다.

rear == front 즉 공백 큐가 되었다는 사실 을 알수있습니다.

 

 

 

 

이번 포스팅에서는 큐에 대한 내부구조를 구현해보도록 하겠습니다.

 

(Java Collections Framework 에서는 JDK 1.5 부터 Queue 인터페이스 및 클래스를 제공 하고 있습니다.

Queue를 구현한 클래스는 PriorityQueue, PriorityBlockingQueue, LinkedList 등이 있습니다.)

 

 

 

참고

[1] Queue wiki : http://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

 

 

 

큐의 주요 API

enQueue : 큐에 데이터를 삽입 한다. (큐가 포화상태인 경우 Overflow 발생) 

deQueue : 큐에 데이터를 추출 한다. (큐가 비어있는 경우 Underflow 발생)

isEmpty : 큐가 비어있는지 확인한다.

isFull : 큐가 포화상태 인지 확인한다.

 

수도코드

 

큐의 삽입 연산

enQueue (Q, element)

  if (isFull(Q)) then Overflow;
  else {
    rear <- rear+1;
    Q[rear] <- element;
  }

end enQueue()

 

해설 : 큐가 포화 상태이면 Overflow 발생 하며, rear 의 위치는 마지막 입력한 데이터의 위치를 가르키게 됩니다.

 

큐의 삭제 연산

deQueue (Q) 
  if (isEmpty(Q)) then Underflow;
  else {
    front <- front+1;
    return Q[front];
  }
end deQueue

 

해설 :  큐에 있는 데이터가 비어 있다면 Underflow 발생 하며, front 의 위치는 가장 처음 데이터를 삭제할 위치를 가르키게 됩니다.

          그리고 해당 위치에 있는 데이터를 리턴합니다.

 

 

공백큐 검사

isEmpty(Q) 

 if (front = rear) then return true;
 else return false;

end isEmpty

 

해설 : front 와 rear 의 위치가 같은 경우 데이터가 없으므로 true 리턴, 아닌 경우 false 리턴

 

큐포화 상태 검사

isFull(Q)

 if (rear=n-1) then return true;
 else return false;

end isFull()

 

해설 : rear 의 위치가 n (큐의 크기)-1 이라면 포화 상태가 됩니다. (배열은 0 부터 시작 하기때문)

 

 

자바 소스코드

 

public class Queue {
	
	private Object[] queue;
	private int size = 0;
	private int rear = -1;
	private int front = -1;
	
	Queue(int size) {
		this.size = size;
		//사이즈 만큼 큐 생성
		this.queue = new Object[size];
	}
	
	public void enQueue(Object element) {
		
		//큐 포화상태 검사
		if (isFull()) {
			throw new QueueOverflow();
		}
		
		queue[++rear] = element;
	}
	
	public Object deQueue() {
		
		//공백큐 검사
		if (isEmpty()) {
			throw new QueueUnderflow();
		}
		
		++front;
		Object temp = queue[front];
		
		//help gc;
		queue[front] = null;
		
		//비어있다면 다시 원점으로 초기화
		if (isEmpty()) {
			rear = -1;
			front = -1;
		}
		
		return temp;
	}
	
	public boolean isFull() {
		return rear == size-1 ? true : false;
	}
	
	public boolean isEmpty() {
		return front == rear ? true : false;
	}
	
	public int getSize() {
		return size;
	}
	
	
	static class QueueOverflow extends RuntimeException {
		
	}

	static class QueueUnderflow extends RuntimeException {
		
	}
}

public static void main(String[] args) {

	Queue queue = new Queue(5);
	queue.enQueue("A");
	queue.enQueue("B");
	queue.enQueue("C");
	queue.enQueue("D");
	queue.enQueue("E");
		
	int size = queue.getSize();
	for(int i=0;i<size;i++) {
		System.out.println(queue.deQueue());
	}

	//공백큐 인데 뺄경우
	System.out.println(queue.deQueue());

}