큐?
스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다.
스택을 프링글스통 이라고 한다면 큐는 그 프링글스 통의 바닥부분을 뻥 뚫어놓은 것.
즉 스택과는 다르게 먼저 넣은 데이터를 먼저 꺼내는 선입선출(FIFO, LILO)의 구조이다.
관련 용어 정리
- 인큐(enqueue) : 큐에 데이터를 넣는 작업
- 디큐(dequeue) : 큐에서 데이터를 꺼내는 작업
- 프런트(front) : 데이터를 꺼내는 쪽, 출구
- 리어(rear) : 데이터를 넣는 쪽, 입구
배열을 이용하여 큐를 만들수 있지만 디큐를 할때 데이터를 꺼내고 그 다음 데이터들을 위치이동 시키는 처리를 해야한다. 데이터를 꺼낼때마다 이런 처리를 하게되면 효율이 떨어짐
이를 해결하기 위해 보통 링 버퍼로 큐를 만들게 된다. 배열의 처음과 끝을 연결되었다고 논리적으로 보는 자료구조이다. 링 버퍼에서 프런트와 리어는 추가적인 의미를 가진다.
- 프런트 : 맨 처음 요소의 인덱스(디큐 시 가장 먼저 나갈 데이터 가리킴)
- 리어 : 맨 끝 요소의 인덱스 + 1 (인큐 시 저장할 데이터의 위치를 미리 가리킴)
인큐 및 디큐 시 이 프런트와 리어를 업데이트 해줌으로써 요소 이동 문제를 해결 가능하다.
- 인큐 / 디큐 처리할 때 복잡도
배열로 만든 일반 큐 : 복잡도 O(n)
배열로 만든 원형 큐 : 복잡도 O(1)
링버퍼로 구현한 큐
int형 자료를 저장한다고 가정.
필요한 필드는 아래와 같다.
- que : 인큐하는 데이를 저장하기 위한 배열 본체
- max : 큐의 최대 용량 = 배열 que 에 저장할 수 있는 최대 요소의 개수
- front : 원형 큐의 첫번째 요소 인덱스 저장 ( 얘가 가리키는 요소가 인큐 대상)
- rear : 원형 큐에 존재하는 데이터 중 가장 마지막에 저장된 요소의 인덱스에 1을 더한 녀석, 그냥 마지막 요소를 가리켜도 되긴하나 데이터를 넣을때 새로 저장될 요소의 인덱스를 미리 준비해두는 것
- num : 큐를 쌓아 놓은 데이터 수를 나타내는 필드, 이 녀석의 필요성은 큐가 비어있는지 가득 찼는지 구별할 때 이다. rear와 front가 값이 같을 때 이게 텅텅 빈건지 가득 찬건지는 이 num의 갯수가 max와 같은지 비교하므로써 판단 할 수 있다.
메서드들은 아래 소스코드를 보면 된다 스택 구현할때와 많이 비슷한게 있다.
public class IntQueue {
private int max; // 큐의 용량
private int front; // 첫 번째 요소 커서
private int rear; // 마지막 요소 + 1 커서
private int num; // 현재 데이터 수
private int[] que; // 큐 본체
//실행 시 예외 : 큐가 비어 있음, num = 0
public class EmptyIntQueueException extends RuntimeException {
public EmptyIntQueueException() {}
}
//실행 시 예외 : 큐가 가득 차 있음, num = max
public class OverflowIntQueueException extends RuntimeException {
public OverflowIntQueueException() {}
}
//생성자
public IntQueue(int capacity) {
num = front = rear = 0;
max = capacity;
try {
que = new int[max];
} catch (OutOfMemoryError e) {
max = 0;
}
}
//데이터를 인큐(입력)
public int enque(int x) throws OverflowIntQueueException {
if(num>=max) throw new OverflowIntQueueException();
que[rear++] = x; //rear 위치에 x를 저장, 이후 rear + 1
num++;
if(rear == max) {
rear = 0;
}
return x;
}
//데이터를 디큐(출력)
public int deque() throws EmptyIntQueueException {
if(num <= 0) throw new EmptyIntQueueException();
int x = que[front++];
if(front == max) {
front = 0;
}
return x;
}
//데이터 피크(프런트 데이터를 들여다봄)
public int peek() throws EmptyIntQueueException {
if(num<=0) throw new EmptyIntQueueException();
return que[front];
}
// 큐에서 x를 검색하여 인덱스를 반환, 못찾으면 -1
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;
}
//clear
public void clear() {
num = front = rear = 0;
}
// 큐의 용량을 반환
public int capacity() {
return max;
}
// 큐에 쌓여져 있는 데이터 수를 반환
public int size() {
return num;
}
public boolean isEmpty() {
return num <=0;
}
public boolean isFull() {
return num >= max;
}
//큐 안의 데이터를 프런트 → 리어 순으로 출력
public void dump() {
if(num<=0) {
System.out.println("큐가 비었습니다.");
return;
}
for(int i=0;i<num; i++) {
System.out.print(que[(i+front)%max]+" ");
}
System.out.println();
}
//큐에서 임의의 데이터를 검색
//배열인덱스가 아닌 프론트로부터 몇번째 있는가 반환(프론트에 있으면 1) 없으면 0
public int search(int key) {
for(int i=0; i<num; i++) {
if(que[(i+front)%max] == key) {
return i+1;
}
}
return 0;
}
public static void main(String[] args) {
}
}
NOBODY