큐란?
Queue란
스택과 마찬가지로 데이터를 일시적으로 쌓아두는 자료구조를 칭한다.
데이터 입출력 순서는 선입선출(FIFO: First In First Out)이다.
Queue에 데이터를 넣는 작업을 'en-queue', 꺼내는 작업을 'de-queue'라고 한다.
데이터가 나오는 곳을 'Front', 데이터가 들어가는 곳을 'Rear'라고 한다.
위 이미지는 큐의 동작방식을 이미지로 표현한 이미지이다.
실생활에서 보면 은행창구 대기열이나, 마트 대기열과 동일하다고 생각하면 된다.
큐 만들기
스택과 마찬가지로 큐도 배열을 이용하여 구현할 수 있다.
또한 Java에서도 Queue클래스가 존재하여 그것을 사용할수도 있다.
하지만 자료구조 탐색을 위해 배열을 이용하여 큐를 구현해보자.
public class IntArrayQueue {
private int[] que; // queue용 배열
private int capacity; // 용량
private int num; // 데이터의 갯수
// 생성자
public IntArrayQueue(int maxlen) {
num = 0
capacity = maxlen;
try {
que = new int[capacity]; // 큐 생성
} catch(OutOfMemoryError e) {
capacity = 0; // 생성할 수 없을때
}
}
// de-queue 예외
public class EmptyIntArrayQueueException extends RuntimeException {
public EmptyIntArrayQueueException() {}
}
// en-queue 예외
public class OverflowIntArrayQueueException extends RuntimeException {
public OverflowIntArrayQueueException() {}
}
}위와 같이 생성자를 통해서 Queue를 생성하였다.
de-queue, en-queue시 발생하는 예외에 대하여 처리하였다.
이전 포스팅에서 처럼 스택과 거의 흡사하다. 다른점이 있다면 큐는 FIFO인점을 생각해야한다.
선입선출 구조를 가진 큐에 특성을 생각하여 enque, deque메서드를 작성해보자.
enque(추가)
큐에 데이터를 추가하기 위한 작업을 en-queue라고 한다.
생성자를 통해 만들어진 큐에 데이터를 추가하기 위한 용도의 enque 메서드를 작성해보았다.
public int enque(int x) throws OverflowIntArrayQueueException {
try {
que[num++] = x;
} catch(OverflowIntArrayQueueException e) {
throw new OverflowIntArrayQueueException();
}
return x; // enque 성공시 해당 값이 추가되었다는 메세지를 위해 x를 반환해줬다.
}이렇게 하면 데이터를 큐에 추가할 수 있다.
deque(데이터 꺼내기)
큐에서 데이터를 꺼내는 작업을 de-queue라고 한다.
생성된 큐에서 front에 있는 데이터를 꺼낸다.
public int deque() throws EmptyIntArrayQueueException {
int x;
try {
x = que[0];
for(int i = 0; i < num - 1; i++) {
que[i] = que[i + 1];
}
num--;
} catch(EmptyIntArrayQueueException e) {
throw new EmptyIntArrayQueueException();
}
return x;
}위와 같은 코드를 통해 큐에서 de-queue를 수행할 수 있다.
스택과 다르게 front의 데이터를 꺼내다보니 뒤에 있는 요소들을 반복문을 통하여 전부
한 칸씩 앞으로 미뤄줘야 한다. 이러한 작업은 요소가 많을 수록 비용이 더 커진다.
이러한 비효율적인 방법을 개선하기 위해 링버퍼라는 자료구조가 존재한다.
링버퍼를 사용하여 큐를 구현하면, de-queue 수행 후 요소를 한 칸씩 옮기는 작업을 하지 않아도 된다.
링 버퍼를 이용하여 큐 만들기
링버퍼를 이용하면 front의 요소를 de-queue 한다 해도 큐의 요소들을
front 쪽으로 한칸씩 옮기지 않아도 된다.
링 버퍼는 그림처럼 배열의 맨 뒤가 맨 앞과 연결되어 있다고 보는 자료구조이다.
여기서 논리적으로 어느 요소가 맨 앞인지 맨 뒤인지 식별하기 위해서
front, rear 변수를 사용하여 식별한다.
링 버퍼에서의 front와 rear는 논리적인 데이터 순서를 말한다.
(배열 요소의 물리적인 나열 순서를 말하는 것이 아니다.)
이런식으로 큐를 구성하면 위에서 이전에 구성한 큐에서 발생한 요소 이동 문제를 해결할 수 있다.
이전에 구성한 큐 : 처리 복잡도 -> O(n)
링버퍼로 구성한 큐 : 처리 복잡도 -> O(1)
IntQueue Class (링버퍼로 구성한 큐 구현)
public class IntQueue {
private int[] que; // 큐용 배열
private int capacity; // 큐의 용량
private int front; // 큐의 front 커서
private int rear; // 큐의 rear 커서
private int num; // 큐에 들어있는 데이터의 수
// 생성자
private IntQueue(int maxlen) {
capacity = maxlen;
num = front = rear = 0;
try {
que = new int[capacity];
} catch(OutOfMemoryError e) { // 생성 실패시 처리
capacity = 0;
}
}
// 큐가 비어있을 때 예외
public class EmptyIntQueueException extends RuntimeException {
public EmptyIntQueueException() {}
}
// 큐가 가득 찼을 때 예외
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() {}
}
}위와 같이 링 버퍼를 이용하여 큐를 구성한다.
달라진 점은 front와 rear 필드변수가 새로 생겼다.
이제까지 front와 rear는 물리적으로 배열의 앞과 뒤를 지칭하였지만 링 버퍼의 자료구조를 활용하면
front와 rear는 논리적으로 구성된다.
이제 큐에 데이터를 넣는 메서드를 작성해보자
en-queue
public int enque(int x) throws OverflowIntQueueException {
if(num >= capacity) { // 들어있는 데이터 갯수가 용량 이상일때 예외 던지기
throw new OverflowIntQueueException();
}
que[rear++] = x; // 데이터가 추가될때마다 맨 뒤가 바뀌므로 rear를 증가
num++; // 데이터가 추가되었으니 num을 증가
if(rear == capacity) { // rear와 capacity가 같아지는걸 방지하기 위한 조건
rear = 0;
}
}en-queue를 했을때 동작이 조금 달라졌다.
que에 데이터를 집어넣을때 rear를 증가시킨다.(FIFO인것을 잊지말자)
num 변수는 que에 들어있는 데이터의 수를 나타내기 때문에 같이 증가시키자
rear가 capacity가 같아지면 배열의 용량을 초과하기 때문에 문제가 발생한다. (OutOfIndex예외 발생)
초과하지 않도록 용량고 rear가 같아지면 0으로 만들어주자.
de-queue
public int deque() throws EmptyIntQueueException {
if(num <= 0) { // 데이터가 없을 경우 예외 발생
throw new EmptyIntQueueException();
}
int x = que[front++]; // 가장 앞의 요소를 가져오고 front를 증가시킨다.
num--;
if(front == capacity) { // front의 인덱스가 용량을 초과해선 안되기 때문에 처리
front = 0;
}
}deque 메서드를 통해 Queue에 들어있는 데이터(가장 앞에 있는)를 반환하도록 만들었다.
데이터가 Queue에 들어있는지 확인하고 Queue에 데이터가 없으면
de-queue를 할 수 없으므로 예외를 던진다. 그게 아니라면 반환할 값을 변수에 담고
front 포인터를 1증가 시켜 논리적으로 front를 이동시킨다.
물론 de-queue가 되었으니 num 변수도 감소시켜준다.
front도 아까 rear와 마찬가지로 capacity(용량)의 인덱스를 넘어가면 OutOfIndex 예외가 발생할 것이므로
문제가 생기지 않도록 조건으로 처리해준다.
이제 마지막으로 링 버퍼로 구성한 큐를 사용한 간단한 프로그램을 작성해보자.
링 버퍼로 구성된 큐를 사용하는 프로그램 작성
Main
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
IntQueue s = new IntQueue(64); // 큐 생성 <- 아까 위에서 만든 큐 클래스
while(true) {
System.out.println();
System.out.println("현재 데이터 개수: %d / %d\n", s.size(), s.getCapacity);
System.out.println("(1) 인큐 (2) 디큐 (3) 피크 (4) 덤프 (0) 종료");
int menu = sc.nextInt();
if(menu == 0) {
break;
}
int x;
switch(menu) {
case 1:
System.out.print("데이터: ");
x = sc.nextInt();
try {
s.enque(x);
} catch(IntQueue.OverflowIntQueueException e) {
System.out.println("큐가 가득 찼습니다.");
}
break;
case 2:
try {
x = s.deque();
System.out.println("디큐한 데이터는 " + x + "입니다.");
} catch(IntQueue.EmptyIntQueueException e) {
System.out.println("큐가 비어 있습니다.");
}
break;
case 3:
try {
x = s.peek();
System.out.println("피크한 데이터는 " + x + "입니다.");
} catch(IntQueue.EmptyIntQueueException e) {
System.out.println("큐가 비어 있습니다.");
}
break;
case 4:
x = s.dump();
break;
}
}
}위와 같이 아까 작성한 링버퍼로 구성된 Queue를 사용하는 프로그램을 작성하였다.
이제 사용자가 입력한대로 메뉴에 따라 원하는 결과를 출력할 것이다.
하지만 지금 문제가 몇가지 있다. 우리가 IntQueue 클래스에 작성하지 않은 메서드를 몇가지 사용하고 있다.
size, getCapacity, dump, peek 4가지 메서드는 우리가 작성하지 않았으니 IntQueue 클래스에 추가해보자
size
큐에 있는 데이터의 갯수를 반환하는 메서드
public int size() {
return num;
}getCapacity
큐의 용량을 반환하는 메서드
public int getCapacity() {
return capacity;
}dump
큐에 존재하는 모든 데이터를 출력하는 메서드
public void dump() {
if(num <= 0) {
System.out.println("큐가 비어 있습니다.");
} else {
for(int i = 0; i < num; i++) {
System.out.println(que[(i + front) % capacity] + " ");
}
System.out.println();
}
}peek
큐에 가장 앞에 있는 데이터 반환
public int peek() throws EmptyIntQueueException {
if(num <= 0) {
throw new EmptyIntQueueException();
}
return que[front];
}위와 같이 메서드를 추가하면 프로그램이 정상적으로 작동한다.
