Deque

Deque

보통 큐(Queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 Dequq(덱 or 데크)다. Deque(덱 or 데크)은 Dobule-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조를 의미한다. Deque은 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수 있고, 큐(Queue)로도 사용할 수 있다. 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(Scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(Shelf)라고 한다. 덱은 주로 시간복잡도를 줄이기 위해 사용된다.

Deque의 시간 복잡도

Deque은 양끝 요소에 append, pop할 때 시간 복잡도가 O(1)이며, 인덱스로 조회할 시에는 O(n)이다. 인덱스 조회의 속도가 중요할 땐 그냥 List를 사용한다.

Java에서의 Deque

Java에서의 덱은

Interface

Deque Interface

ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList

Java Deque Method

• addFirst() - 덱의 앞쪽에 엘리먼트를 삽입. 용량 제한이 있는 경우, 용량 초과시 예외(Exception)가 발생
• offerFirst() - 덱의 앞쪽에 엘리먼트를 삽입. 정상적으로 엘리먼트가 삽입된 경우 true가 return, 용량 제한에 걸리는 경우 false를 return
• addLast() - 덱의 마지막 쪽에 엘리먼트를 삽입. 용량 제한이 있는 경우, 용량 초과시 예외(Exception)가 발생
• add() - addLast()와 동일
• offerLast() - 덱의 마지막 쪽에 엘리먼트를 삽입. 정상적으로 삽입된 경우 true가 return, 용량 제한에 걸리는 경우 false를 return

• removeFirst() - 덱의 앞쪽에서 엘리먼트 하나를 제거한 다음 해당 엘리먼트를 return. 덱이 비어있으면 예외 발생