[자료구조] 9. 배열 덱(Array Deque)

Deque (Using Array)

Deque는 Double-ended queue의 줄임말이다. 두 개의 종료지점이 있는 queue라는 뜻이다. 덱의 장점은 스택처럼 사용할 수도 있고 큐처럼 사용할 수 있는 자료구조이다.

 

덱의 구조를 큐의 구조와 한번 비교해보자

 

 

Deque는 삽입, 삭제가 총 12 종류가 있다.

 

offer 계열과 poll 계열의 경우 삭제 과정에서 저장공간이 넘치거나 삭제할 원소가 없을 때 특정 값(null, false 등)을 반환하지만, add 계열과 remove 계열은 예외를 던진다.

 

---

ArrayDeque 구현

 

<필수 목록>

• 클래스 및 생성자 구성
• resize 메소드 구현
• offer 계열 메소드 구현
• poll 계열 메소드 구현
• peek 계열 메소드 구현
• size, isEmpty, contains, clear 메소드 구현

 

<부가 목록>

• toArray, clone, sort 구현

 

---

 

Deque 클래스 및 생성자 구성하기

 

public class ArrayDeque<E> implements QueueInterface<E> {
    
    private static final int DEFAULT_CAPACITY = 64;
    
    private Object[] array;
    private int size;
    
    private int front;
    private int rear;
    
    public ArrayDeque() {
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.front = 0;
        this.rear = 0;
    }
    
    public ArrayDeque(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;

    front = 0;
    rear = size;
}

 

---

offer 계열 메소드 구현

offerLast를 베이스로 구현한 뒤, offer 메소드에서 offerLast를 호출하는 방식으로 구현한다.

 

1. offer(), offerLast()

 

@Override
public boolean offer(E item) {
    return offerLast(item);
}

public boolean offerLast(E item) {
    if ((rear + 1) % array.length == front) {
        resize(array.length * 2);
    }

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

    array[rear] = item;
    size++;

    return true;
}

 

 

2. offerFirst()

 

public boolean offerFirst(E item) {
    if ((front - 1 + array.length) % array.length == rear) {
        resize(array.length * 2);
    }

    array[front] = item;
    front = (front - 1 % array.length) % array.length;
    size++;

    return true;
}

 

---

poll 계열 메소드 구현

 

1. poll(), pollFirst()

 

pollFirst()를 먼저 구현하고 poll() 메소드 안에서 pollFirst를 호출하는 방식으로 구현한다.

 

@Override
public E poll() {
    return pollFirst();
}

public E pollFirst() {
    if (size == 0) {
        return null;
    }

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

    @SuppressWarnings("unchecked")
    E item = (E) array[front];

    array[front] = null;
    size--;

    // 용량이 최소 크기 (64) 보다 크고 요소 개수가 1/4 미만일 경우
    if (array.length > DEFAULT_CAPACITY && size < (array.length / 4)) {
        // 아무리 작아도 최소 용량 미만으로 줄이지는 않는다.
        resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
    }

    return item;
}

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    E item = pollFirst();

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

    return item;
}

 

 

2. pollLast()

 

public E pollLast() {
    if (size == 0) {
        return null;
    }

    @SuppressWarnings("unchecked")
    E item = (E) array[rear];

    array[rear] = null;

    rear = (rear - 1 +  array.length) % array.length;
    size--;

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

    return item;
}

public E removeLast() {
    E item = pollLast();

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

    return item;
}

 

---

peek 계열 메소드 구현

 

1. peek(), peekFirst()

 

@Override
public E peek() {
    return peekFirst();
}

public E peekFirst() {
    if (size == 0) {
        return null;
    }

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

    return item;
}

 

 

2. peekLast()

 

public E peekLast() {
    if (size == 0) {
        return null;
    }

    @SuppressWarnings("unchecked")
    E item = (E) array[(rear)];
    return item;
}

 

 

3. element(), getFirst()

 

public E element() {
    return getFirst();
}

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

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

    return item;
}

 

element 메소드와 getFirst 메소드는 같은 메소드다. peek 메소드를 호출하여 맨 앞의 원소를 얻고 만약 Null 이라면 예외를 던진다.

 

 

4. getLast()

 

 

public E getLast() {
    E item = peekLast();

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

 

 

4. clear()

 

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

    front = rear = size = 0;
}

 

---

<부가 목록>

 

toArray, clone, sort 메소드 구현

 

https://yoseph0310.tistory.com/178 의 것과 같다.

---

정리

 

기본적으로 Deque는 자바로 구현할 경우 LinkedList로 구현하는 것이 훨씬 편하다. 자바에서는 배열로 구현되고 있다.