[프로그래밍, 자료구조] 큐(Queue)

큐는 FIFO(First In First Out) 형태의 자료구조로 먼저 들어간 데이터가 먼저 빠져나가는 것이다.

실생활에서 이와 비슷한 내용은 버스 줄서기로 먼저 줄을 선 사람이 먼저 버스를 탄다.

이를 구현하는 방법은 여러가지 방법이 있는데, 여기서는 데이터 구조를 원형처럼 생각해서 구현하는 방법을 이용하였다. 디버그의 편의성을 위해서 총 4개의 파일로 분할해서 만들었다.

첫 번째는 배열의 크기가 0이면 에러를 발생시키게 하는 파일 소스이다.

public class EQException extends Exception{
	public EQException(){
		super("The queue is empty!");
	}
}

두 번째는 interface로 Queue에 필요한 메서드를 선언하는 파일 소스이다.

public interface Queue<E> {
	public void enqueue(E element);
	
	public E front() throws EQException;
	
	public E dequeue() throws EQException;
	
	public boolean isEmpty();
	
	public int size();
}

세 번째는 앞에서 선언한 메서드에 대한 body부분을 작성하는 파일 소스이다.

public class QueueArray<E> implements Queue<E> {
	private E[] data;
	private int size, front, back;
	
	static final int DEFAULT_CAPACITY = 2;
	public QueueArray(){
		data = (E[]) new Object[DEFAULT_CAPACITY];
		
		size = 0;
		front = 0;
		back = -1;
	}
	
	public boolean isEmpty(){
		return (size==0);
	}
	
	private int increment(int i){
		return ((i+1)%data.length);
	}
	
	public void enqueue(E element){
		if(size==data.length){
			expandArray(2);
		}
		back = increment(back);
		data[back] = element;
		size++;
	}
	
	public E dequeue() throws EQException {
		if(isEmpty()) {
			throw new EQException();
		}
		size--;
		E returnValue = data[front];
		front = increment(front);
		return returnValue;
	}
	
	public E front() throws EQException{
		if(isEmpty()){
			throw new EQException();
		}
		return data[front];
	}
	
	public int size(){
		return size;
	}
	
	private void expandArray(int n){
		System.out.println("Expanding array...");
		E[] newArray = (E[])new Object[n*data.length];
		
		if(front <= back){
			for(int i = front; i<= back; i++){
				newArray[i-front] = data[i];
			}
		} else {
			int i;
			for(i=front; i<data.length; i++){
				newArray[i-front] = data[i];
			}
			for(int j=0; j<=back; j++,i++){
				newArray[i-front] = data[j];
			}
		}
		data = newArray;
		front = 0;
		back = front + size - 1;
	}
	
	public String toString(){
		if(size==0){
			return "[]";
		}
		String result = "[ ";
		if(front <= back) {
			for(int i = front; i<=back; i++){
				result += i + ":" + data[i] + ", ";
			}
		} else {
			for(int i = front; i<data.length; i++){
				result += i + ":" + data[i] + ", ";
			}
			for(int i = 0; i<=back;i++){
				result += i + ":" + data[i] + ", ";
			}
		}
		result = result.substring(0, result.length()-2);
		result += " ]";
		return result;
	}
}

마지막은 main 함수로 앞에서 선언한 Queue가 제대로 작동하는지 확인하는 내용이다. 이 부분은 직접 선언해서 함수들이 잘 작동하는지 확인해본다.

자바, java, 자료구조, 큐, queue