1. 자료구조 큐 이해하기
2. 자료구조 큐의 로직 이해
3. 자료구조 큐와 오퍼레이션 구현하기
4. 라이브러리 이용하여 큐 사용하기
1. 자료구조 큐 이해하기
(1) 큐(Queue)란?
음식점에 늘어져 있는 대기 줄과 같이 한쪽에서는 삽입, 다른 한쪽에서는 삭제 연산이 발생하는 자료구조. 먼저 들어간 원소가 먼저 삭제되는 선입선출 방식(FIFO)이다.
(2) 큐의 오퍼레이션
큐에는 rear와 front라고 부르는 포인터가 존재하며 이들이 가리키는 위치에 따라 삽입, 삭제 연산이 이루어진다. 일반적으로 큐에서의 삽입은 Enqueue, 삭제는 Dequeue라고 부르며 이외에도 가장 첫번째 원소를 반환하는 peek 등의 오퍼레이션이 있다.
-Enqueue: rear가 가리키는 위치에 원소를 삽입한다.
-Dequeue: front가 가리키는 위치에 있는 원소를 삭제한다.
-Peek: 가장 첫번째에 있는 원소를 삭제하지 않고 반환한다.
(3)큐의 응용
먼저 들어간 원소가 먼저 나오는 식의 순서성을 띄기 때문에 어떤 작업의 스케쥴링을 관리하는 경우에 활용된다.
예) CPU 관리기법 - FCFS(First-Come First-Served) 스케쥴링 기법, RR(Round Robin) 스케쥴링 기법
(4) 문제점
큐에서 삽입과 삭제를 반복하다보면 큐가 비어있음에도 빈 공간에 원소를 삽입하지 못하는 상황이 발생한다. 이 때문에 빈 공간을 활용하지 못한다는 문제점이 발생하는데, 원형 큐를 이용하면 이 부분을 해결할 수 있다. 원형 큐에 대한 내용은 뒷 부분에 더 설명하도록 하겠다.
2. 자료구조 큐의 로직 이해
(1) 삽입 (Enqueue)
초기 front와 rear는 -1로 초기화 되어있다가 삽입 연산이 시행되고 큐에 공간이 있다면 rear 포인터를 하나 증가 시킨 자리에 원소를 삽입한다. rear가 큐의 크기인 max에 1을 빼준 max-1와 같아졌을 때 큐는 가득 찬 상태가 된다.
(2) 삭제 (Dequeue)
삭제 연산 시에는 큐가 비어있는지 확인한후 비어 있지 않다면 front 포인터를 증가시키고 해당 자리에 위치한 원소를 하나 삭제한다.
계속된 삭제 연산으로 front 와 rear가 같아지면 큐가 비어있다고 간주한다.
여기서 하나 예를 들어보자. 크기가 6인 큐를 생성하고 삽입 연산을 6번 시행한다면 rear가 인덱스 [5]에 도달하여 큐가 가득 찬 상태가 될 것이다. 이 상태에서 삭제 연산을 3번 실행하면 front가 인덱스[2]에 도달하게 된다. 따라서 해당 큐에는 실질적으로 2개의 원소를 저장할 수 있는 공간이 있다. 하지만 rear가 max-1과 같아졌기 때문에 여유 공간이 있음에도 큐에 더이상 삽입을 할 수 없어 공간 낭비가 발생한다.
이러한 점을 보안하기 위하여 원형 큐를 사용할 수 있다.
기존의 큐는 양쪽이 뚫려 있는 파이프 형태였다면 원형 큐는 파이프의 출입구를 연결시켜 원형의 형태를 갖고있다.
rear와 front값은 rear = (rear + 1) % max 와 front = (front + 1) % max 식을 이용하여 (구현하는 방법에 따라 달라질 수 있음) 조정을 해주기 때문에 삽입과 삭제가 반복되어도 여유공간을 최대로 활용할 수 있다.
위의 그림처럼 rear가 max-1의 위치해 있어도 큐가 공간이 있다면 다음 빈 공간에 새로운 원소를 저장할 수 있다.
3. 자료구조 큐와 오퍼레이션 구현하기
지금까지 배워본 내용을 토대로 하여 큐를 직접 구현해 보도록 하자.
(1) 큐
class MyQueue {
int rear = -1;
int front = -1;
int max;
int[] queue;
public void create_q(int max){
this.max = max;
queue = new int[this.max];
}
public boolean is_full(){
return rear == max -1;
}
public boolean is_empty(){
return front == rear;
}
public void add_q(int element){ //큐에 데이터 추가
if(!is_full()){
queue[++rear] = element;
}else{
System.out.println("queue is full");
}
}
public int delete_q(){ //큐의 첫번째 요소 반환 후 제거
if(!is_empty()){
return queue[++front];
}
System.out.println("queue is empty");
return -1;
}
public int peek(){ //첫번째 요소 반환
if(!is_empty()){
return queue[front+1];
}
System.out.println("queue is empty");
return -1;
}
public void clear(){ //큐 초기화
if(!is_empty()){
queue = new int [this.max];
rear = -1;
front = -1;
}
}
}
(2) 원형 큐
public class CircularQueue {
int rear = -1;
int front = -1;
int max;
int count = 0;
int[] queue;
public void create_q(int max){
this.max = max;
queue = new int[this.max];
}
public boolean is_full(){
return count == max;
}
public boolean is_empty(){
return count == 0;
}
public void add_q(int element){ //큐에 데이터 추가
if(!is_full()){
rear = (rear+1) % max;
queue[rear] = element;
count++;
}else{
System.out.println("queue is full");
}
}
public int delete_q(){ //큐의 첫번째 요소 반환 후 제거
if(!is_empty()){
front = (front+1) % max;
count--;
return queue[front];
}
System.out.println("queue is empty");
return -1;
}
public int peek(){ //첫번째 요소 반환
if(!is_empty()){
front = (front + 1) % max;
return queue[front];
}
System.out.println("queue is empty");
return -1;
}
public void clear(){ //큐 초기화
if(!is_empty()){
queue = new int [this.max];
rear = -1;
front = -1;
}
}
}
4. 라이브러리 이용하여 큐 사용하기
재사용성, 협업 등의 이유로 큐를 직접 구현하여 사용하기 보다는 라이브러리를 이용하는 경우가 일반적이다.
JAVA에서는 큐를 클래스로 정의해놓지 않고 인터페이스로만 제공하고 있기 때문에 큐 인터페이스를 구현한 클래스를 사용하면 된다.
import java.util.*;
Queue<Integer> q = new LinkedList<>(); //int형 큐 선언 및 생성
//원소 삽입
q.add(1);
q.offer(2);
q.offer(3);
//가장 첫번째 원소 반환 후 삭제
q.remove();
q.poll();
//삭제하지 않고 가장 첫번째 원소 반환
q.peek();
q.element();
위 표에서 볼 수 있듯이 두번째 열에 나열된 메서드들은 에러 발생 시 예외 처리하고, 세번째 열의 메서드들은 에러 발생 시 false 혹은 null을 반환한다.
참고: Java의 정석, 자료구조 [한국방송통신대학교], Java API
*해당 게시글은 개인 공부 목적으로 작성되었습니다.