본문으로 건너뛰기

Deque

1 Deque Interface​

  • Deque는 double-ended-queue를 의미한다.
  • Deque는 Queue와 유사하지만 양쪽 끝에서 삽입과 삭제가 가능한 Collection이다.
  • 보통 덱이라고 발음한다.
  • Deque는 Stack과 Queue의 추상화된 인터페이스라고 생각할 수 있다.
    • 즉 Deque를 Stack과 Queue를 대신해서 사용하는 것이 가능하다.

1.1 메소드​

Insert

  • 원소의 수의 제한이 있는 Deque를 사용해 원소를 삽입 하는 경우 offerFirst(e) 와 offerLast(e) 를 사용한다.
    • addFirst(e)와 addLast(e)는 용량이 가득차면 예외를 던지기 때문

Remove

  • Deque가 비어있는 상태에서 아래 메소드 호출 시
    • removeFirst(), removeLast() throw Exception
    • pollFirst(), pollLast() return NULL

Retrieve

  • Deque가 비어있는 상태에서 아래 메소드 호출 시
    • getFirst(), getLast() throw an exception
    • peekFirst(), peekLast() return NULL.

Deque 메소드

Type of OperationFirst Element (Beginning of the Deque instance)Last Element (End of the Deque instance)
InsertaddFirst(e) offerFirst(e)addLast(e) offerLast(e)
RemoveremoveFirst() pollFirst()removeLast() pollLast()
ExaminegetFirst() peekFirst()getLast() peekLast()

1.2 구현체​

  • ArrayDeque
  • LinkedList

1.3 원소 순회​

  • LinkedList는 iterate하기에 좋은 구조가 아니므로 ArrayDeque를 예시로 들겠다.

foreach​

ArrayDeque<String> aDeque = new ArrayDeque<String>();

. . .
for (String str : aDeque) {
    System.out.println(str);
}

Iterator​

ArrayDeque<String> aDeque = new ArrayDeque<String>();
. . .
for (Iterator<String> iter = aDeque.iterator(); iter.hasNext();  ) {
    System.out.println(iter.next());
}

2 ArrayDeque Class​

  • ArrayDeque는 size 조절이 가능한 Circular Array로 Deque Interface를 구현한 구현체다.
    • 용량 제한이 없다
  • 원소로 null을 허용하지 않는다.
  • thread-safe하지 않다.
  • ArrayDeque를 스택처럼 사용할 때 Stack보다 성능이 좋다.
  • ArrayDeque를 큐처럼 사용할 때 LinkedList보다 성능이 좋다.
  • 대부분의 오퍼레이션이 O(1) 시간복잡도를 가진다.
    • remove, removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove() 메소드는 O(N)

3 LinkedList Class​

  • Deque Interface의 구현체
    • List Interface의 구현체이기도 하다
  • ArrayDeque는 Array로 구현했다면 LinkedList는 List로 Deque를 구현했다.
  • 원소로 null을 허용한다.
  • thread-safe하지 않다.

4 어떤 구현체를 사용할까?​

  • 성능면에서 ArrayDeque가 LinkedList 보다 좋다.
  • LinkedList는 iterate하기에 좋은 구조가 아니다.
  • LinkedList이 ArrayDeque 보다 메모리를 더 차지한다.

성능 비교 참고

참고