[자료구조] Deque

Deque이란?

(Double-ended Queues의 줄임말. 디큐라고 발음하는 줄 알았는데 덱 / 데크라고 한다.)

스택과 큐를 합쳐놓은 자료구조라고 생각하면 쉽다.

앞과 뒤에서 삽입/삭제가 가능하다.

 

 

Java에서 사용법

1. 선언

Deque<Integer> deque = new LinkedList<>();

Deque<Integer> deque = new ArrayDeque<>();

 

Deque를 구현할 때 보통 LinkedList와 ArrayDeque를 사용한다.

 

(성능차이)

- 양 끝의 데이터를 add / remove할 때 : ArrayDeque > LinkedList

- 반복 작업에서 현재 요소를 삭제할 때 : ArrayDeque < LinkedList

참고 : https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist

 

 

2. 삽입

add()	deque의 끝 부분에 값 추가	성공 시 true 반환, 실패 시 Exception 발생
addFirst()	deque의 처음 부분에 값 추가	실패 시 Exception 발생
addLast()	deque의 끝 부분에 값 추가 (= add())	실패 시 Exception 발생
offer()	deque의 끝 부분에 값 추가	성공 시 true 반환, 실패 시 false 반환
offerFirst()	deque의 처음 부분에 값 추가	성공 시 true 반환, 실패 시 false 반환
offerLast()	deque의 끝 부분에 값 추가 (= offer())	성공 시 true 반환, 실패 시 false 반환

 

 

3. 삭제

remove()	deque의 첫 값 삭제	삭제된 값 반환, 실패 시 Exception 발생
removeFirst()	deque의 첫 값 삭제 (= remove())	삭제된 값 반환, 실패 시 Exception 발생
removeLast()	deque의 끝 값 삭제	삭제된 값 반환, 실패 시 Exception 발생
poll()	deque의 첫 값 삭제	삭제된 값 반환, 실패 시 null 반환
pollFirst()	deque의 첫 값 삭제 (= poll())	삭제된 값 반환, 실패 시 null 반환
pollLast()	deque의 끝 값 삭제	삭제된 값 반환, 실패 시 null 반환

 

3. 확인

element()	deque의 첫 값 확인	첫 값 반환, 실패 시 Exception 발생
getFirst()	deque의 첫 값 확인 (= element())	첫 값 반환, 실패 시 Exception 발생
getLast()	deque의 끝 값 확인	끝 값 반환, 실패 시 Exception 발생
peek()	deque의 첫 값 확인	첫 값 반환, 실패 시 null 반환
peekFirst()	deque의 첫 값 확인 (= peek())	첫 값 반환, 실패 시 null 반환
peekLast()	deque의 끝 값 확인	끝 값 반환, 실패 시 null 반환