ArrayDeque 구현 with Java

저번까지는 Queue를 구현해봤다.

이번부터는 Deque을 구현해 보겠다.
Deque도 구현하는 방식이 크게 두개가 있다.
먼저 Array로 구현해 보겠다.

Deque의 특징

앞서 구현한 Queue는 선입선출이었다.
삽입은 rear에서 일어나고, 삭제는 front에서 일어났다.

Deque은 Double-Ended-Queue의 약자로, Queue와는 달리 front와 rear 양 끝에서 삽입 삭제연산을 지원한다.
그러므로 Stack와 Queue의 방식을 모두 지원한다.

1. resize(int newCapacity)

Array방식으로 구현하므로 배열의 사이즈를 늘려주거나 줄여줘야 한다.
이 함수가 호출되는 시점은 size가 바뀌는 연산을 할 때이다.
그러니까 offer, poll, remove 연산을 할 때 이 함수를 호출해야 한다.

2. offer

Deque은 양 끝에서 삽입 연산을 지원한다고 했다.

삽입 전에 배열의 용량을 체크해서 꽉 찼을 경우에 2배로 늘려주는 작업을 한다.
그리고 그 후엔 각 함수에 맞는 위치에 데이터를 삽입하고 front를 한칸 뒤로 밀어준다.

배열을 원형으로 생각하기 때문에 만약 front가 0일경우 -1을 하면 음수가 되므로, 그럴경우엔 index 0의 전 index인 array.length -1 로 초기화 해준다.

3. remove, poll

덱이 비어있을 때 remove나 poll 연산을 하면 오류가 생긴다.
poll은 예외처리로 null을 리턴하고 remove는 예외를 던져준다.

주의할 점은 삭제연산을 한 뒤 resize함수를 호출하는 과정이다.
맨 처음엔 사이즈가 array.length/2 보다 작으면 배열의 길이를 줄여주게 했었다.

그렇게 하면 경계선에서 삽입 삭제를 반복할 때 오버헤드가 늘어나게 된다.
그러므로 /2가 아닌 /4로 조정해 주었다. 이렇게 함으로써 오버헤드를 줄였다.

4. peek, get

peek과 get함수도 실행 로직은 같고 예외를 처리하는 방법이 다르다.
peek은 만약 덱이 비어있을 때 null을 리턴하고 get은 예외를 리턴한다.

전체코드

package Queue;

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

public class MyArrayDeque<E> implements CustomArrayDeque<E>{

    private Object[] array;
    private int size;

    private int front;
    private int rear;

    public MyArrayDeque() {
        this.array = new Object[10];
        this.size = 0;
        this.front = 0;
        this.rear = 0;
    }
    @Override
    public void resize(int newCapacity) {

        int arrayCapacity = array.length;
        Object[] newArray = new Object[newCapacity];

        int count = 1;
        for (int i = front + 1; count <= size; i++) {
            newArray[count++] = array[i % arrayCapacity];
        }

        this.array = newArray;

        front = 0;
        rear = size;
    }

    @Override
    public boolean offerLast(E item) {


        if(size == array.length - 1)
            resize(array.length * 2);

        rear = (rear+1) % array.length;
        array[rear] = item;
        size++;
        return true;
    }

    @Override
    public boolean offerFirst(E item) {
        if(size == array.length - 1)
            resize(array.length * 2);
        array[front--] = item;
        if(front < 0)
            front = array.length-1;

        size++;
        return true;
    }
    @Override
    public boolean offer(E e) {

        return offerLast(e);
    }

    @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/4 && array.length > 10)
            resize(Math.max(array.length/2 , 10));


        return returnData;
    }

    @Override
    public E pollFirst() {

        if(isEmpty())
            return null;

        return poll();
    }


    @Override
    public E pollLast() {

        if(isEmpty())
            throw new NoSuchElementException("비어있음");

        E returnData = (E)array[rear];
        array[rear] = null;
        rear = (rear + array.length - 1) % array.length;
        size--;

        if(size < array.length/4 && array.length > 10)
            resize(Math.max(array.length/2 , 10));

        return returnData;
    }


    @Override
    public E removeFirst() {
        if(isEmpty())
            throw new NoSuchElementException("비어있음");

        return pollFirst();
    }

    @Override
    public E removeLast() {
        if(isEmpty())
            throw new NoSuchElementException("비어있음");

        return pollLast();
    }

    @Override
    public E remove() {

        return removeFirst();
    }


    @Override
    public E peek() {

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

    @Override
    public E peekFirst() {

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

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

        return (E)array[rear];
    }

    @Override
    public E getFirst() {
        if(isEmpty())
            throw new NoSuchElementException("비어있음");

        return (E)array[front];
    }

    @Override
    public E getLast() {
        if(isEmpty())
            throw new NoSuchElementException("비어있음");

        return (E)array[rear];
    }

    @Override
    public boolean isEmpty() {

        return (rear + 1) % array.length == front;
    }

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

    @Override
    public void clear() {
        array = new Object[10];
        front = 0;
        rear = 0;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        final T[] res;
        if(a.length < size) {

            if(front <= rear) {
                return (T[]) Arrays.copyOfRange(array, front + 1, rear + 1, a.getClass());
            }

            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;
        }

        if(front <= rear) {
            System.arraycopy(array, front + 1, a, 0, size);
        }

        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[] toArray() {
        return toArray(new Object[size]);
    }

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


}