[자료구조] Java Queue 구현 / 자바 큐 구현

이번엔 Queue와 관련된 자료구조에 대해 공부하려고 한다.

Queue는 Stack과는 반대로, FIFO(First In First Out)성질을 갖는다. 즉 먼저 들어온 녀석이 먼저 나간다.

Queue의 가장 흔한 예시로는 프린트 출력 대기열을 들 수 있는데, 먼저 출력 요청한 문서를 먼저 출력해야 하기 때문이다. 비슷한 예로 입장 대기줄 등이 있다. 

큐는 탐색에서도 스택과 함께 많이 쓰이므로 잘 알아두면 좋다. 특히 큐는 우선순위 큐, 원형 큐 ... 등 많은 종류가 있기 때문에, 기본 큐는 반드시 알아야 한다.

---

Queue에는 어떤게 필요할까?

Queue는 Stack과 비슷한 자료구조로, 데이터를 삽입하고 반환할 수 있어야 한다. Stack처럼 제일 위에 삽입한다고 생각해도 된다. 다만 Stack과의 차이점은 시작점과 끝점이 있어야 한다는 것이다. Stack은 top이라는 시작점만 존재했지만, Queue는 끝점도 가져야하는 이유는 다음과 같다.

1. 제일 먼저 들어온 녀석을 반환하기 위함
2. 큐가 가득 찼는지 확인하기 위함.

즉 Queue에도 Top만 존재했다면, 어느 녀석을 먼저 반환해야 할지, 새로 들어온 녀석은 어디로 들어와야 할지를 동시에 수행할 수 없기 때문에 끝점도 존재해야 하는 것이다.

그렇다면 rear는 어떻게 활용할 수 있을까? Queue에 데이터가 삽입되면 rear가 하나씩 증가하게 된다. 이를 조금 더 생각 해 보면, front와 rear가 같다면, Queue가 비어있는 상황이 되고, rear가 capacity와 같아지게 되면 Queue가 가득차게 되는 것이다.

따라서 Queue는 front, rear, capacity 그리고 queue를 담는 배열이 필요하다.

---

Queue 구현

Queue의 기본은 다음과 같다.

public class Queue {
	int front;
	int rear;
	int capacity;
	Object[] queue;
	Queue(int capacity){
		this.front = -1;
		this.rear = -1;
		this.capacity = capacity;
		queue = new Object[this.capacity];
	}
	
	public boolean isFull() {
    /*
    capacity가 10이면 배열은 0~9를 갖고, rear도 0부터 시작하기 때문에 -1을 해야한다.
    */
		return (this.rear == this.capacity-1); 
	}
	
	public boolean isEmpty() {
    /*
   	front와 rear가 같으면 비어있는 상태이기 때문에, 편의를 위해 front와 rear를 -1로 초기화 시켜준다.
    */
    	if(front == rear) {
			front = -1;
			rear = -1;
		}
		return (this.front == this.rear);
	}
}

다음으로 Queue에 데이터를 삽입하고 반환하는 함수가 필요한데, Stack에서는 이를 pop, push라고 했다면 Queue에서는 enqueue, dequeue라고 한다.

데이터를 반환하기 위해서는 front에 있는 먼저 들어온 녀석을 반환해줘야 하는데, 반환 해줄 때 마다 front의 위치를 옮겨주어야 한다.

 

왼쪽이 간편해 보인다.

위 그림을 보면, 다음 출력 문서의 위치 front는 고정되어 있고, 남아있는 문서들을 한칸씩 옮기는 오른쪽 그림과 다음 출력 문서의 위치 front를 이동시키고 남아있는 문서들은 고정되어 있는 왼쪽 그림중 어느 것이 더 편해 보이겠는가?

정답은 당연히 왼쪽 그림인 front를 옮기는게 훨씬 간단하다.

이렇게 dequeue에서 front를 옮기기 때문에, rear의 위치 또한 단순히 배열의 index를 옮겨서는 안되고, 한가지 트릭을 써야 한다. (만약 n칸짜리 queue에서 n개를 넣고 dequeue를 n번 하면, front와 rear의 크기는 같아지게 된다. 즉 queue는 비어있게 되는데, 문제는 rear의 위치가 capacity와 같아지기 때문에 동시에 가득찬 상황이 된다. 이는 Queue의 모순이지 않는가?)

rear에 사용할 트릭은, 단순히 index를 지정하는 게 아니라 Queue의 capacity로 나누어서 나온 몫이 rear의 index가 되게 해야 한다. 위 괄호안에서 든 예시로 말하자면, capacity가 10이라고 가정 했을 때, rear와 front는 모두 9가 되는 상황이다. 이 때, (rear+1) % (capacity = 10) 을 하면 삽입할 다음 index는 0이 되고, rear와 front의 차이는 다시금 10이 되기 때문에 처음부터 넣는것과 같게 된다. (+1을 해주는 이유는, 삽입할 element는 다음 번 index를 가져야 하기 때문이다.)

