[DataStructure]큐(Queue)란?
알고리즘 설계 할 때 Queue는 상당히 많이 사용된다. 뿐만 아니라 MSA과 같은 환경에서 비동기 메세지처리를 위해서 Queue가 많이 사용된다. 그러므로 Queue를 이해하기 위해서 Java로 직접 구현해보도록 한다.
- 구현코드는 여기에 저장되어 있다.
큐(Queue)란 무엇인가?
Queue는 FIFO(First In First Out)방식의 자료구조이다. Queue통해서 데이터를 저장하고 저장된 데이터를 추출하면 가장 먼저 저장 된 순서대로 추출되게된다.
선형 큐(Queue)
큐도 배열을 통해서 구현할 수 있다. 이러한 배열로 큐를 구현하면 배열의 앞을 front 배열을 뒤를 rear로 하여 rear에 저장되어 front에서 추출되도록 구현 할 수 있다. 아래의 코드를 보면 enqueue()메소드를 통해서 데이터를 배열 rear에 저장하여 입력의 마지막을 표현히였고 dequeue()메소드를 통해서 front의 데이터를 추출하여 추출의 첫번째를 표현하였다.
public class Queue {
private int [] arr;
private int front;
private int rear;
private int capable;
private final int QUEUE_SIZE = 8;
public Queue() {
this.arr = new int [QUEUE_SIZE];
this.front = 0;
this.rear = 0;
this.capable = 0;
}
public void enqueue(int value) throws Exception {
if(rear == QUEUE_SIZE)
compact();
arr[rear] = value;
rear++;
capable++;
}
public int dequeue() throws Exception {
if(front == rear)
throw new Exception("empty datastructure.queue");
int value = arr[front];
front++;
capable--;
return value;
}
private void compact() throws Exception {
if(front == 0)
throw new Exception("full datastructure.queue");
int oldFront = front;
for(int i = 0; i < capable; i++){
arr[i] = arr[oldFront];
oldFront++;
}
front = 0;
rear = capable;
}
public void print() {
System.out.print("Queue{ ");
for(int i = front; i < rear; i++){
System.out.print(arr[i] + " ");
}
System.out.println("}");
}
}선형 큐(Queue)의 한계
선형큐는 front, rear의 인덱스 값이 계속 증가하므로 인덱스가 배열의 크기 이상으로 커질 수 없다. rear이 배열의 마지막 인덱스를 가리키게 되면 앞의 빈공간으로 데이터를 이동하여 뒤쪽 공간을 확보해줘야한다. 이는 시간복잡도 O(n)만큼의 시간이 소모되므로 배열의 크기가 크면 많은 리소스를 낭비하게 된다. 위 소스에 compact()메소드가 그에 대한 기능을 제공해주고 있다.
원형 큐(Circular Queue)의 등장
위와 같은 선형 큐는 compact()와 같은 메소드를 만들어줘야한다. compact()와 같은 메소드를 사용하지 않고 큐를 하나의 원형의 데이터구조로 가정하여 구현하는 큐가 원형큐이다. 큐를 사용하는 클라이언트 입장에서는 FIFO만 잘 처리되면 될 뿐 배열의 인덱스를 신경쓰지 필요가 없다. 그러므로 rear가 배열의 마지막 인덱스를 가리키면 굳지 compact와 같은 작업를 할 필요없이 배열 앞의 빈공간에 데이터를 입력하면 된다.
아래의 코드는 rear이 배열의 마지막 인덱스를 가리키고 있는 경우 0을 입력하여 다음 입력 때 배열의 인덱스 0부터 다시 입력 할 수 있도록한다. 그러므로써 compact와 같은 작업이 필요없어졌다.
public class CircularQueue {
private int [] arr;
private int front;
private int rear;
private int capable;
private final int QUEUE_SIZE = 8;
public CircularQueue() {
this.arr = new int [QUEUE_SIZE];
this.front = 0;
this.rear = 0;
this.capable = 0;
}
public void enqueue(int value) throws Exception {
if(rear == QUEUE_SIZE)
rear = 0;
arr[rear] = value;
rear++;
capable++;
}
public int dequeue() throws Exception {
if(front == rear)
throw new Exception("empty datastructure.queue");
if(front == QUEUE_SIZE)
front = 0;
int value = arr[front];
front++;
capable--;
return value;
}
public void print() {
System.out.print("CircularQueue{ ");
int i = front;
do{
if(i == QUEUE_SIZE)
i = 0;
System.out.print(arr[i] + " ");
i++;
}while (i != rear);
System.out.println("}");
}
}큐(Queue)의 사용
큐를 선형으로 구현하든 원형으로 구현하든 사실 클라이언트 측에서는 상관없다. 그러므로 클라이언트에서 사용법은 똑같다. 아래의 코드를 보면 같은 사용법과 같은 결과가 나온 것을 확인 할 수 있다.
public class Main {
public static void main(String[] args) {
try {
Queue queue = new Queue();
queue.enqueue(12);
queue.enqueue(54);
queue.enqueue(67);
queue.enqueue(91);
queue.enqueue(12);
queue.enqueue(54);
queue.enqueue(67);
queue.enqueue(91);
queue.dequeue();
queue.dequeue();
queue.enqueue(88);
queue.enqueue(45);
queue.print();
} catch (Exception e) {
throw new RuntimeException(e);
}
try {
CircularQueue queue = new CircularQueue();
queue.enqueue(12);
queue.enqueue(54);
queue.enqueue(67);
queue.enqueue(91);
queue.enqueue(12);
queue.enqueue(54);
queue.enqueue(67);
queue.enqueue(91);
queue.dequeue();
queue.dequeue();
queue.enqueue(88);
queue.enqueue(45);
queue.print();
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}