POWER JAVA 7장 mini project 큐(queue) 구현하기

안녕하세요

이 문제는 접한 지 몇일 지났지만, 어떻게 푸는 게 좋을지 잘모르겠어서 한 블로그를 참조하게 되었습니다.

꽤 좋은 문제라고 생각하기에 저도 한번 죽 따라쳐보고, 어째서 구현되는지 아래에 블로그에서 해설을 보면서 고민해봤습니다.

책에 있는 문제대로 배열을 활용한 큐(queue) 구현입니다.

 

출처는 다음과 같으며 이 글은 개인공부 기록용이기에 영리를 추구하지 않으며, 변경도 허용하지 않습니다. 혹시라도 문제가 될 시 바로 삭제하겠습니다.

 https://st-lab.tistory.com/183#size

 

인터페이스 

package test;
 
public interface Queue<E> {
 
    boolean offer(E e);
    
    E poll();
    
    E peek();
}
 

인터페이스 구현 클래스

package test;
 
import java.util.NoSuchElementException;
 
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;// 마지막 요소의 인덱스를 가리키는 변수
 
    // 생성자 초기 용적 할당하지 않을 경우
    public ArrayQueue() {
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.front = 0;
        this.rear = 0;
    }
 
    // 생성자 초기 용적 할당할 경우
    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는 요소의 개수만큼 반복
        // j는 front 다음 위치부터 시작하여 요소의 개수만큼 반복되는 동안
        // front가 한 칸씩 이동하여서 값을 증가시켜준다.
        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;
        // front와 rear의 위치를 변경시켜준다.
    }
 
    @Override
    public boolean offer(E item) {
        // 용적이 가득찼을 경우
        if (rear + 1 % array.length == front) {
            resize(array.length * 2);// 용적을 두 배로 늘려준다.
        }
        // rear의 위치를 rear의 다음 위치로 갱신시켜준다.
        // 그리고 거기에 값을 넣어준다.
        rear = (rear + 1) % array.length;
        array[rear] = item;
        // 값을 추가했으니 요소 개수를 추가해준다.
        size++;
        return true;
    }
 
    @Override
    public E poll() {
        // 삭제할 요소가 없ㅇ르 경우 null 반환
 
        if (size == 0) {
            return null;
        }
 
        // front를 한 칸 옮긴다.
        front = (front + 1) % array.length;
 
        @SuppressWarnings("unchecked")
        // 타입 안정성에 대해 경고를 보낸다
        // object[] 배열의 데이터를 E타입으로 캐스팅해서 반환을 하는 것인데,
        // 이 과정에서 변환할 수 없는 데이터가 있을 수 있다라고 경고가 뜨는 것을
        // 받아들이는 데이터 타입은 유일하게 E타입만 존재. 즉 형안정성이 확실하다고 생각하여
        // 경고문이 안뜨도록 위의 어노테이션을 썼다.
        E item = (E) array[front];
        // 반환할 데이터 임시 저장
 
        array[front] = null; // 해당 front의 데이터 삭제
        size--; // 사이즈 감소
 
        // 용적이 최소 크기보다 크고 요소 개수가 1/4 미만일 경우
 
        // 아무리 작아도 최소용적 미만으로 줄이지는 않도록 한다.
        if (array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
            resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
 
        }
        return item;
    }
 
    // API 문서에서 보면 poll()과 remove()의 기능 차이는 null 값을 반환하냐
    // 예외를 던져주냐이기에 기존 poll()값이 null값 즉 비어 있을 경우 예외를 던져주는 식으로 만들면 된다.
    public E remove() {
        E item = poll();
 
        if (item == null) {
            throw new NoSuchElementException();
        }
 
        return item;
    }
 
    // poll()메소드에서 삭제 과정없이 가장 앞에 있는 데이터 값을 반환받는 것이 peek()메소드이다.
    @Override
    public E peek() {
 
        // 요소가 없을 경우 null 반환
        if (size == 0) {
            return null;
        }
 
        @SuppressWarnings("unchecked")
        E item = (E) array[(front + 1) % array.length];
        return item;
    }
 
    // peek()과의 차이는 null 값 반환이냐 예외를 던져주냐의 차이이다.
    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;
    }
 
    // contains() 는 현재 찾고자 하는 요소가 큐에 들어가있는지를 알려주는 메소드다
 
    public boolean contains(Object value) {
        int start = (front + 1) & array.length;
 
        // i 요소 개수만큼만 반복한다.
        // idx front 다음 위치부터 시작하여서 그 다음 위치로 계속해서 변경시켜준다.
        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 static void main(String[] args) {
 
    }
 
}