큐란?
◽ 데이터를 일시적으로 쌓아 두기 위한 자료구조
◽ 데이터 입력과 출력 순서는 선입선출(FIFO)
◽ 배열로 큐 만들기
◽ 인큐 시간 복잡도 : O(1)
◽ 디큐 시간 복잡도 : O(n) : 꺼낸 다음 요소부터 모든 요소들을 앞으로 한 칸씩 모두 당겨야 함
◽ 링 버퍼로 큐 만들기
◽ 배열의 처음과 끝이 연결되어 있는 자료구조
링 버퍼로 큐 구현하기
본체 만들기
public class IntQueue {
private int max; // 큐의 용량
private int front; // 첫 번째 요소 커서
private int rear; // 마지막 요소 커서
private int num; // 현재 데이터 수
private int[] que; // 큐 본체
// 실행 시 예외 : 큐가 비어 있음
public class EmptyIntQueueException extends RuntimeException {
public EmptyIntQueueException() { }
}
// 실행 시 예외 : 큐가 가득 참
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;
}
}
}
◽ front : 인큐하는 데이터 가운데 첫 번째 요소의 인덱스를 저장하는 필드
◽ rear : 인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장하는 필드
◽ num : 큐에 쌓아 놓은 데이터 수를 나타내는 필드로, front와 rear의 값이 같은 경우 큐가 비어 있는지, 가득 찼는지 구별하기 위해 필요하다.
인큐 메서드 enque
// 큐에 데이터를 인큐
public int enque(int x) throws OverflowIntQueueException {
if (num >= max)
throw new OverflowIntQueueException(); // 큐가 가득 참
que[rear++] = x;
num++;
if (rear == max)
rear = 0;
return x;
}
디큐 메서드 deque
// 큐에서 데이터를 디큐
public int deque() throws EmptyIntQueueException {
if (num <= 0)
throw new EmptyIntQueueException();
int x = que[front++];
num--;
if (front == max)
front = 0;
return x;
}
피크 메서드 peek
// 큐에서 데이터를 peek(front 데이터를 들여다 봄)
public int peek() throws EmptyIntQueueException {
if (num <= 0)
throw new EmptyIntQueueException();
return que[front];
}
검색 메서드 indexOf
// 큐에서 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;
}
◽ 요소 값은 덮어 씌우면 되기 때문에 요소 값들을 삭제할 필요는 없다.
최대 용량을 확인하는 메서드 capacity
// 큐의 용량을 반환
public int capacity() {
return max;
}
데이터 수를 확인하는 메서드 size
// 큐에 쌓여 있는 데이터 수를 반환
public int size() {
return num;
}
큐가 비어 있는지 판단하는 메서드 isEmpty
public boolean isEmpty() {
return num <= 0;
}
큐가 가득 찼는지 판단하는 메서드 isFull
public boolean isFull() {
return num >= max;
}
모든 데이터를 출력하는 메서드 dump
public void dump() {
if (num <= 0)
System.out.println("큐가 비어 있습니다.");
else {
for (int i = 0; i < num; i++)
System.out.println(que[(i + front) % max] + " ");
System.out.println();
}
}
'Data Structure' 카테고리의 다른 글
배열로 집합 만들기 (0) | 2021.12.13 |
---|---|
재귀 알고리즘 (0) | 2021.11.30 |
스택 (0) | 2021.11.28 |
검색 (0) | 2021.11.24 |
배열 (0) | 2021.11.22 |