이를 바탕으로 enqueue를 설계하면 다음과 같다.

public class Queue {
	...
	public void enqueue(Object element) {
		if(isFull()) {
			System.out.println("Queue is Full!");
			return;
		}
		
		rear = (rear+1) % this.capacity;
		queue[rear] = element;
	}
    ...
}

dequeue 또한 enqueue와 같은 원리로 Queue의 capacity로 나눈 몫을 index로 가지면 된다. 이유는 위에서 rear에 대한 설명한 것과 같다.

public class Queue {
	...
	public Object dequeue() {
		if(isEmpty()) {
			System.out.println("Queue is empty");
			return null;
		}
		
		front = (front+1) % this.capacity;
		return queue[front];
	}
    ...
}

Queue도 Stack과 같이 element를 반환하지 않고 엿보는 peek을 가질 수 있는데, 코드는 다음과 같다.

public class Queue {
	...
	public Object peek() {
		if(isEmpty()) {
			System.out.println("Queue is empty");
			return null;
		}
		
		return queue[front+1];
	}
    ...
}

 

이제 queue의 size와 초기화를 시켜주는 함수를 만들면 된다.

size는 rear - front를 통해 구할 수 있다. 이는 내가 마지막으로 삽입한 index - 제일 먼저 삽입한 index가 되고, 5개 입력했으면 다음과 같기 때문이다 (5-0) = 5. 그런데 배열은 0부터 시작하기 때문에 front와 rear에 각각 1씩 더해주면 된다. ( (4+1) - (-1+1) ) = 5. 또한 Queue는 front와 rear의 index가 역전될 수 있으니, 절대값 으로 반환하면 된다.

초기화는 간단하게 front, rear, 모두 -1로, 그리고 queue 배열을 새로 선언하면 된다. 

코드는 다음과 같다.

public class Queue {
	...
	public int size() {
		return Math.abs( (rear+1) - (front+1) );
	}
	
	public void clear() {
		if(isEmpty()) {
			System.out.println("Queue is already empty!");
		}
		else {
			front = -1;
			rear = -1;
			queue = new Object[this.capacity];
			System.out.println("Queue has cleared!");
		}
	}
}

---

Queue 코드 전체 및 실행결과

 

public class Queue {
	int front;
	int rear;
	int capacity;
	Object[] queue;
	Queue(int capacity){
		this.front = -1;
		this.rear = -1;
		this.capacity = capacity;
		queue = new Object[this.capacity];
	}
	
	public boolean isFull() {
		return (this.rear == this.capacity-1);
	}
	
	public boolean isEmpty() {
		if(front == rear) {
			front = -1;
			rear = -1;
		}
		return (this.front == this.rear);
	}
	
	public void enqueue(Object element) {
		if(isFull()) {
			System.out.println("Queue is Full!");
			return;
		}
		
		rear = (rear+1) % this.capacity;
		queue[rear] = element;
	}
	
	public Object dequeue() {
		if(isEmpty()) {
			System.out.println("Queue is empty");
			return null;
		}
		
		front = (front+1) % this.capacity;
		return queue[front];
	}
	
	public Object peek() {
		if(isEmpty()) {
			System.out.println("Queue is empty");
			return null;
		}
		
		return queue[front+1];
	}
	
	public int size() {
		return Math.abs( (rear+1) - (front+1) );
	}
	
	public void clear() {
		if(isEmpty()) {
			System.out.println("Queue is already empty!");
		}
		else {
			front = -1;
			rear = -1;
			queue = new Object[this.capacity];
			System.out.println("Queue has cleared!");
		}
	}
}

아래는 실행코드이다.

public class mainQueue {
	public static void main(String[] args) {
		System.out.println("=====짧은머리 개발자=====");
		
		Queue queue = new Queue(10);
		
		queue.dequeue();
		
		for(int i = 0; i < 10; i++) {
			queue.enqueue(i);
		}
		
		System.out.println("isFull : " + queue.isFull());
		
		System.out.println("size : " + queue.size());
		
		for(int i = 0; i < 10; i++) {
			System.out.println("Dequeue : " + queue.dequeue());
			System.out.println("size : " + queue.size());
		}
		
		System.out.println("Dequeue : " + queue.dequeue());
		
		System.out.println("isEmpty : " + queue.isEmpty());
		
		queue.enqueue(555);
		System.out.println("isEmpty : " + queue.isEmpty());
		System.out.println("isFull : " + queue.isFull());
		System.out.println("peek: " + queue.peek());
	}
}

실행 결과

제네릭은 일부러 안했다. 여러분이 한번 해보세요! 쉬워요.