Java 자료구조 8 - Deque

Java 자료구조 1 - 톺아보기
Java 자료구조 2 - Set
Java 자료구조 3 - Map
Java 자료구조 4 - List
Java 자료구조 5 - Collection
Java 자료구조 6 - Stack
Java 자료구조 7 - Queue, Comparator
Java 자료구조 8 - Deque

 

Deque

Deque는 Queue를 상속받고 있습니다. 먼저 사전에 전달하자면, 큐에서 데이터를 입력하는 enqueue의 반대에 해당하는 dequeue 와는 다릅니다.

---

Module java.base

Package java.util

Interface Deque<E>

Type Parameters:E - the type of elements held in this deque
All Superinterfaces:Collection<E>, Iterable<E>, Queue<E>
All Known Subinterfaces:BlockingDeque<E>
All Known Implementing Classes:ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList

---

Deque는 Double-Ended Queue의 줄임말로 큐의 양쪽에 데이터를 넣고 뺄 수 있는 형태의 자료구조를 의미합니다.

Deque의 앞쪽으로 데이터를 넣고 뒤쪽에서 빼면 Queue처럼 사용할 수 있고, 앞쪽에 넣고 다시 앞쪽에서 빼면 Stack처럼 활용할 수도 있습니다. 양쪽으로 입출력이 모두 가능하지만, 이 중에 한쪽으로만 입력이 가능하도록 설정한 Deque를 scroll이라고 하며, 한쪽으로만 출력할 수 있도록 설정한 Deque를 shelf라고 합니다.

Deque는 interface이기 때문에, 아래와 같이 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque는 물론 LinkedList도 사용이 가능합니다.

Deque<String> deque1 = new ArrayDeque<>();
Deque<String> deque2 = new LinkedBlockingDeque<>();
Deque<String> deque3 = new ConcurrentLinkedDeque<>();
Deque<String> deque4 = new LinkedList<>();

Deque에는 아래와 같이 addFirst(), addLast(), offerFirst(), offerLast()가 존재하며, offer와 add의 차이는 offer의 경우는 데이터 삽입 후 true를 전달하며, 용량 초과 시 false를 전달하나 add는 Exception이 발생합니다.

/**
 * Inserts the specified element at the front of this deque if it is
 * possible to do so immediately without violating capacity restrictions,
 * throwing an {@code IllegalStateException} if no space is currently
 * available.  When using a capacity-restricted deque, it is generally
 * preferable to use method {@link #offerFirst}.
 *
 * @param e the element to add
 * @throws IllegalStateException if the element cannot be added at this
 *         time due to capacity restrictions
 * @throws ClassCastException if the class of the specified element
 *         prevents it from being added to this deque
 * @throws NullPointerException if the specified element is null and this
 *         deque does not permit null elements
 * @throws IllegalArgumentException if some property of the specified
 *         element prevents it from being added to this deque
 */
void addFirst(E e);

/**
 * Inserts the specified element at the end of this deque if it is
 * possible to do so immediately without violating capacity restrictions,
 * throwing an {@code IllegalStateException} if no space is currently
 * available.  When using a capacity-restricted deque, it is generally
 * preferable to use method {@link #offerLast}.
 *
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 * @throws IllegalStateException if the element cannot be added at this
 *         time due to capacity restrictions
 * @throws ClassCastException if the class of the specified element
 *         prevents it from being added to this deque
 * @throws NullPointerException if the specified element is null and this
 *         deque does not permit null elements
 * @throws IllegalArgumentException if some property of the specified
 *         element prevents it from being added to this deque
 */
void addLast(E e);

/**
 * Inserts the specified element at the front of this deque unless it would
 * violate capacity restrictions.  When using a capacity-restricted deque,
 * this method is generally preferable to the {@link #addFirst} method,
 * which can fail to insert an element only by throwing an exception.
 *
 * @param e the element to add
 * @return {@code true} if the element was added to this deque, else
 *         {@code false}
 * @throws ClassCastException if the class of the specified element
 *         prevents it from being added to this deque
 * @throws NullPointerException if the specified element is null and this
 *         deque does not permit null elements
 * @throws IllegalArgumentException if some property of the specified
 *         element prevents it from being added to this deque
 */
boolean offerFirst(E e);

/**
 * Inserts the specified element at the end of this deque unless it would
 * violate capacity restrictions.  When using a capacity-restricted deque,
 * this method is generally preferable to the {@link #addLast} method,
 * which can fail to insert an element only by throwing an exception.
 *
 * @param e the element to add
 * @return {@code true} if the element was added to this deque, else
 *         {@code false}
 * @throws ClassCastException if the class of the specified element
 *         prevents it from being added to this deque
 * @throws NullPointerException if the specified element is null and this
 *         deque does not permit null elements
 * @throws IllegalArgumentException if some property of the specified
 *         element prevents it from being added to this deque
 */
boolean offerLast(E e);

addFirst(), offerFirst()는 Deque의 앞쪽에 데이터를 넣고, addLast(),  offerLast()와 add(), offer()는 Deque의 뒤쪽에 데이터를 넣습니다.

push() 역시 addFirst()와 동일하며, pop()의 경우는 removeFirst()와 동일합니다.(Deque를 Stack 형태로 사용할 때 사용됩니다.)

Deque에서 값을 제거할 때는 아래와 같이 removeFirst(), removeLast(), pollFirst(), pollLast()를 통해 제거할 수 있습니다. 이 차이도 입력과 유사하게 remove의 경우 제거 대상이 없다면 Exception이 발생하며, poll의 경우 null을 리턴합니다.

/**
 * Retrieves and removes the first element of this deque.  This method
 * differs from {@link #pollFirst pollFirst} only in that it throws an
 * exception if this deque is empty.
 *
 * @return the head of this deque
 * @throws NoSuchElementException if this deque is empty
 */
E removeFirst();

/**
 * Retrieves and removes the last element of this deque.  This method
 * differs from {@link #pollLast pollLast} only in that it throws an
 * exception if this deque is empty.
 *
 * @return the tail of this deque
 * @throws NoSuchElementException if this deque is empty
 */
E removeLast();

/**
 * Retrieves and removes the first element of this deque,
 * or returns {@code null} if this deque is empty.
 *
 * @return the head of this deque, or {@code null} if this deque is empty
 */
E pollFirst();

/**
 * Retrieves and removes the last element of this deque,
 * or returns {@code null} if this deque is empty.
 *
 * @return the tail of this deque, or {@code null} if this deque is empty
 */
E pollLast();

이 외 데이터를 찾아서 제거하는 removeFirstOccurrence()나 removeLastOcurrence()등도 존재하며, getFirst(), peekFirst(), peek(), getLast(), peekLast(), contain(), size()등 많은 기능들을 제공합니다.

Deque는 Stack과 Queue를 합친 자료구조 형태로, push, pop연산이 빈번한 알고리즘에서 List보다 좋은 속도를 자랑합니다. 성능상 List 사용 시 문제가 발생한다면 Deque를 활용한 방법을 고려해 볼 수 있습니다.