[JAVA] Deque 직접 구현하기

Deque 란

 Queue에서 확장된 개념이다. 선입선출로 가장 첫번째 node만 꺼내고 빼올 수 있던 단방향 구조인 Queue와는 달리 Deque ( Double-ended Queue)는 양방향 구조이다.

Deque의 기본 구조이다.

 Queue의 연장선이기 때문에 Queue와의 차이점은 한쪽에서만 뺄 수 있느냐(단방향이냐) 양쪽에서 뺄 수 있느냐(양방향이냐)일 뿐 다른 차이점은 없다. 따라서 단방향구조였던 Queue 인터페이스를 상속받아서 양방향으로 메소드를 더 추가해주는 과정을 거친 것이 Deque라고할 수 있다.

 

구현

 Deque는 구조적으로 Queue의 기능을 양방향으로 확장한 개념이기 때문에 Queue를 상속받아서 구현한다.

Deque는 Queue 인터페이스를 상속받는다.

 Queue 구현에서 메소드는 너무 단순했다. LinkedList가 Queue를 상속(Deque를 상속받고 Deque가 Queue를 상속)받아 실제로 Queue로 인해서 구현해야할 메소드는 추가하는 offer(), 상위값 가져오는 peek(), 상위값 제거하는 poll()뿐이었다.

 Deque는 여기에 더불어서 List의 가장 끝에 있는 값도 추가, 삭제를 할 수 있는 자료구조이기 때문에 first node 뿐만 아니라 last node를 추가, 삭제할 수 있는 메소드를 추가해야한다.

 

 구현 목록은 다음과 같다. 기존 Queue 인터페이스의 메소드 역시 마찬가지로 사용가능하다.

• offerFirst()
• offerLast()
• pollFirst()
• pollLast()
• peekFirst()
• peekLast()

(코드 가독성을 위해 javadoc는 지우고 코드를 설명했다. 전체코드는 github.com/jinyoungchoi95/DataStructure/blob/master/src/DataStructure/Queue/Deque.java에서 확인할 수 있다.)

 

 

1. default 세팅

package DataStructure;

public interface Deque<E> extends Queue<E> {

 Deque는 Queue 인터페이스를 상속받는다. Queue에서 확장한 개념이 Deque이기 때문이다.

 따라서 Queue에서 구현했던 offer(), poll(), peek() 모두 Deque 인터페이스에서 사용할 수 있다.

 

2. offerFirst(), offerLast()

 Deque의 최상단에 추가하거나 최하단에 추가하는 메소드이다. offerFirst()는 결국 offer() 메소드와 동일한 기능을 하므로 offerLast()만 보면

@Override
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

public void addLast(E e) {
    linkLast(e);
}

private void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null) {
        first = newNode;
    } else {
        l.next = newNode;
    }
    size++;
}

offrLast() 메소드와 LinkedList에 구현되어있는 addLast()메소드는 결국 같은 구현부를 가지고 있다. LinkedList의 가장 마지막 node에 새로운 마지막 node를 추가하는 것이 linkLast()메소드이며, offerLast()는 반환값이 boolean으로 반환이 된다면 항상 true가 리턴 된다.

 

3. peekFirst(), peekLast()

 Deque의 최상단의 값, 최하단의 값을 받아오는 메소드이다. peekFirst()는 마찬가지로 peek()메소드와 동일한 기능을 하므로 peekLast()메소드만 본다.

@Override
public E peekLast() {
    Node<E> node = last;
    return node == null ? null : node.item;
}

 LinkedList의 가장 마지막에 있는 node는 last로 지정해두었기 때문에 last 참조변수를 받아온다. size가 만약 0라면 last는 null이다. 리턴하는 값은 size가 0이라면 null을, 아니라면 last node에 있는 값을 리턴한다.

 

4. pollFirst(), pollLast()

@Override
public E pollLast() {
    Node<E> node = last;
    return node == null ? null : unlinkLast();
}

private E unlinkLast() {
    final E item = last.item;
    final Node<E> prev = last.prev;

    last = prev;
    if (last == null) {
        first = null;
    } else {
        last.next = null;
    }
    size--;
    return item;
}

pollFirst() 메소드도 마찬가지로 poll() 메소드와 동일하며 pollLast()는 LinkedList에서 last node를 제거하는 unlinkLast() 메소드를 사용하여 last node가 비었으면 null을, 아니라면 unlinkLast()를 통해서 last node를 하나 끊어준다.

 

 

Queue와 Deque 그리고 ArrayDeque

 사실 Queue도 그렇고 Deque도 자료구조의 구현도가 그렇게 심하지는 않다. 이미 구현되어있는 List 구조에서 Queue에서 원하는 선입선출기능, Deque에서 원하는 Queue의 확장기능을 추가만 하면 되는 것이기 때문에 구현량은 생각보다 빈약하다.

 구현량이 빈약해서 안좋다는 것은 아니다. 충실하게 List 인터페이스와 Queue 인터페이스를 기능에 따라서 분류할 수 있었고 List에서 사용한 메소드들을 재사용해서 사용하는 등 자바의 객체지향적인 장점을 사용하였다.

 

 재미있었던 사실을 Queue와 Deque의 도입시기와 그에 맞추어서 새로 생기는 ArrayDeque가 있다는 것이다.

 Collection 프레임워크들이 나온 시기에 대해서 앞전에 이야기했었지만 Queue와 Deque의 관점에서 이야기해보면,

• JDK 1.2 : List 인터페이스 (ArrayList, LinkedList) 도입
• JDK 1.5 : Queue 인터페이스 도입
• JDK 1.6 : Deque 인터페이스, ArrayDeque 도입

 Deque는 Queue 다음 버전에 업데이트 되었고 사실 LinkedList는 Queue를 처음에 상속받지 않았을까하는 업데이트 과정이라고 생각한다.

 또한 1.6에서는 ArrayDeque 또한 업데이트 되어 Oracle에서는 상황에 따라 Queue와 Deque를 구현하는데 있어서 ArrayDeque를 추천하기도 한다.(https://docs.oracle.com/javase/tutorial/collections/implementations/deque.html)

 ArrayDeque에 대한 내용은 다음 포스팅에서 ArrayDeque를 직접 구현하면서 이야기할 예정이다.

 

 

 

앞에서도 말했지만 전체 코드는 깃허브에 전부 저장해두었습니다.

최대한 공식문서와 실제 class 파일을 참고하여 만들었지만 혹시 모를 이탈자나 잘못된 부분은 댓글로 피드백 부탁드립니다.