목차
큐(queue)
스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조이며 순서를 기억하고, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 자료구조를 큐(queue)라고 한다.
큐의 특징
큐는 아래와 같이 데이터를 저장하고 사용한다.
- 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 형태이다.
- 한쪽 끝에서 자료의 삽입이 이루어지고, 다른쪽 끝에서 자료의 삭제가 이루어진다.
그림으로 표현하면 이러한 형태이다.
- 큐에 맨 뒤에 데이터를 넣는 작업을 인큐(enqueue) 라고 한다.
- 큐에서 맨 앞의 데이터를 꺼내는 작업을 디큐(equeue) 라고 한다.
- 데이터를 꺼내는 쪽을 front 라고 한다.
- 데이터를 넣는 쪽을 rear 라고 한다.
큐 만들기
일반 큐 에서는 디큐를 할 때 배열 전체를 하나씩 앞으로 옮겨야(shift) 한다. 이 처리의 복잡도는 O(n)이며 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어진다.
링 버퍼
배열 요소를 앞으로 옮기지 않으려면 링 버퍼를 이용해서 큐를 구현해야한다. 링 버퍼는 다음 그림처럼 배열의 처음과 끝이 연결되어있다고 보는 자료구조이다.
- 프런트(front) : 맨 처음 요소의 인덱스
- 리어(rear) : 맨 끝 요소의 하나 뒤 인덱스(다음 요소를 인큐할 위치)
현재 그림에서 front는 7, rear는 4 이다.
3을 rear에 인큐(enqueue)하게 되면 다음과 같이 된다.
front 는 7, 맨 끝은 4, rear는 5이다.
다음에 또 인큐(enqueue)를 하려고 한다면 rear에 데이터를 넣어준 뒤 rear 값을 +1 해준다.
디큐(equeue) 를 할 경우 front의 값을 꺼낸다. 그 후 front의 값이 배열의 끝일 경우 0으로 다시 되돌아가고, 아닐 경우 +1을 해준다.
큐 본체
public class IntQueue {
private int max; //큐의 최대 용량, 배열 que 에 저장할 수 있는 최대 요소의 개수와 같다.
private int num; // 현재 데이터 수, front 와 rear 값이 같은 경우 큐가 비어있는지, 가득 찼는지 구별할 수 없는 상황이 있기 때문에 이 변수가 필요하다.
private int front; // 맨 앞
private int rear; // 맨 뒤
private int[] que; //큐 본체
//생성자. capacity 크기의 배열을 생성.
public IntQueue(int capacity){
num = 0;
front = 0;
rear = 0;
max = capacity;
try{
que = new int[max]; //큐 본체용 배열 생성
}catch(OutOfMemoryError e){
max = 0;
}
}
// 큐가 비어있을 때 예외
public class EmptyIntQueueException extends RuntimeException{
public EmptyIntQueueException(){}
}
// 큐가 가득 찼을 때 예외
public class OverflowIntQueueException extends RuntimeException{
public OverflowIntQueueException(){};
}
}
생성자 IntQueue
생성 시 큐는 비어있기 때문에 num, front, rear 값을 모두 0으로 한다. 요솟수가 max인 배열 que의 본체를 생성한다.
인큐(enqueue)
public int enque(int x) throws OverflowIntQueueException{
if(num >= max){ // 큐가 가득 차 인큐할 수 없으면 예외를 던진다.
throw new OverflowIntQueueException();
}
que[rear++] = x;
num++;
if(rear == max){ //큐의 최대 용량 값인 max와 같아질 경우 rear 를 배열의 처음인 0으로 변경한다.
rear = 0;
}
return x;
}디큐(dequeue)
public int deque() throws EmptyIntQueueException{
if(num<=0){ // 큐가 비어있어 디큐할 수 없다면 예외를 던진다.
throw new EmptyIntQueueException();
}
int x=que[front++];
num--;
if (front == max) { // 큐의 용량인 max와 같아지면 front 값을 배열의 처음인 0으로 변경한다.
front=0;
}
return x;
}
검색 메서드(indexOf)
public int indexOf(int x){
for(int i=0; i<num; i++){
int idx = (i+front) % max;
if(que[idx] == x){
return idx;
}
}
return -1;
}큐의 배열에서 x와 같은 데이터가 저장되어 있는 위치를 알아낸다. front 에서 rear 쪽으로 선형 검색을 수행한다. 검색에 성공하면 찾은 요소의 인덱스를 반환하고 실패하면 -1을 반환한다.
참고
방송통신대학교 자료구조 수업
자료구조와 함께 배우는 알고리즘 입문