IntQueue 클래스
2025. 4. 20. 18:05ㆍ카테고리 없음
코드 설명
/******************************************************************************
* IntQueue 클래스는 정수를 저장하는 순서 큐(Queue)를 배열을 이용하여 구현한 클래스입니다.
******************************************************************************/
public class IntQueue implements Cloneable {
// IntQueue 클래스의 불변 조건 (Invariant):
// 1. 큐에 있는 항목의 개수는 manyItems에 저장됩니다.
// 2. 비어 있지 않은 큐의 경우, 항목들은 data[front]부터 data[rear]까지 순환 배열 형태로 저장됩니다.
// 3. 큐가 비어있는 경우, manyItems는 0이며, data는 배열을 참조하지만 front와 rear는 중요하지 않습니다.
private int[] data;
private int manyItems;
private int front;
private int rear;
/**
* 초기 용량이 10인 빈 큐를 생성합니다.
* @param - 없음
* <dt><b>후조건:</b><dd>
* 이 큐는 비어 있으며, 초기 용량은 10입니다.
* @exception OutOfMemoryError
* 메모리가 부족할 경우 발생:
* <CODE>new int[10]</CODE>.
**/
public IntQueue() {
final int INITIAL_CAPACITY = 10;
manyItems = 0;
data = new int[INITIAL_CAPACITY];
// 빈 큐에서는 front와 rear는 중요하지 않습니다.
}
/**
* 지정한 초기 용량을 가진 빈 큐를 생성합니다.
* @param initialCapacity
* 큐의 초기 용량
* <dt><b>전제조건:</b><dd>
* initialCapacity는 음수가 아니어야 합니다.
* <dt><b>후조건:</b><dd>
* 이 큐는 비어 있으며, 주어진 초기 용량을 가집니다.
* @exception IllegalArgumentException
* initialCapacity가 음수인 경우 발생.
* @exception OutOfMemoryError
* 메모리가 부족한 경우 발생:
* <CODE>new int[initialCapacity]</CODE>.
**/
public IntQueue(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException("초기 용량이 음수입니다: " + initialCapacity);
manyItems = 0;
data = new int[initialCapacity];
}
/**
* 이 큐의 복사본을 생성합니다.
* @param - 없음
* @return
* 복사된 큐 객체. 원본과 복사본은 이후의 변경이 서로 영향을 주지 않습니다.
* @exception OutOfMemoryError
* 복사를 위한 메모리가 부족한 경우 발생.
**/
public Object clone() {
IntQueue answer;
try {
answer = (IntQueue) super.clone();
} catch (CloneNotSupportedException e) {
// 이 예외는 발생하지 않아야 하지만, 발생할 경우 clone이 불가능한 설계 오류일 수 있습니다.
throw new RuntimeException("이 클래스는 Cloneable을 구현하지 않았습니다.");
}
answer.data = (int[]) data.clone();
return answer;
}
/**
* 큐의 용량을 변경하여 최소한 minimumCapacity를 보장합니다.
* @param minimumCapacity
* 큐의 새로운 최소 용량
* <dt><b>후조건:</b><dd>
* 큐의 용량이 minimumCapacity 이상으로 설정됩니다.
* @exception OutOfMemoryError
* 메모리가 부족하여 용량 증가가 불가능한 경우 발생.
**/
public void ensureCapacity(int minimumCapacity) {
int[] biggerArray;
int n1, n2;
if (data.length >= minimumCapacity)
return;
else if (manyItems == 0)
data = new int[minimumCapacity];
else if (front <= rear) {
biggerArray = new int[minimumCapacity];
System.arraycopy(data, front, biggerArray, front, manyItems);
data = biggerArray;
} else {
biggerArray = new int[minimumCapacity];
n1 = data.length - front;
n2 = rear + 1;
System.arraycopy(data, front, biggerArray, 0, n1);
System.arraycopy(data, 0, biggerArray, n1, n2);
front = 0;
rear = manyItems - 1;
data = biggerArray;
}
}
/**
* 현재 큐의 용량을 반환합니다.
* @return
* 큐의 현재 용량
**/
public int getCapacity() {
return data.length;
}
/**
* 큐의 앞쪽 항목을 제거하고 반환합니다.
* @return
* 큐의 앞쪽 항목 값
* @exception NoSuchElementException
* 큐가 비어 있을 경우 발생.
**/
public int getFront() {
int answer;
if (manyItems == 0)
throw new NoSuchElementException("큐 언더플로우");
answer = data[front];
front = nextIndex(front);
manyItems--;
return answer;
}
/**
* 새로운 항목을 큐에 추가합니다.
* 필요 시 자동으로 용량이 늘어납니다.
* @param item
* 큐에 추가할 항목
* <dt><b>후조건:</b><dd>
* 항목이 큐에 추가됩니다.
* @exception OutOfMemoryError
* 용량을 늘릴 메모리가 부족할 경우 발생.
**/
public void insert(int item) {
if (manyItems == data.length) {
ensureCapacity(manyItems * 2 + 1);
}
if (manyItems == 0) {
front = 0;
rear = 0;
} else
rear = nextIndex(rear);
data[rear] = item;
manyItems++;
}
/**
* 큐가 비어 있는지 확인합니다.
* @return
* 큐가 비어 있으면 true, 그렇지 않으면 false
**/
public boolean isEmpty() {
return (manyItems == 0);
}
private int nextIndex(int i) {
// 전제조건: 0 <= i < data.length
// 후조건: i+1이 data.length이면 0을 반환, 아니면 i+1을 반환
if (++i == data.length)
return 0;
else
return i;
}
/**
* 큐에 들어 있는 항목 수를 반환합니다.
* @return
* 큐에 저장된 항목 수
**/
public int size() {
return manyItems;
}
/**
* 큐의 용량을 실제 항목 수만큼 줄입니다.
* @exception OutOfMemoryError
* 메모리 부족으로 인해 용량 조정이 불가능한 경우 발생.
**/
public void trimToSize() {
int[] trimmedArray;
int n1, n2;
if (data.length == manyItems)
return;
else if (manyItems == 0)
data = new int[0];
else if (front <= rear) {
trimmedArray = new int[manyItems];
System.arraycopy(data, front, trimmedArray, front, manyItems);
data = trimmedArray;
} else {
trimmedArray = new int[manyItems];
n1 = data.length - front;
n2 = rear + 1;
System.arraycopy(data, front, trimmedArray, 0, n1);
System.arraycopy(data, 0, trimmedArray, n1, n2);
front = 0;
rear = manyItems - 1;
data = trimmedArray;
}
}
}인스턴스 멤버
private int[] data;
private int manyItems;
private int front;
private int rear;- data에는 데이터를 저장해 준다.
- manyItems에는 데이터의 개수를 저장해 준다.
- front부터 rear까지 순환 배열의 구조로 데이터를 저장해 둔다.
생성자
public IntQueue() {
final int INITIAL_CAPACITY = 10;
manyItems = 0;
data = new int[INITIAL_CAPACITY];
}- 기본적으로 배열의 크기를 10으로 지정해 둔다.
public IntQueue(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException("초기 용량이 음수입니다: " + initialCapacity);
manyItems = 0;
data = new int[initialCapacity];
}- initialCapacity를 기본적으로 배열의 크기를 지정해 둔다.
- 0보다 작은 경우에만 예외를 발생시켜 준다.
메서드
public Object clone() {
IntQueue answer;
try {
answer = (IntQueue) super.clone();
} catch (CloneNotSupportedException e) {
// 이 예외는 발생하지 않아야 하지만, 발생할 경우 clone이 불가능한 설계 오류일 수 있습니다.
throw new RuntimeException("이 클래스는 Cloneable을 구현하지 않았습니다.");
}
answer.data = (int[]) data.clone();
return answer;
}- (IntQueue) super.clone()으로 얕은 복사를 해주고, (int []) data.clone()으로 answer.data에 깊은 복사를 해준다.
public void ensureCapacity(int minimumCapacity) {
int[] biggerArray;
int n1, n2;
if (data.length >= minimumCapacity)
return;
else if (manyItems == 0)
data = new int[minimumCapacity];
else if (front <= rear) {
biggerArray = new int[minimumCapacity];
System.arraycopy(data, front, biggerArray, front, manyItems);
data = biggerArray;
} else {
biggerArray = new int[minimumCapacity];
n1 = data.length - front;
n2 = rear + 1;
System.arraycopy(data, front, biggerArray, 0, n1);
System.arraycopy(data, 0, biggerArray, n1, n2);
front = 0;
rear = manyItems - 1;
data = biggerArray;
}
}- 기본적으로 minimumCapacity보다 데이터의 용량이 더 크면 그냥 리턴해준다.
- 그리고 데이터의 개수가 0인 경우에는 data의 용량을 minimumCapacity 해주고 리턴해준다.
- 만약 front <=rear인 경우에는 front부터 manyItems만큼의 데이터를 복사해 주고 리턴해주면 된다.
- 반대로 rear <front인 경우에는 두 번을 나누어서 데이터를 복사해주어야 한다.
1)
-front~끝까지 데이터를 복사해주어야 함!
-즉, front부터 시작해서 (data.length-front) 만큼의 데이터를 biggerArray의 0~(data.length-front)까지의 위치에 저장해주어야 한다.
2)
-이번에는 처음부터 0번부터 시작하여서 (rear+1) 개만큼의 데이터를 biggerArray에 (data.length-front)부터 복사해주어야 한다.
3)
이후에는 front를 0, rear를 manyItems-1로 지정해 준다.
public int getCapacity() {
return data.length;
}- 배열의 용량을 리턴해준다.
private int nextIndex(int i) {
if (++i == data.length)
return 0;
else
return i;
}- 다음에 있는 데이터의 인덱스를 가리키는 메서드이다.
- 만약 다음 인덱스가 데이터의 용량과 동일한 경우 0, 즉 맨 처음 인덱스를 리턴해줘야 한다.
public int getFront() {
int answer;
if (manyItems == 0)
throw new NoSuchElementException("큐 언더플로우");
answer = data[front];
front = nextIndex(front);
manyItems--;
return answer;
}- 만약 데이터의 개수(manyItems)가 0인 경우에는 예외 처리를 발생시켜 준다.
- 그리고 front를 1 증가시켜서 데이터를 줄여주고, manyItems 또한 1 감소시켜 준다.
public void insert(int item) {
if (manyItems == data.length) {
ensureCapacity(manyItems * 2 + 1);
}
if (manyItems == 0) {
front = 0;
rear = 0;
} else
rear = nextIndex(rear);
data[rear] = item;
manyItems++;
}- 데이터의 용량이 꽉 찬 경우에는 두 배 정도 용량을 늘려준다.
- 만약 데이터의 개수가 0인 경우에는 front=rear=0으로 지정해 준다.
- 아니라면 rear를 nextIndex 메서드를 활용하여서 다음 인덱스를 구해준다.
- 그러고 나서 rear에 해당하는 위치에 데이터를 저장해 주고 데이터 개수(manyItems)를 1 늘려준다.
public boolean isEmpty() {
return (manyItems == 0);
}- 데이터 개수가 0이면 true 아니면 false를 리턴해준다.
public int size() {
return manyItems;
}- 데이터의 개수를 리턴해준다.
public void trimToSize() {
int[] trimmedArray;
int n1, n2;
if (data.length == manyItems)
return;
else if (manyItems == 0)
data = new int[0];
else if (front <= rear) {
trimmedArray = new int[manyItems];
System.arraycopy(data, front, trimmedArray, front, manyItems);
data = trimmedArray;
} else {
trimmedArray = new int[manyItems];
n1 = data.length - front;
n2 = rear + 1;
System.arraycopy(data, front, trimmedArray, 0, n1);
System.arraycopy(data, 0, trimmedArray, n1, n2);
front = 0;
rear = manyItems - 1;
data = trimmedArray;
}
}- 만약 data의 용량이 데이터의 개수와 동일하다면 그냥 리턴해준다.
- 그리고 데이터의 개수가 0이면 data의 용량을 0으로 지정해 주고 리턴한다.
- 만약 front <=rear인 경우에는 front부터 rear까지를 복사해 준다.
- 반대로 rear <front이면 위에서 ensureCapacity 해준 것과 비슷하게 저장해 준다.