[자료구조] 7. 배열 큐(Array Queue) 구현

Queue

선입선출의 대표적 자료구조인 Queue를 구현하고자 한다. java에서 제공하고 있는 Queue는 인터페이스이고 이 Queue 인터페이스를 구현하는 라이브러리는 크게 ArrayDeque, LinkedList, PriorityQueue가 있다. 대개는 LinkedList로 구현한 큐가 쓰이지만, 상황에 따라 ArrayDeque나 PrioirityQueue처럼 내부적으로 배열을 사용해 구현하는 큐 자료구조도 있다.

 

기본적으로 배열을 사용하여 구현되는 자료구조 클래스는 내부에서 최상위 타입인 Object[] 배열을 사용하여 데이터들을 관리하고 있다. 

---

큐의 삭제가 계속된다면 뒤에 있던 원소들을 앞으로 땡겨오지는 않는다. 결국 원소들이 뒤로 치우치게 되는 경우가 발생하는데 삭제가 발생할때마다 모든 원소들을 한자리씩 땡겨오는것은 매우 비효율적이다. 이를 해결하기 위해 배열을 '원형'이라고 생각하고 새로 추가 되는 원소들을 앞의 빈자리에 다시 채워넣는 것이다. 이 때, 가장 마지막 원소의 위치를 가리키는 변수 front(앞), rear(뒤)가 필요하다.

 

 

만약 원소를 추가한다면? 0번째 인덱스에 추가하는 것이다.

 

그리고 반대로 원소를 삭제한다면 front + 1번째, 즉 인덱스 4에 위치한 원소가 삭제된다.

쉽게 생각하면 rear와 front에 따라서 원소가 추가되고 삭제된다고 보면 된다. 위와 같은 방식으로 효율적으로 배열을 관리할 수 있다. 그리고 더 이상 빈자리가 없다면 그 때 배열의 크기를 늘려준다.

 

여기서 궁금증은 rear은 채워져있는데 front는 왜 비워져있을까? 다음 그림을 통해 이해해보자.

 

 

front 위치를 비워두는 이유는 front와 rear가 엇갈려버리는 상황이 발생할 수 있다. 이렇게 되면 비어있는지 가득차있는지 두 변수만으로는 알 수가 없다. 다음 그림을 보면 더 이해가 쉬울것이다.

 

 

 

그래서 한자리를 비워서 front와 rear를 통해 큐가 비어있음을 확인할 수 있다. front == rear라면 큐는 비어있는 상태이고 비어있다면 다시 두 변수 모두 0으로 초기화 하면 된다.

 

이러한 구조를 Circular Queue, 원형 큐, 환형 큐라고도 한다.

---

ArrayQueue 구현

 

<필수 목록>

• 클래스 및 생성자
• resize()
• offer()
• poll()
• peek()
• size, isEmpty, contains, clear

 

<부가 목록>

• toArray, clone, sort

---

Queue 클래스 및 생성자 구성

public class ArrayQueue<E> implements QueueInterface<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;
    }
}

 

---

동적할당을 위한 resize() 메소드 구현

 

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 = newArray;  // 새 배열을 기존 array 의 배열로 덮는다.

    front = 0;
    rear = size;
}

 

용량을 증가하는 경우 : ((rear + 1) % arrayCapacity == front)

 

용량이 가득찰 경우는 rear의 다음 인덱스(rear + 1) 이 front랑 같다는 말이다. 다만 (rear + 1)에 % arrayCapacity 즉, 기존 배열의 길이를 나누는 이유는 front가 rear보다 작은 경우를 고려해야 하기 때문이다. 예를 들어 rear가 7이고 front가 1이라면 7 + 1 = 8이므로 0과 같지 않다. 즉 나눠준 나머지를 해야 정확한 조건으로 용량을 늘릴 수 있다.

 

 

용량을 줄여야 하는 경우 : (size < (arrayCapacity / 4))

 

데이터가 1/4 미만으로 떨어지는 경우에는 필요한 공간이 너무 많아지므로 절반 정도로 줄인다. 새로운 용량의 배열에 값을 복사하는 과정 자체는 같기 때문에 따로 조건문을 달지 않고 파라미터로 받은 새 용량을 이용해 사이즈를 변경할 것이다.

 

---

offer()

