선입선출의 대표적 자료구조인 Queue를 구현해보자.Java에서 제공하고 있는 Queue인터페이스가 있고 Queue인터페이스를 구현하는 라이브러리는 크게 PriorityQueue, ArrayDeque, LinkedList가 있다. LinkedList에도 Queue의 모든 메소드가 구현되어있어서 큐를 사용하려면 아래처럼 선언하였을것이다.
Queue<Integer> queue = new LinkedList(); 대개는 LinkedList로 구현한 큐가 쓰이지만 , 상황에 따라 ArrayDeque이나 PriorityQueue처럼 내부적으로 배열을 사용하여 구현한 큐 자료구조도 있기 때문에 이번에는 배열을 이용하여 구현해보자.
기본적으로 Object[] 배열을 사용하여 데이터들을 관리하고 있다.
큐는 기본적으로 선입선출이다.(First In First Out) 이름에서 알 수 있듯이 먼저 들어온 것이 먼저 나간다. 놀이공원에서 순서를 기다리는 사람들을 생각해보면 편할것이다.
관람차를 타려고 기다리는 줄이 있다. 우리나라의 정서에 따르면 제일 오래기다린 사람 즉 가장 첫번째로 온 사람이 먼저 들어가야한다.
이것이 큐이다.
하지만 배열로 구현했을경우 문제가 있다. 
offer를 하면 뒤에붙는다. poll을 하면 앞에것이 빠진다. 계속 반복하다보면 배열의 뒤에 요소들이 모이게된다.
그렇다고 poll을 할때마다 요소들을 옮겨주면 비효율적일것이다. 크기를 늘리게 된다면 배열의 앞쪽 부분들이 남아있어서 이것도 비효율적이다.
이를 해결하려면 배열의 앞에 넣으면된다. 저 배열을 원형이라고 생각해보자. 이걸 생각해낸 사람도 엄청 대단한것같다.
삽입과 삭제가 엄청 쉬워질 것이다.
이제 구현을 해보자
<필수목록>
- 클래스 및 생성자 구성
- resize 메소드 구현
- offer 메소드 구현
- poll 메소드 구현
- peek 메소드 구현
- size, isEmpty, contains, clear 메소드 구현
클래스 및 생성자 구성
public class ArrayQueue<E> implements Queue<E> {
private static final int DEFAULT_CAPACITY = 8; // 최소(기본) 용적 크기
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 : 상수로 사용할 용량의 기본값이다.
Object[] array : 요소들이 담길 배열이다.
size : 요소의 개수이다.
front : 시작 위치를 가리키는 변수이다. (빈공간)
rear : 마지막 요소의 위치를 가리키는 변수이다.
생성자는 공간을 할당해주지 않으면 DEFAULT_CAPACITY로 해주고 공간 용량을 정해주면 그만큼 할당해주는것으로 하였다.
resize 메소드 구현
용량이 부족하거나 여유로울때 조정하는 함수이다. 하지만 두개를 나누어서 생각할 필요가 없다. 이유는 코드를 보면 나온다.
public void resize(int capacity){
Object[] new_array = new Object[capacity];
for(int i = 1, j = front + 1 ; i <= size; i++, j++){
new_array[i] = array[ j % array.length ];
}
array = new_array;
front = 0;
rear = size; // 1부터 채워넣었으니 size와 인덱스는 같다.
}크기를 늘려야 하는 경우
꽉찼을 경우이다. ((rear + 1) % arrayCapacity == front) 이다.
출처: https://st-lab.tistory.com/183
arrayCapacity로 나누어주는 이유는 rear 가 7이고 front가 0일때를 생각해보자. rear + 1 == front 라고 간단히 했을때는 rear 가 8 front 가 0으로 내가 생각하지 않았던 오류가 나게된다. rear + 1 % arrayCapacity 를 해준다면 rear가 0이 되어서 조건이 맞게된다.
크기를 줄여야 하는 경우
데이터가 1/4미만으로 떨어질 경우에는 필요없는 공간이 너무 많아지게 되므로 절반정도로 줄인다.
offer 메소드 구현
@Override
public boolean offer(E e) {
//늘리기
if( (rear + 1) % array.length == front){
resize(array.length * 2);
}
rear = (rear + 1) % array.length;
array[rear] = e;
size++;
return true;
}rear를 한칸 늘려주고 그곳에 요소를 집어넣는다. 중요한것은 꽉찼을때 크기를 늘려주는 것이다.
poll 메소드 구현
poll은 remove와 하는일은 똑같은데 삭제할 요소가 없을경우에 처리하는 방법이 다르다. poll은 null을 반환하고 remove는 예외를 발생시킨다.
@Override
public E poll() {
if(size == 0){
return null;
}
front = ( front +1) % array.length;
E data = (E)array[front];
array[front] = null;
size--;
if(array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
// 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다.
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
System.out.println("resize 줄이기 ");
}
return data;
}peek 메소드 구현
@Override
public E peek() {
if(size == 0){
return null;
}
return (E)array[front % array.length + 1];
}첫번째에 위치한 요소가 보고싶을때 하는 함수이다.
size, isEmpty, contains, clear 메소드 구현
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object value) {
int start = (front + 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;
}```
