큐는 기본 원칙이 '선입선출(FIFO : First in First out)' 이다.
선입선출.. 한자로 先入先出 이다. 말 그대로 '먼저 들어온 것이 먼저 나오는 방식'이다.
그림으로 보면 이렇다.
우리가 흔히 줄을 서서 대기하는 모습을 상상하면 된다.
문제는 배열을 이용하여 구현 할 경우 문제가 있다. 예로들어 다음과 같이 배열에 원소들을 추가해놓았다고 가정해보자.
그리고 큐는 선입선출이므로 큐 원소를 삭제(poll)할 경우 가장 앞에있는 원소. 즉, index 0 의 원소가 삭제 된다.
그리고 위에서 다시 원소를 추가(offer)하면 맨 뒤의 원소 바로 뒷 자리. 즉 index 3 의 자리에 원소가 추가 된다.
이런식으로 큐의 삽입 삭제가 반복되면 결국에 원소들이 뒤로 치우치게 되는 경우가 발생한다.
이렇게 선형적으로 접근하게 되면 쏠림현상이 발생하는데, 그렇다고 매 번 삭제 연산 때마다 삭제된 원소 뒤의 모든 원소들을 한 자리씩 앞으로 땡겨오는 것은 매우 비효율적이고, 그렇다고 배열 크기를 늘리자니 배열이 꽉찬 상태인 것도 아니라 빈 공간을 낭비하게 된다.
이를 해결하기 위한 아주 간단한 방법은 앞의 빈 자리에 다시 채워넣는 것이다. 이해가 어렵다면 저 배열을 '원형'이라고 생각하자.그림으로 보면 아래와 같다. 이 때 가장 마지막 원소의 위치를 가리키는 변수 'front(앞)' 와 'rear(뒤)'가 필요하다.
만약 원소를 추가한다면? 0번째 인덱스에 원소를 추가하는 것이다.
그리고 반대로 원소를 삭제한다면? front+1 번째, 즉 index 4에 위치한 원소가 삭제되는 것이다.
쉽게 생각하면 rear을 따라 원소가 추가되고, front를 따라 원소가 삭제된다고 보면 된다. 위와 같은 방식으로 원소들을 채워나가면 효율적으로 배열을 관리할 수 있다.
만약에 '더이상 빈 자리가 없을 경우'에만 배열의 크기를 늘려주면 된다.
여기서 여러분들이 한 가지 의아할 점이 있을 것이다. 왜 front 변수 다음부터 원소가 추가되는 것이죠?
이는 연속하여 삭제하게 될 경우 다음과 같은 이유 때문에 일반적으로 front 위치는 비워두고 다음 index부터 시작한다.
[front 위치의 공간을 비우지 않을 경우]
이렇게 front와 rear가 엇갈려 버리게 되는데, 문제는 아래와 같다.
위 두 배열 모두 rear와 front가 각각 가리키는 위치는 같지만, 비어있는지 가득차있는지는 저 두 변수만으로는 알 수 없다는 것이다. 그럼 반대로 front 위치는 비우게 되면 어떻게 될까?
[front 위치의 공간을 비우는 경우]
이렇게 한 자리를 비움으로 front와 rear가 같은 경우 큐가 비어있음을 확인 할 수 있게 된다.
한마디로 front == rear 라면 큐는 비어있는 상태이며, 비어있다면 다시 두 변수 모두 0으로 초기화 해주면 더욱 깔끔해진다.
이러한 구조를 보통 Circular Queue, 우리나라 말로는 '원형 큐' 또는 '환형 큐' 라고도 한다.
그럼 본격적으로 큐(Queue)을 구현하기 전에 알아가야할 것이 있다.
모든 자료구조는 '동적 할당'을 전제로 한다. 가끔 ArrayList, Stack 같이 Object[] 배열을 사용하는 자료구조를 구현 할 때, 자료구조의 용적(Capacity)이 꽉 차면 리스트의 크기를 늘리지 않고 그냥 꽉 찼다고 더이상 원소를 안받도록 구현한 경우가 많은데 이는 자료구조를 구현하는 의미가 없다.
동적 할당을 안하고 사이즈를 정해놓고 구현한다면 메인함수에서 정적배열을 선언하는 것과 차이가 없다.
데이터의 개수를 알 수 없는데 배열을 쓰고 싶을 때 여러분은 어떤 방법을 선택하는가? ArrayList, LinkedList 등의 자료구조를 선택할 것이다. 왜냐면 사이즈를 정하지 않고 동적으로 활용할 수 있기 때문이다. 그렇기 때문에 당장은 어렵더라도 반드시 동적 할당이 가능한 형태로 구현하도록 노력을 하는 것이 좋다.
- Array Queue 구현
[Queue 클래스 및 생성자 구성하기]
이 번에 구현 할 큐는 '배열'을 이용하므로, ArrayQueue 라는 이름으로 생성한다. 그리고 앞선 Queue Interface 포스팅에서 작성했던 Queue 인터페이스를 implements 해준다. (필자의 경우 인터페이스는 Interface_form 이라는 패키지에 생성해두었다.)
implements 를 하면 class 옆에 경고표시가 뜰 텐데 인터페이스에 있는 메소드들을 구현하라는 것이다. 어차피 모두 구현해나갈 것이기 때문에 일단은 무시한다.
[ArrayQueue.java]
import Interface_form.Queue;
public class ArrayQueue<E> implements Queue<E> {
private static final int DEFAULT_CAPACITY = 64; // 최소(기본) 용적 크기
private Object[] array; // 요소를 담을 배열
private int size; // 요소 개수
private int front; // 시작 인덱스를 가리키는 변수(빈 공간임을 유의)
private int rear; // 마지막 요소의 인덱스를 가리키는 변수
// 생성자1 (초기 용적 할당을 안할 경우)
public ArrayQueue() {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.front = 0;
this.rear = 0;
}
// 생성자2 (초기 용적 할당을 할 경우)
public ArrayQueue(int capacity) {
this.array = new Object[capacity];
this.size = 0;
this.front = 0;
this.rear = 0;
}
}변수부터 먼저 차례대로 설명해주도록 하겠다.
DEFAULT_CAPACITY : 배열이 생성 될 때의 최초 할당 크기(용적)이자 최소 할당 용적 변수로 기본값은 64으로 설정해두었다. (capacity가 용적이라는 의미다)
array : 요소들을 담을 배열
size : 배열에 담긴 요소(원소)의 개수 변수 (용적 크기가 아니다. 절대 헷갈리지 말자)
front : 시작 위치(index)를 가리키는 변수 (빈 공간이다.)
rear : 마지막 요소의 위치(index)를 가리키는 변수
그리고 DEFAULT_CAPACITY 변수는 상수로 쓸 것이기 때문에 static final 키워드를 붙인다.
그리고 보면 생성자가 2개를 두었다.
생성자 1의 경우 사용자가 공간 할당을 안하고 객체만 생성할 때, 즉 다음과 같은 상태일 때이다.
ArrayQueue<Integer> q = new ArrayQueue<>();반면에 사용자가 데이터의 개수를 예측할 수 있어서 미리 공간 할당을 해놓고 싶을 경우, 즉 다음과 같이 생성할 경우
ArrayQueue<Integer> q = new ArrayQueue<>(100);array의 공간 할당을 입력 된 수 만큼 (예제에서는 array = new Object[100]) 배열을 만든다. 그리고 마찬가지로 size, front, rear 들을 0으로 초기화 시켜놓는다.
(size는 요소(원소)의 개수를 의미하는 것이다. 공간을 할당해놓는 것하고는 다른 개념이다.)
[동적할당을 위한 resize 메소드 구현]
앞서 필자가 말했던 것 처럼 우리는 들어오는 데이터에 개수에 따라 '최적화'된 용적을 갖을 필요가 있다. 만약 데이터는 적은데 용적이 크면 메모리가 낭비되고, 반대로 용적은 적은데 데이터가 많으면 넘치는 데이터들은 보관할 수 없게 되는 상황을 마주칠 수 있다.
그렇기 때문에 size(요소의 개수)가 용적(capacity)에 얼마만큼 차있는지를 확인하고, 적절한 크기에 맞게 배열의 용적을 변경해야 한다. 또한 용적은 외부에서 마음대로 접근하면 데이터의 손상을 야기할 수 있기 때문에 private로 접근을 제한해주도록 하자.
용적이 변경되는 경우는 크게 용적을 증가시켜야 하는 경우와 용적을 줄여야 하는 경우. 이 두가지로 나뉜다. 그러나 따로 용적을 증가해야 하는 경우와 줄여야 하는 경우를 굳이 나눌 필요 없다. 밑에서 그림을 보면 알겠지만, 먼저 코드부터 보고 가자.
private void resize(int newCapacity) {
int arrayCapacity = array.length; // 현재 용적 크기
Object[] newArray = new Object[newCapacity]; // 용적을 변경한 배열
/*
* i = new array index
* j = original array
* index 요소 개수(size)만큼 새 배열에 값 복사
*/
for (int i = 1, j = front + 1; i <= size; i++, j++) {
newArray[i] = array[j % arrayCapacity];
}
this.array = null;
this.array = newArray; // 새 배열을 기존 array의 배열로 덮어씌움
front = 0;
rear = size;
}용적을 증가하는 경우 : ((rear + 1) % arrayCapacity == front)
용적이 가득 찰 경우다. 이 의미는 rear의 다음 인덱스(rear +1) 이 front 랑 같다는 말과 동일하다. 다만 (rear+1)에 % arrayCapacity 즉, 기존 배열의 길이를 나누는 이유는 front 가 rear보다 작을경우를 고려해야 하기 때문이다.
예로들어 rear가 7이고, front가 0이라면 7+1 = 8이므로, 0과 같지 않다. 이러한 이유로 길이(예시에서는 8)로 나눠준 나머지 (7+1)%8 = 0 을 해야 정확한 조건 때 용적을 증가 시킬 수 있다.
용적을 줄여야 하는 경우 : (size < (arrayCapacity / 4))
데이터가 1/4 미만으로 떨어질 경우에는 필요없는 공간이 너무 많아지게 되므로 절반정도로만 줄인다.
코드를 보면 알겠지만 새로운 용적의 배열에 값을 복사하는 과정 자체는 똑같기 때문에 따로 두 경우의 조건문은 달지 않고 파라미터(newCapacity)로 받은 새 용적을 이용하여 용적의 사이즈를 변경할 것이다.
[offer 메소드 구현]
이제 본격적으로 Queue에 데이터를 추가할 수 있도록 해보자.
Queue의 offer는 항상 후방(맨 뒤)에 데이터를 추가해야하므로 한 종류밖에 없다. 리스트로 치면 add(E value)와 같은 역할이다. 다만 고려해야 할 부분이라면 배열의 마지막 인덱스에 도달했을 경우 또는 배열이 꽉 차있을 경우다.
- 가장 마지막 부분에 추가 - offer(E item)
그림으로 과정을 보면 이렇다.
이를 토대로 구현해보자.
1. 기본 삽입 : offer(E item)
구현 자체는 그리 어렵지 않다. offer() 메소드를 구현하자면 이렇다.
@Override
public boolean offer(E item) {
// 용적이 가득 찼을 경우
if((rear + 1) % array.length == front) {
resize(array.length * 2); // 용적을 두 배 늘려준다.
}
rear = (rear + 1) % array.length; // rear을 rear의 다음 위치로 갱신
array[rear] = item;
size++; // 사이즈 1 증가
return true;
}@Override
public E poll() {
if(size == 0) { // 삭제할 요소가 없을 경우 null 반환
return null;
}
front = (front + 1) % array.length; // front 를 한 칸 옮긴다.
@SuppressWarnings("unchecked")
E item = (E) array[front]; // 반환할 데이터 임시 저장
array[front] = null; // 해당 front의 데이터 삭제
size--; // 사이즈 감소
// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다.
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
return item;
}또한 필자가 '동적할당'을 강조했듯 용적이 가득찼다면 array의 용적을 늘려주어야 한다. 그렇기 때문에 앞서 구현한 resize() 메소드를 호출하여 용적을 두 배 늘려준 뒤 데이터를 추가해주도록 하자.
[offer 메소드 묶어보기]
더보기
[poll 메소드 구현]
poll 메소드 또한 그리 어렵지 않게 만들 수 있다. 리스트에서의 remove()와 같은 역할로 front + 1 위치에 있는 요소를 삭제하면 된다.
다만 중요한 점은 '삭제할 요소가 없는 경우' 다.
자바의 Queue에 관한 API 문서를 보면 알겠지만, add() - offer(), remove() - poll(), element() - peek() 이 각각 대응되는데, 자바에서 둘 다 제공하는 이유는 다음과 같다.
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html
참고 문서 링크 : docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html
(add()의 경우 만약 용적이 제한되어있는데 용적보다 더 많은 요소를 추가 할 경우 예외를 던지는데, 지금 구현하는 것에서는 최대 제한을 걸지 않아 넘어갔다.)
삭제의 경우 remove() 같은 경우 삭제 할 요소가 없으면 NoSuchElementException() 예외를 던진다. 반대로 poll()의 경우는 삭제 할 요소가 없다면 null을 반환한다는 차이점이 있다.
일단 poll() 메소드를 구현하고 이를 remove() 메소드에 응용하여 적용해보도록 하자.
poll의 구조 또한 매우 쉬우니 그림을 다시 한 번 보고 구현해보도록 하자.
1. poll() 메소드
@Override
public E poll() {
if(size == 0) { // 삭제할 요소가 없을 경우 null 반환
return null;
}
front = (front + 1) % array.length; // front 를 한 칸 옮긴다.
@SuppressWarnings("unchecked")
E item = (E) array[front]; // 반환할 데이터 임시 저장
array[front] = null; // 해당 front의 데이터 삭제
size--; // 사이즈 감소
// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다.
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
return item;
}여기서 @SuppressWarnings("unchecked") 에 대해 잠깐 언급하고 가겠다.
@SuppressWarnings("unchecked")을 붙이지 않으면 type safe(타입 안정성)에 대해 경고를 보낸다. 반환되는 것을 보면 E 타입으로 캐스팅을 하고 있고 그 대상이 되는 것은 Object[] 배열의 Object 데이터다. 즉, Object -> E 타입으로 변환을 하는 것인데 이 과정에서 변환할 수 없는 타입을 가능성이 있다는 경고로 메소드 옆에 경고표시가 뜨는데, 우리가 push하여 받아들이는 데이터 타입은 유일하게 E 타입만 존재한다.
그렇기 때문에 형 안정성이 보장된다. 한마디로 ClassCastException이 뜨지 않으니 이 경고들을 무시하겠다는 것이 @SuppressWarnings("unchecked") 이다. 물론 절대 남발하면 안되고, 형 변환시 예외 가능성이 없을 확실한 경우에 최소한의 범위에서 써주는 것이 좋다. 그렇지 않으면 중요한 경고 메세지를 놓칠 수도 있기 때문이다.
2. remove() 메소드
public E remove() {
E item = poll();
if(item == null) {
throw new NoSuchElementException();
}
return item;
}@Override
public E poll() {
if(size == 0) { // 삭제할 요소가 없을 경우 null 반환
return null;
}
front = (front + 1) % array.length; // front 를 한 칸 옮긴다.
@SuppressWarnings("unchecked")
E item = (E) array[front]; // 반환할 데이터 임시 저장
array[front] = null; // 해당 front의 데이터 삭제
size--; // 사이즈 감소
// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다.
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
return item;
}@Override
public E poll() {
if(size == 0) { // 삭제할 요소가 없을 경우 null 반환
return null;
}
front = (front + 1) % array.length; // front 를 한 칸 옮긴다.
@SuppressWarnings("unchecked")
E item = (E) array[front]; // 반환할 데이터 임시 저장
array[front] = null; // 해당 front의 데이터 삭제
size--; // 사이즈 감소
// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다.
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
return item;remove() 메소드는 poll() 을 호출하여 null 일 경우에만 예외를 던지면 되기 때문에 별다르게 설명 할 것은 없다.
[poll / remove 메소드 묶어보기]
[peek() 메소드 구현]
가장 앞에 있는 데이터((front + 1)%array.length)를 삭제하지 않고 확인만 하고싶을 때가 있다. 그럴 때 쓰는 것이 peek() 메소드다. 한마디로 poll() 메소드에서 삭제과정만 없는 것이 peek() 이다.
그래서 삭제과정만 빼고 그대로 반환하면 되기 때문에 설명 할 것이 없다.
그리고 참고로 큐에 데이터가 없는 경우는 null을 던진다. 반대로 이와 유사한 element() 메소드는 큐에 요소가 없을 경우 remove() 메소드와 마찬가지로 NoSuchElementException 예외를 던진다. 위 처럼 두 가지 모두 구현해보도록 해보자.
1. peek() 메소드
@Override
public E peek() {
// 요소가 없을 경우 null 반환
if(size == 0) {
return null;
}
@SuppressWarnings("unchecked")
E item = (E) array[(front + 1) % array.length];
return item;
}마찬가지로 E 타입 원소를 반환해야하는지라 Object 타입을 E 타입으로 캐스팅을 해주면서 경고창이 뜬다. 하지만 poll()메소드에서 설명했듯이 마지막 원소 또한 E Type 외에 들어오는 것이 없기 때문에 형 안정성이 확보되므로 경고표시를 무시하기 위해 @SuppressWarnings("unchecked")을 붙인다.
2. element() 메소드
public E element() {
E item = peek();
if(item == null) {
throw new NoSuchElementException();
}
return item;
}public int size() {
return size;
remove()랑 과정이 같다.
[peek / element 메소드 묶어보기]
[size, isEmpty, contains, clear 메소드 구현]
이제 나머지는 그나마 자주 사용되는, 거의 필수적인 메소드를 구현해보고자 한다.
1. size() 메소드
size는 매우 간단하게 현재 큐에 있는 요소의 개수를 알려준다.
public int size() {
return size;
}public boolean isEmpty() {
return size == 0;
}2. isEmpty() 메소드
isEmpty() 메소드는 현재 큐가 비어있는지를 확인 할 때 쓰인다. 요소의 개수가 0개라면 비어있다는 뜻이므로, 비어있다면 true를, 비어있지 않다면 false를 반환한다.
public boolean isEmpty() { return size == 0;}3. contains() 메소드
contains() 는 현재 찾고자하는 요소가 큐에 들어가있는지를 알려주는 메소드다.
public boolean contains(Object value) {
int start = (front + 1) % array.length;
/**
* i : 요소 개수만큼만 반복한다.
* idx : 원소 위치로, 매 회 (idx + 1) % array.length; 의 위치로 갱신
*/
for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
if(array[idx].equals(value)) {
return true;
}
}
return false;
}이 때 0번째 인덱스부터 용적크기(array.length)까지 모두 검사할 수도 있겠지만, 기본적으로 용적 크기에 비해 요소의 개수가 훨씬 적은 경우가 많다.
굳이 모든 공간을 찾기보단, 요소의 개수만큼만 정확히 범위를 짚어서 반복해주는 것이 더욱 효율적이지 않겠는가?
만약 해당 범위 외의 공간에 요소가 있으면 어떡해요? 라고 한다면, 그 것은 구현이 잘못된 것이기에.. 한 마디로 잘못된 참조가 있다는 것이고 굳이 그 요소를 검사할 필요가 없다.
4. clear() 메소드
clear() 메소드는 단어 그대로 Queue의 모든 요소를 비워버린다.
public void clear() {
for(int i = 0; i < array.length; i++) {
array[i] = null;
}
front = rear = size = 0;
}이 때는 혹시 모를 경우까지 대비해 모든 공간을 명시적으로 null 처리를 해주는 것이 좋다.
그리고 빈 공간은 초기 상태와 마찬가지로 front 와 rear와 size 모두 0으로 초기화 해준다.
이렇게 size, isEmpty, contains, clear 메소드들을 만들어보았다. 해당 메소드들을 묶어서 한 눈에 보고싶다면 아래 더보기를 누르면 된다.
[ size, isEmpty, contains, clear 메소드 묶어보기]
<부가 목록>
[toArray, clone, sort 메소드 구현]
이 부분은 굳이 구현하는데 중요한 부분은 아니라 넘어가도 된다. 다만 조금 더 많은 기능을 원할 경우 추가해주면 좋은 메소드들이긴 하다. toArray는 사용자가 main 함수에서 특정 배열로 반환받고싶다거나 복사하고 싶을 때 Queue에 저장된 데이터들을 배열로 반환해주는 역할을 하기 위해 만들었다. clone은 기존에 있던 객체를 파괴하지 않고 요소들이 동일한 객체를 새로 하나 만드는 것이다.
마지막으로 sort()메소드는 말 그대로 정렬해주는 메소드다.
1. toArray() 메소드
toArray()는 크게 두 가지가 있다.
하나는 아무런 인자 없이 현재 있는 큐의 요소들을 객체배열(Object[]) 로 반환해주는 Object[] toArray() 메소드가 있고,
다른 하나는 큐를 이미 생성 된 다른 배열에 복사해주고자 할 때 쓰는 T[] toArray(T[] a) 메소드가 있다.
즉 차이는 이런 것이다.
ArrayQueue<Integer> arrayqueue = new ArrayQueue<>();
// get ArrayQueue to array (using toArray())
Object[] q1 = arrayqueue.toArray();
// get ArrayQueue to array (using toArray(T[] a)
Integer[] q2 = new Integer[10];
q2 = arrayqueue.toArray(q2)1번의 장점이라면 큐에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환된다는 점이다.
2번의 장점이라면 객체 클래스로 상속관계에 있는 타입이거나 Wrapper(Integer -> int) 같이 데이터 타입을 유연하게 캐스팅할 여지가 있다는 것이다. 또한 큐의 원소 5개가 있고, q2 배열에 10개의 원소가 있다면 q2에 0~4 index에 원소가 복사되고, 그 외의 원소는 기존 q2배열에 초기화 되어있던 원소가 그대로 남는다.
다만 ArrayQueue 에서는 앞(front)이 뒤(rear)보다 항상 앞에 있는 것이 아니라 중간이 비어버리는 경우가 발생할 수 있기 때문에 이러한 것을 방지하기 위해 정확한 시작 위치와 끝나는 위치 범위를 잘 설정해야 한다.
복사되는 원소의 범위는 (front + 1) % array.length 부터 rear까지다.
두 메소드 모두 구현해보자면 다음과 같다.
public Object[] toArray() {
return toArray(new Object[size]);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
final T[] res;
// 들어오는 배열의 길이가 큐의 요소 개수보다 작은경우
if(a.length < size) {
/*
* front가 rear보다 앞에 있을 경우 (또는 요소가 없을 경우 f==r)
* ______________________
* | | | | | | | |
* ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
* f r
*/
if(front <= rear) {
return (T[]) Arrays.copyOfRange(array, front + 1, rear + 1, a.getClass());
}
/*
* front가 rear보다 뒤에 있을 경우
* ______________________
* | | | | | | | |
* ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
* r f
*/
res = (T[]) Arrays.copyOfRange(array, 0, size, a.getClass());
int rearlength = array.length - 1 - front; // 뒷 부분의 요소 개수
// 뒷 부분 복사
if(rearlength > 0) {
System.arraycopy(array, front + 1, res, 0, rearlength);
}
// 앞 부분 복사
System.arraycopy(array, 0, res, rearlength, rear + 1);
return res;
}
/*
* front가 rear보다 앞에 있을 경우 (또는 요소가 없을 경우 f==r)
* ______________________
* | | | | | | | |
* ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
* f r
*/
if(front <= rear) {
System.arraycopy(array, front + 1, a, 0, size);
}
/*
* front가 rear보다 뒤에 있을 경우
* ______________________
* | | | | | | | |
* ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
* r f
*/
else {
int rearlength = array.length - 1 - front; // 뒷 부분의 요소 개수
// 뒷 부분 복사
if(rearlength > 0) {
System.arraycopy(array, front + 1, a, 0, rearlength);
}
// 앞 부분 복사
System.arraycopy(array, 0, a, rearlength, rear + 1);
}
return a;
}먼저 첫 번째 toArray() 메소드의 경우 두 번째 toArray(T[] a) 로 보내도록 하겠다. (동작 구현이 겹치기 때문이다.)
두 번째 T[] toArray(T[] a) 메소드를 보자.
이 부분은 제네릭 메소드로, 우리가 만들었던 ArrayQueue의 E타입하고는 다른 제네릭이다. 예로들어 E Type이 Integer라고 가정하고, T타입은 Object 라고 해보자.
Object는 Integer보다 상위 타입으로, Object 안에 Integer 타입의 데이터를 담을 수도 있다. 이 외에도 사용자가 만든 부모, 자식 클래스 같이 상속관계에 있는 클래스들에서 하위 타입이 상위 타입으로 데이터를 받고 싶을 때 쓸 수 있도록 하기 위함이다.
즉, 상위타입으로 들어오는 객체에 대해서도 데이터를 담을 수 있도록 별도의 제네릭메소드를 구성하는 것이다.
그리고 중요한 점이 있다. 기본적으로 toArray(T[] a) 에서 a로 들어오는 파라미터 배열의 길이가 큐에 들어있는 요소 개수보다 작은 경우 요소 개수를 모두 복사할 수 있도록 고려해야한다는 점에 추가하여 원형 큐로 구현하다보니 front와 rear의 위치에 따라 복사 과정이 다르다.
그냥 Arrays.copyOf() 메소드를 쓸 수 없다는 것이다.
만약 파라미터로 들어오는 배열의 경우 Arrays.copyOfRange() 로 지정된 범위 만큼 복사하여 크기를 맞춰주어야 하며, front와 rear의 위치에 따라 front가 rear보다 앞에 있는 경우 front + 1 ~ rear 까지 복사하면 되고, 만약 rear가 front 가 앞설 경우 front + 1 부터 시작하는 뒷 부분을 먼저 저장 한 뒤, 0번째부터 rear까지 뒤이어서 복사해주어야 한다.
조금 복잡해보일 수는 있으나, 최대한 이해할 수 있도록 주석을 달아놓았으니 참고해보고 이해가 안된다면 댓글은 남겨주시면 답변드리도록 하겠다.
2. clone() 메소드
만약 사용자가 사용하고 있던 Queue를 새로 하나 복제하고 싶을 때 쓰는 메소드다. 즉, 얕은 복사가 아닌 깊은 복사로 아예 다른 하나의 클론을 만드는 것이다.
단순히 = 연산자로 객체를 복사하게 되면 '주소'를 복사하는 것이기 때문에 복사한 객체에서 데이터를 조작할 경우 원본 객체까지 영향을 미친다. 즉 얕은 복사(shallow copy)가 된다는 것이다.
ArrayQueue<Integer> original = new ArrayQueue<>();
original.offer(10); // original에 10추가
ArrayQueue<Integer> copy = original;
copy.offer(20); // copy에 20추가
System.out.println("original ArrayQueue");
int i = 0;
for(Object a : original.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\ncopy ArrayQueue");
i = 0;
for(Object a : copy.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\noriginal ArrayQueue reference : " + original);
System.out.println("copy ArrayQueue reference : " + copy);[결과]
보다시피 객체의 주소가 복사되는 것이기 때문에 주소와 데이터 모두 같아져버리는 문제가 발생한다.
이러한 것을 방지하기 위해서 깊은 복사를 하는데, 이 때 필요한 것이 바로 clone()이다. Object에 있는 메소드이지만 접근제어자가 protected로 되어있어 구현해야 할 경우 반드시 Cloneable 인터페이스를 implement 해야한다.
즉, public class ArrayQueue implements Queue 에 Cloneable도 추가해주어야 한다.
그리고나서 clone()을 구현하면 되는데, 다음과 같이 재정의를 하면 된다.
@Override
public Object clone() {
// super.clone() 은 CloneNotSupportedException 예외를 처리해주어야 한다.
try {
@SuppressWarnings("unchecked")
ArrayQueue<E> clone = (ArrayQueue<E>) super.clone();// 새로운 큐 객체 생성
// 새로운 큐의 배열도 생성해주어야 함 (내부 객체는 깊은 복사가 되지 않기 때문)
clone.array = Arrays.copyOf(array, array.length);
return clone;
}
catch(CloneNotSupportedException e) {
throw new Error(e); // 예외처리는 여러분들이 자유롭게 구성하면 된다.
}
}조금 어려워 보일 수 있는데, 이해하지 못해도 된다. 자료구조에서 중요한 부분은 아니니...
설명을 덧붙이자면, super.clone() 자체가 생성자 비슷한 역할이고 shallow copy를 통해 사실상 new ArrayQueue<>() 를 호출하는 격이라 제대로 완벽하게 복제하려면 clone한 큐의 array 또한 새로 생성해서 해당 배열에 copy를 해주어야 한다.
위와같이 만들고 나서 clone()한 것 까지 포함해서 테스트를 해보자.
ArrayQueue<Integer> original = new ArrayQueue<>();
original.offer(10); // original에 10추가
ArrayQueue<Integer> copy = original;
ArrayQueue<Integer> clone = (ArrayQueue<Integer>) original.clone();
copy.offer(20); // copy에 20추가
clone.offer(30); // clone에 30추가
System.out.println("original ArrayQueue");
int i = 0;
for (Object a : original.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\ncopy ArrayQueue");
i = 0;
for (Object a : copy.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\nclone ArrayQueue");
i = 0;
for (Object a : clone.toArray()) {
System.out.println(i + "번 째 data = " + a);
i++;
}
System.out.println("\noriginal ArrayQueue reference : " + original);
System.out.println("copy ArrayQueue reference : " + copy);
System.out.println("clone ArrayQueue reference : " + clone);[결과]
결과적으로 clone으로 복사한 ArrayQueue는 원본 ArrayQueue에 영향을 주지 않는다.
3. sort() 메소드
ArrayQueue의 경우는 내부적으로 Object[] 배열을 사용하기 때문에 정렬 자체는 매우 쉽다.
일단 sort()를 구현하기 전에 자바의 비교기에 대해 알아야 한다.
자바의 데이터 정렬을 위한 비교기는 크게 두 가지가 있다. 하나는 Comparable, 다른 하나는 Comparator다. 정말정말 쉽게 말하자면 Comparable을 쓰는 경우는 해당 객체의 기본 정렬 방법을 설정할 때이고, Comparator의 경우는 특정한 경우에 임시적으로 쓸 수 있게 정렬을 정의할 때 쓰인다.
우리가 흔히 쓰는 int[] 배열, String[] 배열 등 수많은 클래스들은 기본적으로 자체 정렬 방식을 지원하기 때문에 Comparator을 쓰지 않아도 정렬 할 수 있었다.
만약 래퍼(Wrapper) 클래스 타입(ex. Integer, String, Double ...)이라면 따로 Comparator 을 구현해주지 않아도 되지만, 사용자 클래스, 예로들어 Student 클래스를 만든다거나.. 이러한 경우는 사용자가 따로 해당 객체에 Comparable를 구현해주거나 또는 Comparator를 구현해주어 파라미터로 넘겨주어야 한다.
Arrays.sort() 메소드를 뜯어본 분들은 알겠지만 Arrays.sort()의 종류중에서는 인자를 두 개 받는 경우가 있다. 정렬을 해보신 분은 알겠지만 가끔 2차원 배열을 정렬하고 싶을 때 다음과 같이 쓰지 않았는가?
int[][] arr = new int[10][10];
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
// 구현부
}
})이러한 메소드가 바로 아래 사진의 메소드로 간다.
위 사진을 보면 크게 if(c == null) 일 경우와 아닌 경우로 나뉜다.
즉, Comparator 인자가 있는지, 또는 없는지를 말해주는데, Comparator 인자(c)가 없는 경우 해당 객체의 Comparable 구현이 있는지를 확인하고 있으면 정렬하며, 구현되지 않았을 경우 에러를 뱉는다.
결과적으로 sort() 메소드를 만들 때, 기본적으로 두 가지 경우를 생각해야 한다는 것이다. 첫 번째는 객체에 Comparable이 구현되어 있어 따로 파라미터로 Comparator를 넘겨주지 않는 경우고, 다른 하나는 Comparator을 넘겨주어 정의 된 정렬 방식을 사용하는 경우다.
public void sort() {
/**
* Comparator를 넘겨주지 않는 경우 해당 객체의 Comparable에 구현된
* 정렬 방식을 사용한다.
* 만약 구현되어있지 않으면 cannot be cast to class java.lang.Comparable
* 에러가 발생한다.
* 만약 구현되어있을 경우 null로 파라미터를 넘기면
* Arrays.sort()가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
*/
sort(null);
}
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
// null 접근 방지를 위해 toArray로 요소만 있는 배열을 얻어 이를 정렬한뒤 덮어씌운다.
Object[] res = toArray();
Arrays.sort((E[]) res, 0, size, c);
clear();
/*
* 정렬된 원소를 다시 array에 0부터 차례대로 채운다.
* 이 때 front = 0 인덱스는 비워야 하므로 사실상 1번째 인덱스부터 채워야 한다.
*
*/
System.arraycopy(res, 0, array, 1, res.length); // res 배열을 array에 복사
this.rear = this.size = res.length;
}여기서 Comparator<? super E> 는 상속관계이면서 부모 클래스에서 정렬 방식을 따르는 경우도 생각하여 <? super E>로 하였다. 이러한 경우를 고려하지 않는다면 Comparator로 해주어도 종속관계 영향을 안받는 객체의 경우는 괜찮다.
그런다음 Object[] 배열을 Arrays.sort()메소드를 통해 정렬해주면 된다. 이 때 배열에 null이 들어가 있으면 NullPointerException 예외가 발생하기 때문에 이를 방지하기 위해 우리가 앞서 만들었던 toArray()메소드를 이용하여 요소들만 있는 배열을 하나 임시로 만들어 이 임시배열을 정렬해준뒤, 기존에 있던 배열(array)를 초기화 하고 이 배열에 덮어씌워주는 방식으로 한다.
이때 Comparator를 넘겨주는 방식은 크게 두 가지가 있는데, 그 중 하나인 Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) 를 쓸 것이다.
관련 API 문서는 아래 링크로 남겨두겠다.
그럼 한 번 테스트를 해보자.
Student 클래스를 통해 이름과 성적을 입력받고, 이를 정렬하는 테스트를 해보도록 한다.
<Student 클래스가 Comparable을 구현하지 않았을 경우>
[test2.java]
public class test2 {
public static void main(String[] args) {
ArrayQueue<Student> q = new ArrayQueue<>();
q.offer(new Student("김자바", 92));
q.offer(new Student("이시플", 72));
q.offer(new Student("조시샵", 98));
q.offer(new Student("파이손", 51));
q.sort();
for(Object a : q.toArray()) {
System.out.println(a);
}
}
}
class Student {
String name;
int score;
Student(String name, int score){
this.name = name;
this.score = score;
}
public String toString() {
return "이름 : " + name + "\t성적 : " + score;
}
}[결과]
이렇게 Comparable을 구현하지 않아 해당 객체의 정렬 방법을 몰라 빨갛게 에러를 뱉어준다. 즉, 명시적으로 Arrays.sort()에 정렬 방법을 알려주던가, Student 클래스에 정렬 방법을 구현하던가 해야한다.
<Comparator의 구현을 통해 명시적으로 Arrays.sort()에 파라미터로 넘기는 방법>
[test2.java]
이렇게 하면 정렬이 될까? 당연하겠지만 된다.
import java.util.Comparator;
public class test2 {
public static void main(String[] args) {
ArrayQueue<Student> q = new ArrayQueue<>();
q.offer(new Student("김자바", 92));
q.offer(new Student("이시플", 72));
q.offer(new Student("조시샵", 98));
q.offer(new Student("파이손", 51));
q.sort(customComp); // Comparator을 넘겨준다.
for(Object a : q.toArray()) {
System.out.println(a);
}
}
// 사용자 설정 comparator(비교기)
static Comparator<Student> customComp = new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.score - o1.score;
}
};
}
class Student {
String name;
int score;
Student(String name, int score){
this.name = name;
this.score = score;
}
public String toString() {
return "이름 : " + name + "\t성적 : " + score;
}
}[결과]
<Comparable의 구현을 통해 객체의 정렬 방법을 설정하는 방법>
객체 기본 정렬방식을 설정해주는 방법. 즉 Comparable 구현 방법으로도 가능하다.
public class test2 {
public static void main(String[] args) {
ArrayQueue<Student> q = new ArrayQueue<>();
q.offer(new Student("김자바", 92));
q.offer(new Student("이시플", 72));
q.offer(new Student("조시샵", 98));
q.offer(new Student("파이손", 51));
q.sort(); // Comparator 인자가 필요하지 않음
for(Object a : q.toArray()) {
System.out.println(a);
}
}
}
class Student implements Comparable<Student> {
String name;
int score;
Student(String name, int score){
this.name = name;
this.score = score;
}
public String toString() {
return "이름 : " + name + "\t성적 : " + score;
}
@Override
public int compareTo(Student o) {
return o.score - this.score;
}
}이러면 sort() 내부에서 Comparator가 없으니 해당 클래스의 Comparable에서 compareTo() 을 구현한 내용을 찾아 작성한대로 정렬을 해준다.
[결과]
참고로 ArrayList 구현 할 때에도 sort() 메소드를 구현하고 싶다면 위와 같은 방법으로 구현하면 된다.
[toArray, clone, sort 메소드 묶어보기]
더보기
- 전체 코드
import Interface_form.Queue;
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
/**
*
* @param <E> the type of elements in this Queue
*
* @author st-lab.tistory.com
* @version 1.0
* @see Queue
*
*/
public class ArrayQueue<E> implements Queue<E>, Cloneable {
private static final int DEFAULT_CAPACITY = 64; // 최소(기본) 용적 크기
private Object[] array; // 요소를 담을 배열
private int size; // 요소 개수
private int front; // 시작 인덱스를 가리키는 변수(빈 공간임을 유의)
private int rear; // 마지막 요소의 인덱스를 가리키는 변수
// 생성자1 (초기 용적 할당을 안할 경우)
public ArrayQueue() {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.front = 0;
this.rear = 0;
}
// 생성자2 (초기 용적 할당을 할 경우)
public ArrayQueue(int capacity) {
this.array = new Object[capacity];
this.size = 0;
this.front = 0;
this.rear = 0;
}
private void resize(int newCapacity) {
int arrayCapacity = array.length; // 현재 용적 크기
Object[] newArray = new Object[newCapacity]; // 용적을 변경한 배열
/*
* i = new array index
* j = original array
* index 요소 개수(size)만큼 새 배열에 값 복사
*/
for (int i = 1, j = front + 1; i <= size; i++, j++) {
newArray[i] = array[j % arrayCapacity];
}
this.array = null;
this.array = newArray; // 새 배열을 기존 array의 배열로 덮어씌움
front = 0;
rear = size;
}
@Override
public boolean offer(E item) {
// 용적이 가득 찼을 경우
if((rear + 1) % array.length == front) {
resize(array.length * 2); // 용적을 두 배 늘려준다.
}
rear = (rear + 1) % array.length; // rear을 rear의 다음 위치로 갱신
array[rear] = item;
size++; // 사이즈 1 증가
return true;
}
@Override
public E poll() {
if(size == 0) { // 삭제할 요소가 없을 경우 null 반환
return null;
}
front = (front + 1) % array.length; // front 를 한 칸 옮긴다.
@SuppressWarnings("unchecked")
E item = (E) array[front]; // 반환할 데이터 임시 저장
array[front] = null; // 해당 front의 데이터 삭제
size--; // 사이즈 감소
// 용적이 최소 크기(64)보다 크고 요소 개수가 1/4 미만일 경우
if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다.
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
return item;
}
public E remove() {
E item = poll();
if(item == null) {
throw new NoSuchElementException();
}
return item;
}
@Override
public E peek() {
// 요소가 없을 경우 null 반환
if(size == 0) {
return null;
}
@SuppressWarnings("unchecked")
E item = (E) array[(front + 1) % array.length];
return item;
}
public E element() {
E item = peek();
if(item == null) {
throw new NoSuchElementException();
}
return item;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object value) {
int start = (front + 1) % array.length;
/**
* i : 요소 개수만큼만 반복한다.
* idx : 원소 위치로, 매 회 (idx + 1) % array.length; 의 위치로 갱신
*/
for(int i = 0, idx = start; i < size; i++, idx = (idx + 1) % array.length) {
if(array[idx].equals(value)) {
return true;
}
}
return false;
}
public void clear() {
for(int i = 0; i < array.length; i++) {
array[i] = null;
}
front = rear = size = 0;
}
public Object[] toArray() {
return toArray(new Object[size]);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
final T[] res;
// 들어오는 배열의 길이가 큐의 요소 개수보다 작은경우
if(a.length < size) {
/*
* front가 rear보다 앞에 있을 경우 (또는 요소가 없을 경우 f==r)
* ______________________
* | | | | | | | |
* ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
* f r
*/
if(front <= rear) {
return (T[]) Arrays.copyOfRange(array, front + 1, rear + 1, a.getClass());
}
/*
* front가 rear보다 뒤에 있을 경우
* ______________________
* | | | | | | | |
* ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
* r1 f4
*/
res = (T[]) Arrays.copyOfRange(array, 0, size, a.getClass());
int rearlength = array.length - 1 - front; // 뒷 부분의 요소 개수
// 뒷 부분 복사
if(rearlength > 0) {
System.arraycopy(array, front + 1, res, 0, rearlength);
}
// 앞 부분 복사
System.arraycopy(array, 0, res, rearlength, rear + 1);
return res;
}
/*
* front가 rear보다 앞에 있을 경우 (또는 요소가 없을 경우 f==r)
* ______________________
* | | | | | | | |
* ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
* f r
*/
if(front <= rear) {
System.arraycopy(array, front + 1, a, 0, size);
}
/*
* front가 rear보다 뒤에 있을 경우
* ______________________
* | | | | | | | |
* ˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉˉ
* r f
*/
else {
int rearlength = array.length - 1 - front; // 뒷 부분의 요소 개수
// 뒷 부분 복사
if(rearlength > 0) {
System.arraycopy(array, front + 1, a, 0, rearlength);
}
// 앞 부분 복사
System.arraycopy(array, 0, a, rearlength, rear + 1);
}
return a;
}
@Override
public Object clone() {
// super.clone() 은 CloneNotSupportedException 예외를 처리해주어야 한다.
try {
@SuppressWarnings("unchecked")
ArrayQueue<E> clone = (ArrayQueue<E>) super.clone();// 새로운 큐 객체 생성
// 새로운 큐의 배열도 생성해주어야 함 (내부 객체는 깊은 복사가 되지 않기 때문)
clone.array = Arrays.copyOf(array, array.length);
return clone;
}
catch(CloneNotSupportedException e) {
throw new Error(e);
}
}
public void sort() {
/**
* Comparator를 넘겨주지 않는 경우 해당 객체의 Comparable에 구현된
* 정렬 방식을 사용한다.
* 만약 구현되어있지 않으면 cannot be cast to class java.lang.Comparable
* 에러가 발생한다.
* 만약 구현되어있을 경우 null로 파라미터를 넘기면
* Arrays.sort()가 객체의 compareTo 메소드에 정의된 방식대로 정렬한다.
*/
sort(null);
}
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
// null 접근 방지를 위해 toArray로 요소만 있는 배열을 얻어 이를 정렬한뒤 덮어씌운다.
Object[] res = toArray();
Arrays.sort((E[]) res, 0, size, c);
clear();
/*
* 정렬된 원소를 다시 array에 0부터 차례대로 채운다.
* 이 때 front = 0 인덱스는 비워야 하므로 사실상 1번째 인덱스부터 채워야 한다.
*
*/
System.arraycopy(res, 0, array, 1, res.length); // res 배열을 array에 복사
this.rear = this.size = res.length;
}
}