ArrayQueue 구현 with Java

Queue는 Stack과 반대되는 자료구조이다.
First In First Out. 먼저 들어온 데이터가 먼저 나간다.

Queue를 구현하는 방식은 크게 두개로 나뉘는데 먼저 배열에 데이터를 저장하는 방식으로 구현해보자.

구현하기 전에 알아둬야 할 것.

Queue는 List와는 다르게 처음 요소의 인덱스가 0이 되는것이 아니다.
왜냐하면 Queue의 poll 연산을 하면 앞에서 요소가 빠진다.
List에서도 remove함수를 통해 처음 요소를 삭제할 수 있긴하지만, Queue와의 차이점은 Queue는 앞에서만 삭제하고, List는 전 범위에서 삭제연산을 할 수 있다는 차이점이 있다.

그러므로 삭제를 하면 배열의 요소들을 한칸씩 당겨서 처음 인덱스를 0으로 고정하는 List와는 달리, Queue는 front를 한칸 증가시키는 작업을 한다.

이러한 queue의 특성 때문에 연산이 계속되다보면 어느새 배열의 모든 공간을 쓰기 힘들다.

이 문제를 해결하는 방법은 선형인 배열을 원형으로 접근하여 해결한다.

배열을 원형으로 접근하면 또 문제가 생긴다.
배열이 모두 차있을때와 배열의 모든 공간이 비어있을 때를 구분해줄 수 없다.
만약 선형일 때는 front = 0, rear = 0일 경우에 비어있는지 확실하게 알 수 있지만, 원형일 때는 위의 두가지 상황이 모두 가능하다.
그러므로 그 차이를 알기 위해서 front를 비워두는 것이다.
그렇게하면 front == rear일 때 size = 0인 상황이고
(rear + 1) % array.length == front 일 경우엔 배열이 꽉 찬 상황이 된다.

1. resize(int newCapacity)

newCapacity만큼의 사이즈로 배열을 리사이징하는 함수이다.

newCapacity를 사이즈로 하는 배열을 만들어서 그 전의 배열을 복사해주면 된다.
여기서 중요한건 front의 성질을 생각해서 front가 가르키는 요소는 비워서 복사해야 한다는 것이다.

2. poll(), remove()

둘 다 삭제하는 함수이다.
두 함수는 예외를 처리하는 방법이 다른데, poll은 만약 size가 비워져 있을 경우 null을 리턴하고, remove함수는 예외를 던진다.

3. peek(), element()

둘다 삭제하지 않고, 맨 앞의 요소를 리턴한다.
peek은 예외일 때 null을 리턴하고, element는 예외를 던진다

4. offer(E data)

예외처리 - 배열이 꽉 차있다면 늘려준다.
다른 연산은 쉬우니까 넘어간다.

5. size(), isEmpty(), contains(Object value), clear()

size는 getter함수이므로 인스턴스 변수를 리턴하면 됨.
empty는 비어있는지 확인하는 함수이다.
비어있는지 확인하는 방법은 두가지인데 size == 0과 front == rear 이 두가지 상황이다.

contains 함수는 매개변수로 받은 value가 배열에 포함되면 true, 포함되지 않는다면 false를 리턴하는 함수이다.
그러므로 front+1부터 rear까지 배열을 돌아서 확인해주면 된다.

clear 함수는 말 그대로 배열을 비우는 함수이다.
두 가지 방법이 있는데
첫번째는 array에 새로운 배열을 할당해주는 것이다.
그렇게 되면 그 전의 배열을 가르키는 참조변수가 없으므로 gc에서 알아서 메모리를 해제해준다.

두번째는 배열을 돌아서 개발자가 명시적으로 null을 초기화시켜 주는 방법이다.

6. toArray(), toArray(T[] a)

toArray()함수와 toArray(T[] a)함수는 배열을 리턴한다.
다른점은 첫번째 함수는 매개변수를 갖지 않는다.
현재 array를 정돈해서 리턴하면 된다. 그래서 size만큼 배열을 할당하여 toArray(T[] a)의 매개변수로 주었고 그대로 리턴했다.

toArray(T[] a)함수는 두가지로 나뉜다.
1. 매개변수의 배열의 길이가 인스턴스 배열의 길이보다 클 경우
2. 아닌경우

1번과 2번의 차이점은 얼마나 반복해주냐의 차이이다.

1번의 경우에는 인스턴스 배열의 길이만큼 초기화를 반복하면 된다.
그러면 인스턴스 배열이 복사되고, a의 남은 공간들은 그대로 보존된 채 리턴된다.

2번의 경우에는 매개변수 배열의 길이만큼 초기화를 반복하면 된다.
매개변수 배열의 길이가 더 작으므로, 매개변수 배열의 모든 요소들이 덮어씌워지게 된다.

전체 코드

package Queue;

import Queue.CustomArrayQueue;

import java.util.Arrays;
import java.util.NoSuchElementException;

public class MyArrayQueue<E> implements CustomArrayQueue<E> {


    private Object[] array;
    private int size;
    private int front;
    private int rear;

    public MyArrayQueue(){
        array = new Object[10];
        size = 0;
        front = 0;
        rear = 0;
    }

    @Override
    public boolean offer(E e) {

        if(size == array.length - 1){
            resize(array.length * 2);
        }
        rear = (rear+1) % array.length;
        array[rear] = e;
        size++;

        return true;
    }

    @Override
    public void resize(int newCapacity) {

        Object[] newArray = new Object[newCapacity];

        int idx = 1;
        for (int i = front+1; idx <= size; i++)
            newArray[idx++] = array[i % array.length];

        this.array = newArray;
        front = 0;
        rear = size;
    }

    @Override
    public E poll() {
        if(isEmpty())
            return null;

        front = (front+1) % array.length;
        E returnData = (E)array[front];
        array[front] = null;
        size--;
        if(size < array.length/2 && 10 < array.length/2)
            resize(array.length/2);
        return returnData;
    }

    @Override
    public E remove() {
        if(isEmpty())
            throw new NoSuchElementException("비어 있습니다.");

        return poll();
    }

    @Override
    public E peek() {
        if(isEmpty())
            return null;

        return (E)array[(front + 1) % array.length];
    }

    @Override
    public E element() {
        if(isEmpty())
            throw new NoSuchElementException("비어 있습니다.");

        return peek();
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object value) {
        for(int i = front + 1; (i % array.length) != rear + 1; i++){
            if(array[i % array.length].equals(value))
                return true;
        }

        if(array[rear].equals(value))
            return true;

        return false;
    }

    @Override
    public void clear() {
        for(int i = front+1; i% array.length != front; i++)
            array[i%array.length] = null;

        size = 0;
        front = 0;
        rear = 0;
    }

    @Override
    public Object[] toArray() {
        return toArray(new Object[size]);
    }

    @Override
    public <T> T[] toArray(T[] a) {
        int iterSize = size;
        if(a.length < size)
          iterSize = a.length;


        int idx = 0;
        for(int i = front+1; idx < iterSize && i != rear+1; i++)
            a[idx++] = (T)array[i % array.length];

        return a;
    }

}