Queue의 offer는 항상 맨뒤에 데이터를 추가해야 해서 한 종류 밖에 없다. 다만 고려할 부분은 배열의 마지막 인덱스에 도달했을 경우와 배열이 꽉 차있을 경우이다.

 

 

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

 

---

poll()

리스트에서의 remove()와 같은 역할로 front + 1 위치에 있는 요소를 삭제하면 된다. 주의해야할 것은 '삭제할 요소가 없는 경우'이다.

자바의 Queue에는 add - offer, remove - poll, element - peek 이 각각 대응되는데 두 가지를 모두 제공하는 이유는 다음과 같다.

 

add 의 경우 용량이 제한되어 있는데 용량 보다 많은 요소를 추가할 경우 예외를 던지게 되는데 이 글에서 구현하는 것은 최대 제한을 걸지 않아 넘어간다.

 

remove 같은 경우 삭제할 요소가 없다면 NoSuchElementException 예외를 발생시킨다. 하지만 poll은 삭제할 요소가 없다면 Null을 반환한다. poll 메소드를 구현하고 이것을 remove 메소드에 응용해볼것이다.

 

 

1. poll()

 

@Override
public E poll() {

    if (size == 0) {
        return null;
    }

    front = (front + 1) % array.length;

    @SuppressWarnings("unchecked")
    E item = (E) array[front];  // 반환할 데이터 임시 저장

    array[front] = null;
    size--;

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

    return item;
}

 

2. remove()

 

public E remove() {
    E item = poll();

    if (item == null) {
        throw new NoSuchElementException();
    }

    return item;
}

 

 

---

peek()

 

1. peek()

 

@Override
public E peek() {

    if (size == 0) {
        return null;
    }

    @SuppressWarnings("unchecked")
    E item = (E) array[(front + 1)  % array.length];

    return item;
}

 

 

 

2. element()

public E element() {
    E item = peek();

    if (item == null) {
        throw new NoSuchElementException();
    }

    return item;
}

---

size, isEmpty, contains, clear 메소드 구현

 

1. size()

 

public int size() {
    return size;
}

 

2. isEmpty()

 

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

 

3. 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()

 

public void clear() {
    for (int i = 0; i < array.length; i++) {
        array[i] = null;
    }

    front = rear = size = 0;
}

 

---

<부가 목록>

 

1. toArray()

 

Array Queue에서는 앞이 뒤보다 항상 앞에 있는것이 아니라 중간이 비어버리는 경우가 발생할 수 있으므로 정확한 시작, 끝 위치를 설정해야 한다. 복사되는 원소의 범위는 (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 보다 앞에 있을 경우 (또는 요소가 없을 경우 front == rear)
         */

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

        /**
         * front 가 rear 보다 뒤에 있을 경우
         */
        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 보다 앞에 있을 경우 (또는 요소가 없을 경우 front == rear)
     */
    if (front <= rear) {
        System.arraycopy(array, front + 1, a, 0, size);
    }
    /**
     * front 가 rear 보다 뒤에 있을 경우
     */
    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;
}

 

 

2. 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);
    }
}

 

 

3. sort()

 

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, front 는 비워야 하기 때문에 사실상 1 부터 채워야 한다.
     */
    System.arraycopy(res, 0, array, 1, res.length);

    this.rear = this.size = res.length;
}

 

---

전체 코드

public class ArrayQueue<E> implements QueueInterface<E>, Cloneable {

    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 = 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 = newArray;  // 새 배열을 기존 array 의 배열로 덮는다.

        front = 0;
        rear = size;
    }

    @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() {

        if (size == 0) {
            return null;
        }

        front = (front + 1) % array.length;

        @SuppressWarnings("unchecked")
        E item = (E) array[front];  // 반환할 데이터 임시 저장

        array[front] = null;
        size--;

        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() {

        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 보다 앞에 있을 경우 (또는 요소가 없을 경우 front == rear)
             */

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

            /**
             * front 가 rear 보다 뒤에 있을 경우
             */
            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 보다 앞에 있을 경우 (또는 요소가 없을 경우 front == rear)
         */
        if (front <= rear) {
            System.arraycopy(array, front + 1, a, 0, size);
        }
        /**
         * front 가 rear 보다 뒤에 있을 경우
         */
        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, front 는 비워야 하기 때문에 사실상 1 부터 채워야 한다.
         */
        System.arraycopy(res, 0, array, 1, res.length);

        this.rear = this.size = res.length;
    }
}