[자료구조] Deque(덱/데크)가 무엇일까?

---

Deque란?

 

자료구조 Deque는 Queue의 특성과 Stack의 특성을 모두 가지고 있는 자료구조 입니다!

 

왼쪽, 오른쪽 방향 상관없이 삽입/삭제가 가능합니다.

Deque의 오른쪽에서 데이터는 삽입하고, 왼쪽에서 삭제하면 Queue의 특성을 갖는 것이고,

Deque의 왼쪽에서 삽입하고, 오른쪽에서 삭제한다면 Stack의 특성을 갖게 되는 것입니다.

 

시간 복잡도는 삽입/삭제는 O(1)이며, 검색은 O(n)이 됩니다.

 

 

---

 Deque 명령어 알아보기

 

- 삽입

addfirst()

: deque 앞쪽에 엘리먼트를 삽입한다. 용량제한이 있는 deque인 경우, 용량이 초과하면 예외가 발생한다.

 

offerfirst()

: deque 앞쪽에 엘리먼트를 삽입한다. 정상적으로 삽입된 경우 true가 리턴되고, 용량제한에 걸리면 false를 리턴한다.

 

addLast(), add()

: deque 마지막에 엘리먼트를 삽입한다. 용량제한이 있는 deque인 경우, 용량이 초과하면 예외가 발생한다.

 

addLast()

: deque 마지막에 엘리먼트를 삽입한다. 정상적으로 삽입된 경우 true가 리턴되고, 용량제한에 걸리면 false를 리턴한다.

 

 

- 삭제

removeFirst(), remove()

: deque 앞쪽에서 엘리먼트를 가져와서 제거한 후 리턴한다.  deque이 비어있는 경우, 예외가 발생한다.

 

pollfirst(), poll()

: deque 앞쪽에 엘리먼트를 가져와서 제거한 후 리턴한다. deque가 비어있는 경우 null이 리턴된다.

 

removeLast()

:  deque 뒤쪽에서 엘리먼트를 가져와서 제거한 후 리턴한다. deque이 비어있는 경우, 예외가 발생한다.

 

pollLast()

: deque 뒤쪽에서 엘리먼트를 가져와서 제거한 후 리턴한다. deque가 비어있는 경우 null이 리턴된다.

 

 

- 그 외

getFirst()

: 첫 번째 엘리먼트를 확인하며, deque가 비어있는 경우 예외가 발생한다.

 

peekFirst(), peek()

: 첫 번째 엘리먼트를 확인하며, deque가 비어있는 경우 null를 리턴한다. 

 

getLast()

: 마지막 엘리먼트를 확인하며, deque가 비어있는 경우 예외가 발생한다.

 

peekLast()

: 마지막 엘리먼트를 확인하며, deque가 비어있는 경우 null를 리턴한다. 

 

conatains()

: deque에 Objact 인자와 동일한 엘리먼트가 포함되어 있는지 확인한다.

 

size()

:deque에 들어있는 엘리먼트 개수를 반환한다

 

 

---

Deque 사용해보기

 

- 생성

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

 

 

- 순회

// for 문을 이용한 순회
for (String elem : deque1) {
  System.out.println(elem);
}

// Iterator를 이용한 순회
Iterator<String> iterator = deque1.iterator();
while (iterator.hasNext()) {
  String elem = iterator.next();
  System.out.println(elem);
}

// 역순순회 
Iterator<String> reverseIterator = deque1.descendingIterator();
while (reverseIterator.hasNext()) {
  String elem = reverseIterator.next();
  System.out.println(elem);
}